合同算術
数学において、ある文脈で発展した概念がまた別の領域で再利用されることは常であり、例えば群論は算術や幾何学に応用される。それは合同算術の道具についても同じであり、これらの道具は抽象代数学やガロワ理論などを含む純粋数学の広汎な分野において影響を与えた。これらの理論は、もはや合同算術の特別の場合とは考えられることがないほどに、合同算術には無い多くの概念を含んでいる。
素数による商体 Z/pZ の構成は他の構造へ一般化される。情報処理において、数は n ビットでコードされる(つまり、数は 0 と 1 からなる長さ n の数列に対応する)。それは二元体 F2 上の n-次元ベクトル空間のベクトルと見なすことができる。この構造はしばしば F2 に係数を持つ次数が m より真に小さい多項式全体の成す空間と見なされる。乗法について閉じているためには、この空間は次数 n の適当な多項式 f で割られなければならない。その多項式 f が既約(素数に対応するもの)であるとき、得られる構造は位数 2 の有限体になる。数 a modulo 2 と多項式 P modulo f はよく似ており、事実
のように書ける。 用例の一つは F2 上の疑似乱数生成器である。そのような生成器は例えば携帯電話での音声通信の文脈でストリーム暗号 A5/1 によって使われる。これは線形帰還シフトレジスタ (LFSR) の後ろの成分を持つ。F2 の元の長さ n の二つの有限列として、係数列および初期化列が
で与えられるとき、LFSRは疑似乱数列 (uj) を線形回帰数列
によって得る。係数列はしばしば固定される。ゆえに鍵は、整数 a modulo 2 で表される初期化列
を与える。得られた結果は周期的だが、係数列を適切に選べば周期は 2 – 1 と非常に長くなる。この状況は、
で与えられる「帰還多項式」R が巡回群 (F2)* の生成元の最小多項式であるときに生じる。
ガウスは有理係数多項式の集合にも(そこでは加法、乗法およびユークリッド除法ができるから)合同算術の論理を持ち込めることを指摘している。多項式の合同は、特定の多項式によって多項式を割った剰余によって与えられる。
ガウスはそのような方法論を円分多項式と呼ばれる多項式 X– 1 に適用してその既約元分解を得ている。またガウスはその結果を以って正十七角形の定規とコンパスによる作図を発見した。
ガウスはこれらの業績を算術と看做すことを躊躇っており、
と記している。この論法の論理は今日も有効である。