数学、特に初等代数的整数論における合同算術（ごうどうさんじゅつ、英: modular arithmetic; モジュラ計算）は、（剰余を持つ除法の意味で））自然数あるいは整数をある特定の自然数で割ったときの剰余に注目して、自然数あるいは整数に関する問題を解決する一連の方法の総称である。合同算術の起源は、一般にはガウスが著作『Disquisitiones Arithmeticae』を出版する1801年にまで遡れるものとされる。ガウスによる合同を用いたこの新しい手法は、有名な平方剰余の相互法則を明らかにし、より抽象的な観点からウィルソンの定理などの定理の記述の簡素化に一役を買った[注釈 1]。ガウスの研究は自然数を扱う整数論のみならず、代数学や幾何学といった数学のほかの主要な分野にまで影響を与えるものであった。
この手法の基本は、「数それ自体」ではなくそれを別な数で割った（商がいくらになるかということは無視して）「剰余だけ」を考えるということにある。こういった考え方は何か特殊で高尚なものというようなものではなく、実際に日常生活においても時刻や角度といったものの計算や単位の換算などで、ちょっとした合同算術が特別な知識無くあるいは無意識に行われているのである。
20世紀には、合同算術にまつわる状況は大きく様変わりをしている。計算機やウェブの普及に伴って情報セキュリティの観点からの暗号化アルゴリズムの開発や取り扱いといったような場面で古典的な合同算術に関する理論の工業的・商業的応用が頻繁に見られるようになった。
歴史
ヨーロッパの怪物
1621年、クロード＝ガスパール・バシェ・ド・メジリアク (1581 - 1638) はディオファントスの本『算術』をラテン語に翻訳し、そこに書かれていた問題について当時の（特にフランスの）数学者が興味を持つこととなる。ピエール・ド・フェルマー (1607 - 1665) は多数の定理を残したが、中でも有名なものは大定理、二平方和定理、小定理の3つであろう。科学コミュニティがこの話題にこぞって取り組むなか、フェルマーは「平方数の和で立方数となるものを求めよ」という問いを発し、« j'attends la solution de ces questions; si elle n'est fournie ni par l'Angleterre, ni par la Gaule Belgique ou Celtique, elle le sera par la Narbonnaise »（“この問いが解決されることを望む。それがイングランド人でもガリア・ベルギー人でもケルト民でもなく、フランス・ナルボンヌの人の手で為されることを。”）と結んでいる[2]。
マラン・メルセンヌ (1588 - 1648) は今日メルセンヌ素数と呼ばれる素数について研究した。フェルマーはメルセンヌに « Si je puis une fois tenir la raison fondamentale que 3, 5, 7, 17, 257, 65537, …, sont nombres premiers, il me semble que je trouverai de très belles choses en cette matière, car j'ai déjà trouvé des choses merveilleuses dont je vous ferai part »（“3, 5, 7, 17, 65537, ... が素数であるとする基本的理由を正しいとするならば、このことについて、いくつかの素敵なことを見つけることができるように思えます。なぜなら、私はすでにいくつかの素晴らしいことを見つけているからです。その私が見つけた素晴らしいことをあなたと共有しましょう。”）と言っている[3]が、これらの数は今ではフェルマー数と呼ばれ、フェルマーの言っていたこれらが全て素数となるだろうという予想は偽であることが知られている。ルネ・デカルト (1596 - 1650) はそれらとは独立に研究を進め、素数の 8 を法とする剰余が 1 または 3 ならば、その素数は x2 + 2y2 の形に書けるということを示した
この手の問題については興味深い要素がふたつあった。
- 人々がディオファントス方程式にいかに心奪われたかということは、バシェ・ド・メジリアクの本の一つの表題が "Problèmes plaisants et délectables qui se font par les nombres"（『数それ自身の成す喜ばしくもほほえましい問題』）であるということや、フェルマーが大定理について « J'ai trouvé une solution merveilleuse ... »（“驚くべき証明を発見した……”）と書き残している[4]ことなどにも顕れている。
- 簡単そうな問題が意外に難しい。おそらくバシェ・ド・メジリアクの手によってベズーの等式のいくつかはうまく解かれたけれども、問題の本質的な部分に答えるようなものではなかったし、フェルマーの二平方和定理にしても答えをほとんど誰も理解できないもので、フェルマーの最終定理にしてもフェルマー自身が « ... mais la place me manque ici pour la développer »（“……しかしこの余白はそれを記すには狭すぎる”）という書き込みを残したのみであった（はじめてきちんとした証明が現れるのは1994年と1995年である[5])）。フェルマーはしばしば自身の失敗を自白するコメント « Je vous avoue tout net (car par avance je vous avertis que je ne suis pas capable de m'attribuer plus que je ne sais, je dis avec la même franchise ce que je ne sais pas) que je n'ai pu encore démontrer... cette belle proposition que je vous ai envoyée... »（“わたしは極めてはっきりと告白しますよ（私が前もって言っていたように、自分で知っていることしか、私がやったとは言えませんから。また、私が何を知らないのかも、同じように正直に言いましょう）、この美しき命題を私はまだ証明できていない、と。その命題をあなたに送ります”）で彼の定理を締めくくっている[6]。
18世紀の数学
フェルマー問題のいくつかは、続く18世紀に、大部分はオイラーの手で解かれていった。オイラーは二平方和問題の証明の過程で、いわゆるフェルマー数が常に素数となるわけではないことを示した[7]。そういった成功とともに、オイラーはいくつかの誤りも犯しており、フェルマーの大定理の n = 3 の場合の証明に失敗している（彼の最初の証明[8]は誤りである）。1782年には、新たな問題として平方剰余の相互法則が俎上に上がることになる。そして、アドリアン＝マリ・ルジャンドル (1752 - 1833) により残りの問題も精力的に解かれていった[9]。
19世紀の初頭には、それまで数学者が用いていた大仕掛けな道具立て（手法や表記法）も、単純な原理を導入することによって徐々に必要なくなっていった。「二つの平方数の和で 4 を法とする剰余が 3 であるようなものは存在するか」という有名な 3 に対する二平方和問題を例に取ろう。証明の内容としては「a2 および b2 を二つの平方数とする。a, b ともに偶数であるかともに奇数であればそれらの和の 4 を法とする剰余は 0 か 2 である。a が偶数で b が奇数とすると、偶数 a の平方は 4 の倍数であり、奇数 b は b = 2c + 1 と表せて、その平方は 4c2 + 4c + 1 となるので、b2 の 4 を法とする剰余は 1 となり、したがって所期の平方和の 4 を法とする剰余は 1 であるとわかる」といった感じであるが、ここでいくつかの道具立てが用いられている。
- 一つ目の道具は、ちょうどふたつの因数を持つものとしての素数である。
- 二つ目は、b を 2c + 1 と表すような「文字の置換え」である。適切に置換える文字を選ぶことによって、数学者はいくつもの整数問題を解決することができた。
- 三つ目は「除法の原理」であり、これによって平方や平方和を 4 で割ることが機械的・系統的に行える。
- 四つ目は例示には表れていないが、二平方和定理のオイラーによる証明に用いられた無限降下法である。これは「自然数解が在れば必ずそれよりも小さな自然数解があることを示すことで、そのような自然数解の存在が繰り返し示され、自然数からなる無限降下列が構成されることになるが、このようなことは不可能である」というものである。これはフェルマーの大定理の n = 4 の場合を証明するのに利用されている。
オイラーによる二平方和定理の証明にしたところで、古い伝統的な道具立てでは証明は長く技巧的なものにならざるを得ず、そのような方法では1世紀以上の努力を費やしてもフェルマーの整数問題を解決することはできなかったのである。
ガウスの貢献
17歳のガウス (1777 - 1855) は平方剰余の相互法則を示した。翌1796年3月30日、ガウスは17次の円分方程式を解くというきわめて算術的な研究の過程で、古来から未解決の幾何学的問題であった定規とコンパスによる正十七角形の作図が可能であることに気付く。最終的に1801年、ガウスは "Disquisitiones Arithmeticae"（『算術の研究』）を著して数学王子と渾名された[10]。
これら二つの大きな発見は共に、フェルマーやオイラーが用いたような道具よりもより抽象的で明確な道具を用いて、証明に掛かる大きな負担を軽減するという過程のなかで為されており、その過程は合同算術として結実する。
ガウスは整数係数多項式をつかって整数概念の拡張を行い、今日ではガウス整数と呼ばれる数の集合を得ている。ディリクレ (1805 - 1859) も類似の整数の集合を発見しており（それはディリクレ整数と呼ばれる）、それを足がかりとしてフェルマーの大定理の n = 5 の場合を証明した。その論文は1825年に科学アカデミーに提出され、ルジャンドルの数ヶ月に亘る査読を受けた後に受理されている[11]
そのころフェルマーの整数問題は、最終定理を除くすべてが解決されていたが、新しい予想も現われていた。たとえば、a と b が互いに素ならば初項 a で公差が b の等差数列のなかに素数は存在するか、存在するとしたらどのくらい含まれるか、というものである。ガウスやルジャンドルらの数学者は無限に存在するだろうと考えたが、平方剰余の相互法則と同様の高次の冪剰余に対する相互法則が必要であり、証明はできなかった。
その後も合同算術は発展を続け、ディリクレはディリクレ指標の概念や解析数論の基礎を固めることによって算術級数定理を証明した[12]。その証明は合同算術の珠玉ともいえるもので、ヤコビ (1804 - 1851) は兄弟への手紙に
En appliquant les séries de Fourier à la théorie des nombres, Dirichlet a récemment trouvé des résultats atteignant les sommets de la perspicacité humaine.（フーリエ級数を数論に応用することで、ディリクレは人類の洞察力の頂点に到達するような結果を見出した）
と記している[13]。今では有限可換群上の調和解析から得られる道具を用いて証明することができるが、ルジャンドルはそういった道具は用いておらず、今ではルジャンドル記号と呼ばれる概念を定式化することにより、平方剰余の相互法則と同様の計算を実数に対して行うことで証明した[14]。ガウスは1801年の著書で最終的にこの方法を複素数にまで拡張した。この計算は ガウス和とガウス周期と呼ばれる。
19世紀にはこれらの数学は超越数論[15]と呼ばれ、算術 (arithmetic) という呼称もより一般の数学を指す言葉として残ったが、1830年にルジャンドルは、この十分に発展を遂げた分野を表すため、数論 (theory of numbers) [16]という呼称を考案した。ガウスのころの算術とは異なる新しい手法が用いられるようになり、代数的整数-論と解析的-数論という分科が現れるようになると、超越数の登場もあって、超越数論という呼称は過去のものとなっていった。
20世紀の合同算術
暗号理論
情報理論
合同算術の道具立て
整数の合同
「合同算術」の歴史的な例は整数に基づくものである。一つの自然数 n を固定して「法 n で考える (modulo n)」とは、任意の整数をそれを n で割った剰余と同一視するものである。例えば n = 12 のときは時計算として詳しく知られるものになる。これは 12 時間だけことなる時刻において時針は同じ位置にあるということと理解すれば、例えば 13 時間と 1 時間は同一視される。そのような集合上で算術を行うには、その加法および乗法が上記のような同一視と両立することを確かめねばならない。そうしてルジャンドル[17]によって「剰余」を数とは異なる対象を与えるものして定式化された。
ガウスの貢献はこの集合、今日整数の合同類 の環 ℤ/nℤ と呼ばれる代数系、の構造を詳らかにするものであった。第一に加法に関して考えれば、これは 1 を生成元とする巡回群を定める。第二に乗法に関しては、これは法 n に依存して性質が異なり、法 n が素数ならば体が得られる。このような方法により、計算の記述は簡素化される。その歴史的な例が、ガウスの著書 Disquisitiones Arithmeticae に載っているウィルソンの定理[18]およびフェルマーの小定理[19]である。
法 n が素数でない場合の合同算術はより複雑なものとなるが、その構造を明らかにするのに中国の剰余定理が利用できる。この場合の合同類環は整域を成さず、零因子（それ自身は非零だが、ほかの非零元に掛けると零になる元）が存在する。この環における可逆元の数はオイラー数 φ(n) で与えられ、例えば一般化されたフェルマーの小定理が成り立つ。
多項式の割り算
ガウスは有理係数多項式の集合にも（そこでは加法、乗法およびユークリッド除法ができるから）合同算術の論理を持ち込めることを指摘している。多項式の合同は、特定の多項式によって多項式を割った剰余によって与えられる。
ガウスはそのような方法論を円分多項式と呼ばれる多項式 Xn– 1 に適用してその既約元分解を得ている。またガウスはその結果を以って正十七角形の定規とコンパスによる作図を発見した。
ガウスはこれらの業績を算術と看做すことを躊躇っており、
« La théorie de la division du cercle, ou des polygones réguliers…, n'appartient pas par elle-même à l'Arithmétique, mais ses principes ne peuvent être puisés que dans l'Arithmétique transcendante »[20].（訳:「この円あるいは正多角形の分割理論は……「それ自身」は算術ではない、が「その原理」は超越的な算術に拠ってしか描くことはできない」）
と記している。この論法の論理は今日も有効である。
代数的整数
整係数多項式の場合は少し事情が異なり、除法がうまく行くには最高次係数が ±1 でなければならない。多項式 X2 + 1 を法とする算術を考えれば、その商構造はやはり環を成し、整数 α, β と虚数単位 i に対して α + iβ の形に書ける数全体の成す集合と同一視することができる（i と単項式 X が対応する）。このような数の集合はガウスの整数環である。
ガウス整数環はノルムを考えることができる。ガウス整数 a = α + iβ には（複素数の絶対値から導かれる）ノルム α2 + β2 が割り当てられる。このノルムを用いて（右図のように）ユークリッド除法が定義できる。ガウス整数はガウス平面上の（成分が整数の）格子点として表すことができることに注意する。ガウス整数 a, b の複素数としての商 a⁄b は b が非零ならば存在するが、それは必ずしもガウス整数ではない。ユークリッド除法が可能であるというのは、a⁄b との差のノルムが最小となるガウス整数がただ一つ存在するということである（右図ではその候補が少なくとも三点、一般には一点から四点の候補が考えられる）。
ユークリッド除法が可能であることからこの整数環の性質がいくつか導かれる（ベズーの等式、ガウス素数の存在、および素因数分解の一意性などを挙げることができる）。ガウス素数を用いてデテキントはフェルマーの二平方和定理の平易な証明を与えている（左図はそれを視覚的に示したもの）。素数 p が二つの平方の和に表すことができるのは、p の平方根を半径とする単位円が少なくとも一つのガウス整数と交わるときである。
ゴットホルト・アイゼンシュタインは1844年にガウスと邂逅し[21]、新たな整数環を発見している[22]。アイゼンシュタインの整数環の算術はフェルマーの最終定理の n = 3 の場合の厳密な証明に利用できる。そういった意味合いからも、このような一般化された合同算術の理論の必要性が正当化される。
ディリクレ指標
ディリクレは互いに素な整数 n, m と正整数を亙る変数 λ に対して n + λm の形に書ける数について注目し、このような数の世界における素数が実際に無数に存在することを示そうと試みた。そのような問題に対して合同算術は有効な道具であり、それはつまり剰余類における素数全体の成す集合の濃度を知ることに同じである。
ディリクレは、法 m に関して可逆な元全体の成す群（環 ℤ/mℤ の単元群、つまり既約合同類群 (ℤ/mℤ)×）を考え、その群から非零複素数全体の成す乗法群への群準同型（すなわち、群の元 a, b に対して f(ab) = f(a)f(b) を満たす写像）全体の成す集合について調べた。このような写像をディリクレ指標という。ディリクレ指標は φ(n) 個存在し、二つの指標の積はまた一つの指標であり、乗積表を書けばそれは既約合同類群のものと全く同じになる。
このような写像を計算することはフーリエが先駆的に為した仕事の形式的なアナロジーであった[23]。にも拘らず、これら二つのやり方を統一する理論（それは調和解析と呼ばれる）の登場は20世紀を待たねばならない。
理論の展開
数学において、ある文脈で発展した概念がまた別の領域で再利用されることは常であり、例えば群論は算術や幾何学に応用される。それは合同算術の道具についても同じであり、これらの道具は抽象代数学やガロワ理論などを含む純粋数学の広汎な分野において影響を与えた。これらの理論は、もはや合同算術の特別の場合とは考えられることがないほどに、合同算術には無い多くの概念を含んでいる。
商構造
現代的な言葉で言えば、合同算術はユークリッド環の商の概念によって定式化できる。この概念は同値関係の概念により、多くの代数的構造に対して一般化される。例えば群の正規部分群による商はジョルダン–ヘルダーの定理を通じて有限群の分類の基本的な道具であり、また代数的位相幾何学においても代数多様体の分類に利用される。環論においてはイデアルが正規部分群の役割を果たし、合同算術を含むもっと広い文脈において用いられる商環の概念が定式化される。可換環論と代数幾何学の橋渡しを為すヒルベルトの零点定理はイデアルの言葉で表される。
とはいえ、合同や法といった語はユークリッド環の商の場合のために用いるのが普通である。
多項式の割り算とガロワ理論
可換体に係数を持つ多項式環は、除法が可能であるから、合同算術を考えることができる。ガロワ理論の出発点は多項式を既約多項式（これが数の場合の素数に相当）で割った合同類の集合を体系的に扱うことにある[24]。これら集合は今日では代数拡大と呼ばれる。
これら拡大により代数方程式（つまり、多項式の等式として書かれる方程式）の可解性が調べられるようになる。与えられた多項式が既約ならば、それを法とする合同類の集合は少なくとも一つその多項式の根を含む体を成す。これを根体と呼ぶ。これを繰り返して与えられた多項式の根をすべて含む体（分解体）が構成できる。合同に関する商を考える論法はこの問題に適した代数的構造を与えるのである。
ガロワ理論では他に様々な概念を利用する。方程式の可解性は、ガロワ対応と呼ばれる部分体と部分群の間の対応により、ガロワ群と呼ばれる体の自己同型群の研究を通じて調べられる。代数方程式の可解性の研究に留まらず、ガロワ理論は算術、数論幾何学や代数幾何学の様々な問題の解法の自然な一部を成し、また時にそういった様々な領域における新しい広汎な問題の定式化をもたらした。
同様の理論をより一般のユークリッド環の商の概念を用いて記述するとき、合同算術の特定の道具からの繋がりにおいて、本項の主題とは大きく異なる別の領域が生じてくる。このような理論の成果の一つが、ガロワ体とも呼ばれる有限体であり、これは合同算術の様々な応用において自然な設定を与える。
代数的整数と代数的整数論
合同算術はフェルマーの大定理を分析するためのよい枠組みを与えた。しかし、n が 10 より大きいとき、ガウスの方法に準じて構成される代数的整数の環を、ディリクレは obstruction（邪魔なもの）と呼んだ。これらの整数環ではその（乗法逆元を持つ元全体の成す）単数群が、ガウスの研究とは異なり、もはや巡回群や有限アーベル群ではないことが示せる。それは整数の加法群のコピーを含み、無限群である。この結果はディリクレの単数定理と呼ばれる。このような新しい状況では、付随する環がユークリッド環でないため、ガウス整数に用いた合同算術の道具が使えないという障害 (obstruction) を生じる。
素数が存在しない環における素数の代替として、エルンスト・クンマーは、今日ではイデアルを用いて定式化される商の一般化に関する道具を用いた。代数的整数論ではそれまでと異なるいくつかの手法が取り入れられる。基本的な道具は、その元が代数的整数と呼ばれ、デデキント環と呼ばれる構造を持つ環である。クンマーは n が正則素数と呼ばれる特定の種類の素数であるときのフェルマーの大定理を証明した[25]。100 以下の値でこれに相当しないものは 37, 59, 67 の三つのみである。
そのほかの道具や数学的対象としては、アデール環、ガロワ理論の各概念、楕円曲線、ディリクレの L-級数とモジュラー形式などが挙げられる。有限体などの合同算術にほぼ由来するいくつかの概念は20世紀においても広く用いられ、ときどき同様の手法をそのまま使うことはあるけれども、代数的整数論は合同算術の範囲を大きく超えた分野である。
ディリクレ指標と解析数論
オイラーにより、素数を亙るある無限積が単位円の面積の平方の1⁄6（つまり、π2/6）に等しいことが発見され、数の理解に対する新たなアプローチの仕方が生まれた。ディリクレはこれを用いて整数の合同類環の単数群が素数を無限に含むことを示した。今日ではこれはディリクレの算術級数定理と呼ばれる。
この証明を得るためにディリクレはディリクレの L-級数という特別な道具を発明した。その一つは有名なリーマンゼータ函数に対応するものである。証明においてもっとも困難であったのは、この函数が点 1 に根を持たないことであった。そのためにディリクレは合同類環の単数群上で調和解析を用いた[26]。
ここでもやはり、合同算術は定理に至るには不十分であり、ディリクレは整級数や複素解析など種々の解析的手法を用いている。そうして新たな数学の分野である、解析数論が生まれた。解析数論の重要な通過点がベルンハルト・リーマンの一つの論文 Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse（「与えられた数より小さい素数の個数について」）によってもたらされる。リーマンはゼータ函数の根の位置に関する予想を提示した。ディリクレによってはじめられた根の位置の研究は、この分野の中心的な関心となり、現代の数学においても最も解決の難しい予想の一つとして残されている[27]。
暗号理論
非対称暗号
対称暗号
素数判定
積の素因数分解
秘匿による安全性は、RSA暗号には及ばない。重要なことは、整数の素因数への分解の様子を明確に知ることである。RSA Factoring Challengeと呼ばれる、公開されたリストにある整数を選んで因数分解できたものを表彰するコンペが、2007年5月まで開かれた。
エラトステネスの篩は分解の方法を与える素数判定法であるが、しかし巨大な整数には時間が掛かり過ぎて適用できない[28].
現在では平方剰余に基づく別な方法がしばしば用いられる[29]。少なくとも二つの完全平方数を代表元に含む平方剰余が零因子になり、その二つの平方数を求めることが目標となる。このような方法が二次篩法および一般数体篩法であり、後者は2007年時点で最速である[30]。また、ポラードの ρ アルゴリズムは誕生日のパラドクスに用いられる。
有限体
素数による商体 ℤ/pℤ の構成は他の構造へ一般化される。情報処理において、数は n ビットでコードされる（つまり、数は 0 と 1 からなる長さ n の数列に対応する）。それは二元体 F2 上の n-次元ベクトル空間のベクトルと見なすことができる。この構造はしばしば F2 に係数を持つ次数が m より真に小さい多項式全体の成す空間と見なされる。乗法について閉じているためには、この空間は次数 n の適当な多項式 f で割られなければならない。その多項式 f が既約（素数に対応するもの）であるとき、得られる構造は位数 2n の有限体になる。数 a modulo 2n と多項式 P modulo f はよく似ており、事実 のように書ける。
用例の一つは F2 上の疑似乱数生成器である。そのような生成器は例えば携帯電話での音声通信の文脈でストリーム暗号[31] A5/1 によって使われる。これは線形帰還シフトレジスタ (LFSR) の後ろの成分を持つ。F2 の元の長さ n の二つの有限列として、係数列および初期化列が で与えられるとき、LFSRは疑似乱数列 (uj) を線形回帰数列 によって得る。係数列はしばしば固定される。ゆえに鍵は、整数 a modulo 2n で表される初期化列 を与える。得られた結果は周期的だが、係数列を適切に選べば周期は 2n – 1 と非常に長くなる。この状況は、 で与えられる「帰還多項式」R が巡回群 (F2n)* の生成元の最小多項式であるときに生じる。
有限アーベル群上の調和解析
誤り訂正符号
チェックサム
巡回符号
マクウィリアムス恒等式
脚注
参考文献
関連項目
外部リンク
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
