合同算術のソースを表示

[[Image:Disqvisitiones-800.jpg|thumb|180px|[[カール・フリードリヒ・ガウス|ガウス]]の "''[[Disquisitiones Arithmeticae]]''"（『算術の研究/整数論』）]]
[[数学]]、特に初等[[代数的整数論]]における'''合同算術'''（ごうどうさんじゅつ、{{lang-en-short|''modular arithmetic''}}; モジュラ計算）は、（[[ユークリッド除法|剰余を持つ除法]]の意味で））自然数あるいは整数をある特定の自然数で割ったときの剰余に注目して、自然数あるいは整数に関する問題を解決する一連の方法の総称である。合同算術の起源は、一般には[[カール・フリードリヒ・ガウス|ガウス]]が著作『[[Disquisitiones Arithmeticae]]』を出版する[[1801年]]にまで遡れるものとされる。ガウスによる[[整数の合同|合同]]を用いたこの新しい手法は、有名な[[平方剰余の相互法則]]を明らかにし、より抽象的な観点から[[ウィルソンの定理]]などの定理の記述の簡素化に一役を買った{{efn|ガウスは、合同式という記号の偉力について、「この計算法を身につけた人なら（中略）全く天才でさえ途方にくれるようなこみ入った場合にも機械的に問題が解ける」と述べている<ref>{{cite book|和書|author=遠山啓|authorlink=遠山啓|title=数学入門|volume=下|page=12|year=1960|series=岩波新書|isbn=4-00-416005-7}}</ref>。}}。ガウスの研究は自然数を扱う整数論のみならず、代数学や幾何学といった数学のほかの主要な分野にまで影響を与えるものであった。

[[file:Clock_group.svg|thumb|right|180px|かんたんな時刻の計算は「時間」については 12 あるいは 24 を法とする、「分・秒」については 60 を法とする合同算術になっている。合同算術はあたかも法 ''n'' を「[[周期]]」として循環あるいは回転しているかのようである。]]
この手法の基本は、「数それ自体」ではなくそれを別な数で割った（商がいくらになるかということは無視して）「剰余だけ」を考えるということにある。こういった考え方は何か特殊で高尚なものというようなものではなく、実際に日常生活においても時刻や角度といったものの計算や単位の換算などで、ちょっとした合同算術が特別な知識無くあるいは無意識に行われているのである。

20世紀には、合同算術にまつわる状況は大きく様変わりをしている。[[計算機]]や[[ウェブ]]の普及に伴って[[情報セキュリティ]]の観点からの[[公開鍵暗号|暗号化アルゴリズム]]の開発や取り扱いといったような場面で古典的な合同算術に関する理論の工業的・商業的応用が頻繁に見られるようになった。
<!--
== 用例 ==
{{section à recycler}}
En [[mathématiques pures]], ce terme est très peu utilisé. La ''[[théorie algébrique des nombres]]'' désignant un domaine beaucoup plus large contenant par exemple les notions d'[[entier algébrique|entiers algébriques]]<ref>{{Samuel1}}.</ref> et de [[théorie de Galois]]<ref>{{en}} {{Lien|Albert Fröhlich}}, ''Galois Module structure of Algebraic integers'', Springer-Verlag, Berlin, 1983.</ref>.

En [[mathématiques appliquées]], cette expression est d'un usage fréquent pour décrire les bases mathématiques de différents domaines de la [[théorie de l'information]] : [[cryptologie]], [[théorie des codes]] et [[informatique]]. De nombreux outils et [[Algorithmique|algorithmes]] entrent dans ce champ d'étude. Parmi les [[test de primalité|tests de primalité]] les plus utilisés<ref>Chantal David, ''[http://www.mathstat.concordia.ca/faculty/cdavid/TALKS/crypto.pdf Cryptographie à clé publique et factorisation]'', [[Université Concordia]], p. 11-17.</ref>, l'utilisation des [[caractère de Dirichlet|caractères d'un groupe]] par exemple pour la [[transformée de Fourier discrète]]<ref>J.-M. Muller et J.-C. Bajard, ''[http://perso.ens-lyon.fr/jean-michel.muller/ExtraitsTraiteIC2.pdf Calcul et arithmétique des ordinateurs]'', Traité Hermes CNRS 2004, p. 142-150 et 181-201.</ref>.

Selon les différents auteurs et le domaine d'application, ces extensions sont considérées, soit comme une partie intégrante de l'arithmétique modulaire{{refnec}}, soit comme des applications, voire ne sont pas citées du tout. Sous sa forme simple, elle prend parfois le nom d'''arithmétique de l'horloge''{{sfn|Singh|2001|p=324-329}}.

Les [[système modulaire de représentation|systèmes modulaires de représentation]] {{en}} (Residue number system, RNS en abrégé), des représentations des entiers fondée sur le [[théorème des restes chinois]], sont utilisés pour accélérer les opérations de l'arithmétique modulaire<ref>{{Chapitre|lang=en|prénom=Pascal|nom1=Paillier|titre=Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor|titre ouvrage=Proceedings PKC'99|collection=Lecture Notes in Computer Science|numéro dans collection=1560|éditeur=Springer|année=1999|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.9930}}.</ref>.
-->

== 歴史 ==
=== ヨーロッパの怪物 ===
[[Image:Pierre de Fermat.jpg|thumb|180px|right|[[ピエール・ド・フェルマー]]は[[算術]]を発展させた。合同算術の基礎となる剰余をもつ除法は、フェルマーによって既に用いられていた。]]

1621年、[[クロード＝ガスパール・バシェ・ド・メジリアク]] <small>(1581 - 1638)</small> は[[アレクサンドリアのディオファントス|ディオファントス]]の本『[[算術 (書物)|算術]]』をラテン語に翻訳し、そこに書かれていた問題について当時の（特にフランスの）数学者が興味を持つこととなる。[[ピエール・ド・フェルマー]] <small>(1607 - 1665)</small> は多数の定理を残したが、中でも有名なものは[[フェルマーの最終定理|大定理]]、[[二個の平方数の和|二平方和定理]]、[[フェルマーの小定理|小定理]]の3つであろう。科学コミュニティがこの話題にこぞって取り組むなか、フェルマーは「平方数の和で立方数となるものを求めよ」という問いを発し、{{lang|fr|« 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 »}}（“この問いが解決されることを望む。それがイングランド人でもガリア・ベルギー人でもケルト民でもなく、フランス・ナルボンヌの人の手で為されることを。”）と結んでいる<ref>[[ピエール・ド・フェルマー|Pierre de Fermat]] ''Correspondance'' 3 janvier 1657</ref>。

[[マラン・メルセンヌ]] <small>(1588 - 1648)</small> は今日[[メルセンヌ素数]]と呼ばれる素数について研究した。フェルマーはメルセンヌに {{lang|fr|« 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, ... が素数であるとする基本的理由を正しいとするならば、このことについて、いくつかの素敵なことを見つけることができるように思えます。なぜなら、私はすでにいくつかの素晴らしいことを見つけているからです。その私が見つけた素晴らしいことをあなたと共有しましょう。”）と言っている<ref>Pierre de Fermat ''Correspondance'' Marin de Mersenne 25 Décembre 1640</ref>が、これらの数は今では[[フェルマー数]]と呼ばれ、フェルマーの言っていたこれらが全て素数となるだろうという予想は偽であることが知られている。[[ルネ・デカルト]] <small>(1596 - 1650)</small> はそれらとは独立に研究を進め、[[素数]]の 8 を法とする剰余が 1 または 3 ならば、その素数は ''x''<sup>2</sup> + 2''y''<sup>2</sup> の形に書けるということを示した

この手の問題については興味深い要素がふたつあった。

: 人々がディオファントス方程式にいかに心奪われたかということは、バシェ・ド・メジリアクの本の一つの表題が "''Problèmes plaisants et délectables qui se font par les nombres''"（『数それ自身の成す喜ばしくもほほえましい問題』）であるということや、フェルマーが大定理について {{lang|fr|« J'ai trouvé une solution merveilleuse ... »}}（“驚くべき証明を発見した……”）と書き残している<ref>Pierre de Fermat ''Remarques sur Diophante'' par Pierre Samuel fils de Fermat 1670</ref>ことなどにも顕れている。

: 簡単そうな問題が意外に難しい。おそらくバシェ・ド・メジリアクの手によって[[ベズーの等式]]のいくつかはうまく解かれたけれども、問題の本質的な部分に答えるようなものではなかったし、フェルマーの二平方和定理にしても答えをほとんど誰も理解できないもので、フェルマーの最終定理にしてもフェルマー自身が {{lang|fr|« ... mais la place me manque ici pour la développer »}}（“……しかしこの余白はそれを記すには狭すぎる”）という書き込みを残したのみであった（はじめてきちんとした証明が現れるのは1994年と1995年である<ref>[[アンドリュー・ワイルズ|Andrew Wiles]] ''[http://math.stanford.edu/~lekheng/flt/wiles.pdf Modular elliptic curves and Fermat's last theorem],'' Annals of Mathematics ('''141''') (3), 443-551 (1995)</ref>)）。フェルマーはしばしば自身の失敗を自白するコメント {{lang|fr|« 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... »}}（“わたしは極めてはっきりと告白しますよ（私が前もって言っていたように、自分で知っていることしか、私がやったとは言えませんから。また、私が何を知らないのかも、同じように正直に言いましょう）、この美しき命題を私はまだ証明できていない、と。その命題をあなたに送ります”）で彼の定理を締めくくっている<ref>Pierre de Fermat ''Correspondance à Frénicle de Bessy'' 18 octobre 1640</ref>。

=== 18世紀の数学 ===
[[Image:Leonhard Euler 2.jpg|thumb|right|180px|18世紀の数論家[[レオンハルト・オイラー]]はいくつも[[ディオファントス方程式|整数問題]]を解いている。]]

フェルマー問題のいくつかは、続く18世紀に、大部分は[[レオンハルト・オイラー|オイラー]]の手で解かれていった。オイラーは二平方和問題の証明の過程で、いわゆる[[フェルマー数]]が常に[[フェルマー素数|素数]]となるわけではないことを示した<ref>[[レオンハルト・オイラー|Leonhard Euler]] ''Correspondance'' à Goldbach 12 avril 1749</ref>。そういった成功とともに、オイラーはいくつかの誤りも犯しており、フェルマーの大定理の ''n'' = 3 の場合の証明に失敗している（彼の最初の証明<ref>Leonhard Euler ''Algèbre'' 1770</ref>は誤りである）。1782年には、新たな問題として[[平方剰余の相互法則]]が俎上に上がることになる。そして、[[アドリアン＝マリ・ルジャンドル]] <small>(1752 - 1833)</small> により残りの問題も精力的に解かれていった<ref>[[アドリアン＝マリ・ルジャンドル|Adrien-Marie Legendre]] ''Théorie des nombres'', Paris Duprat 1798</ref>。

19世紀の初頭には、それまで数学者が用いていた大仕掛けな道具立て（手法や表記法）も、単純な原理を導入することによって徐々に必要なくなっていった。「二つの平方数の和で 4 を法とする剰余が 3 であるようなものは存在するか」という有名な 3 に対する二平方和問題を例に取ろう。証明の内容としては「''a''<sup>2</sup> および ''b''<sup>2</sup> を二つの平方数とする。''a'', ''b'' ともに偶数であるかともに奇数であればそれらの和の 4 を法とする剰余は 0 か 2 である。''a'' が偶数で ''b'' が奇数とすると、偶数 ''a'' の平方は 4 の倍数であり、奇数 ''b'' は ''b'' = 2''c'' + 1 と表せて、その平方は 4''c''<sup>2</sup> + 4''c'' + 1 となるので、''b''<sup>2</sup> の 4 を法とする剰余は 1 となり、したがって所期の平方和の 4 を法とする剰余は 1 であるとわかる」といった感じであるが、ここでいくつかの道具立てが用いられている。

* 一つ目の道具は、ちょうどふたつの因数を持つものとしての素数である。
* 二つ目は、''b'' を 2''c'' + 1 と表すような「文字の置換え」である。適切に置換える文字を選ぶことによって、数学者はいくつもの整数問題を解決することができた。
* 三つ目は「[[除法の原理]]」であり、これによって平方や平方和を 4 で割ることが機械的・系統的に行える。
* 四つ目は例示には表れていないが、二平方和定理のオイラーによる証明に用いられた[[無限降下法]]である。これは「自然数解が在れば必ずそれよりも小さな自然数解があることを示すことで、そのような自然数解の存在が繰り返し示され、自然数からなる無限降下列が構成されることになるが、このようなことは不可能である」というものである。これは[[フェルマーの大定理]]の ''n'' = 4 の場合を証明するのに利用されている。

オイラーによる二平方和定理の証明にしたところで、古い伝統的な道具立てでは証明は長く技巧的なものにならざるを得ず、そのような方法では1世紀以上の努力を費やしてもフェルマーの整数問題を解決することはできなかったのである。

=== ガウスの貢献 ===
[[file:Carl_Friedrich_Gauss.jpg|thumb|right|180px|合同算術の祖ガウス]]
17歳の[[カール・フリードリヒ・ガウス|ガウス]] <small>(1777 - 1855)</small> は[[平方剰余の相互法則]]を示した。翌1796年3月30日、ガウスは17次の[[円分多項式|円分方程式]]を解くというきわめて算術的な研究の過程で、古来から未解決の幾何学的問題であった[[定規とコンパスによる作図|定規とコンパスによる]][[正十七角形]]の作図が可能であることに気付く。最終的に1801年、ガウスは "''[[Disquisitiones Arithmeticae]]''"（『算術の研究』）を著して'''数学王子'''と渾名された<ref>Patrice Naudin, Claude Quitté, ''Algorithmique algébrique'' Masson 1992</ref>。

これら二つの大きな発見は共に、フェルマーやオイラーが用いたような道具よりもより抽象的で明確な道具を用いて、証明に掛かる大きな負担を軽減するという過程のなかで為されており、その過程は合同算術として結実する。

ガウスは整数係数多項式をつかって整数概念の拡張を行い、今日では[[ガウス整数]]と呼ばれる数の集合を得ている。[[ペーター・グスタフ・ディリクレ|ディリクレ]] <small>(1805 - 1859)</small> も類似の整数の集合を発見しており（それは[[ディリクレ整数]]と呼ばれる）、それを足がかりとして[[フェルマーの大定理]]の ''n'' = 5 の場合を証明した。その論文は1825年に[[フランス科学アカデミー|科学アカデミー]]に提出され、ルジャンドルの数ヶ月に亘る査読を受けた後に受理されている<ref>[[ペーター・グスタフ・ディリクレ|Dirichlet]] ''Démonstration du théorème de Fermat et de Wilson'' (compte-rendu par Cournot de quelques mémoires d'Abel, Jacobi et Lejeune-Dirichlet, au Journ. der Mathemat., de M. Crelle, t. 3, cah. 4). 1829, t. 11, p. 153-157</ref>

そのころフェルマーの整数問題は、最終定理を除くすべてが解決されていたが、新しい予想も現われていた。たとえば、''a'' と ''b'' が[[互いに素 (整数論)|互いに素]]ならば初項 ''a'' で公差が ''b'' の[[等差数列]]のなかに素数は存在するか、存在するとしたらどのくらい含まれるか、というものである。ガウスやルジャンドルらの数学者は無限に存在するだろうと考えたが、平方剰余の相互法則と同様の高次の冪剰余に対する相互法則が必要であり、証明はできなかった。

その後も合同算術は発展を続け、ディリクレは[[ディリクレ指標]]の概念や[[解析的整数論|解析数論]]の基礎を固めることによって[[算術級数定理]]を証明した<ref>Dirichlet ''Recherches de diverses applications de l'analyse infinitésimale à la théorie des nombres'' J. Reine Angew math. (19) 1839 ibid (21) 1840</ref>。その証明は合同算術の珠玉ともいえるもので、[[カール・グスタフ・ヤコブ・ヤコビ|ヤコビ]] <small>(1804 - 1851)</small> は兄弟への手紙に {{quote|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.（フーリエ級数を数論に応用することで、ディリクレは人類の洞察力の頂点に到達するような結果を見出した）}}と記している<ref>W. Ahrens ''Briefwechsel zwischen C. G. J. Jacobi und M. H. Jacobi'' The Mathematical Gazette, Vol. 4, No. 71 pp. 269-270, 1908</ref>。今では[[有限可換群上の調和解析]]から得られる道具を用いて証明することができるが、ルジャンドルはそういった道具は用いておらず、今では[[ルジャンドル記号]]と呼ばれる概念を定式化することにより、[[平方剰余の相互法則]]と同様の計算を[[実数]]に対して行うことで証明した<ref>[[アドリアン＝マリ・ルジャンドル|Adrien-Marie Legendre]] ''Essai sur la théorie des nombres'', Duprat, Paris 1798</ref>。ガウスは1801年の著書で最終的にこの方法を[[複素数]]にまで拡張した。この計算は [[ガウス和]]と[[ガウス周期]]と呼ばれる。

19世紀にはこれらの数学は'''超越数論'''<ref>[[フェルディナンド・アイゼンシュタイン|Ferdinand Eisenstein]] ''Application de l'Algèbre à l'Arithmétique transcendante'', Journal de Crelle. Berlin 1845</ref>と呼ばれ、[[算術]] (arithmetic) という呼称もより一般の数学を指す言葉として残ったが、1830年にルジャンドルは、この十分に発展を遂げた分野を表すため、[[数論]] (theory of numbers) <ref>Adrien-Marie Legendre ''Théorie des nombres'', Firmin Didot 3<sup>e</sup> édition, 1830</ref>という呼称を考案した。ガウスのころの算術とは異なる新しい手法が用いられるようになり、[[代数的整数論|代数的整数-論]]と[[解析的整数論|解析的-数論]]という分科が現れるようになると、[[超越数]]の登場もあって、超越数論という呼称は過去のものとなっていった。

=== 20世紀の合同算術 ===
==== 暗号理論 ====
{{main|暗号理論}}
<!--
[[Image:Kerkhoffs.jpg|left|thumb|[[Auguste Kerckhoffs]] énonce un principe fondateur de la [[cryptologie]] moderne.]]
[[Image:Enigma.jpg|thumb|''[[Enigma (machine)|Enigma]]'', une machine de chiffrement utilisée durant la [[Seconde Guerre mondiale]], décrypté par un [[mathématicien]] : [[Marian Rejewski]].]]
Ce domaine quitte celui des mathématiques pures. En revanche, une application industrielle fait, au cours du temps, de plus en plus appel aux notions mathématiques développées par Gauss : la science des codes secrets appelée [[cryptologie]]. En [[1883 en science|1883]], [[Auguste Kerckhoffs]] énonce que : {{Citation|la sécurité d'un système de cryptographie ne doit pas reposer sur le secret de l'[[Algorithmique|algorithme]]. La sécurité ne repose que sur le secret de la [[Clé de chiffrement|clé]]}}<ref>{{cite journal|first=A.|last=Kerckhoffs|title=La cryptographie militaire|journal=Journal des sciences militaires|volume=IX|year=1883|p.=5-83 et 161-191|url=http://www.petitcolas.net/fabien/kerckhoffs}}.</ref>. Cette approche est à l'origine d'une modification profonde de cette science. Au milieu du {{s-|XX}}, elle devient une branche des [[mathématiques appliquées]]<ref>{{cite journal|authorlink=Claude Shannon|first=C.|last=Shannon|url=http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|title={{仮リンク|Communication Theory of Secrecy Systems|en|Communication Theory of Secrecy Systems}}|journal=Bell System Technical Journal|volume=28|year=1949|p.=656-715}}.</ref>.

Au début des [[années 1930]], le bureau du chiffre polonais fait appel au mathématicien [[Marian Rejewski]] pour [[cryptanalyse d'Enigma|percer]] le code du système [[Enigma (machine)|Enigma]], utilisé par les Allemands. Les anciens codes, comme le [[chiffre de César]], sont réinterprétés comme une transformation mathématique dans l'ensemble des moduli de Gauss sur les nombres entiers. Le terme d'« arithmétique modulaire »<ref>Alain Tapp, ''Cryptographie'', Laboratoire d’informatique théorique et quantique de l'[[université de Montréal]].<--lien apparemment mort le 17/04/11 : http://www.iro.umontreal.ca/~tappa/IFT6155/cryptographie.pdf--</ref>  est utilisé pour décrire ces techniques. Durant les [[années 1970]], [[Horst Feistel]] développe<ref>{{cite journal|language=en|first=H.|last=Feistel|url=http://archive.wikiwix.com/cache/?url=http://www3.edgenet.net/dcowley/docs.html&title=lire|title=Cryptography and Computer Privacy|journal= [[Scientific American]]|volume=228|issue=5|year=1973}}.</ref> un système à [[Cryptographie symétrique|clé privée]], le [[Data Encryption Standard]] ou DES, qui devient le standard des applications non classifiées<ref>{{citation|language=en|authorlink=Don Coppersmith|first=Don|last=Coppersmith|url=http://archive.wikiwix.com/cache/?url=http://www.research.ibm.com/journal/rd/383/coppersmith.pdf&title=lire|title=The data encryption standard (DES) and its strength against attacks|journal=IBM Journal of Research and Development|volume=38|issue=3|year=1994|pages=243-250}}.</ref>. Les [[cryptanalyse|cryptanalystes]] du DES, et plus généralement des [[Cryptographie symétrique|chiffrements symétriques]], utiliseront des mathématiques issues des travaux de Dirichlet sur les [[Caractère de Dirichlet|caractères]], dans le cadre d'un [[espace vectoriel]] sur un [[corps fini]] à deux éléments.

En [[1976 en science|1976]] une nouvelle famille de codes est découverte<ref name="DiffieHellman">{{cite journal|language=en|author1-link=Whitfield Diffie|first1=Whitfield|last1=Diffie|authrr2-link=Martin Hellman|first2=Martin|last2=Hellman|url=http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/diffie-hellman.pdf|title=New directions in cryptography|journal=IEEE Trans. Inf. Theory|volume=22|issue=6|year=1976|pages=644-654}}.</ref>, fondée sur une [[Cryptographie asymétrique|clé publique]]. Des solutions industrielles sont rapidement développées, la plus célèbre est dénommée [[Rivest Shamir Adleman|R.S.A.]]<ref>{{cite journal|language=en|author1-link=Ronald Rivest|last1=Rivest|author2-link=Adi Shamir|last2=Shamir|author3-link=Leonard Adleman|last3=Adleman|url=http://people.csail.mit.edu/rivest/Rsapaper.pdf|title=A Method for Obtaining Digital Signatures and Public-Key Cryptosystems|journal= [[Communications of the ACM]]|volume=21|issue=2|year=1978|pages=120-126}}.</ref>. Elle se fonde sur les travaux de Fermat et d'Euler. Le terme« arithmétique modulaire » est, dans ce contexte, utilisé pour décrire<ref>Laurent Bloch, ''Les systèmes d'exploitation des ordinateurs. Histoire, fonctionnement, enjeux'', Vuibert, 2003 {{ISBN2|978-2-7117-5322-2}}.</ref> non seulement la structure des moduli sur les entiers, mais aussi les théorèmes traitant des nombres premiers comme la [[décomposition en produit de facteurs premiers]], le [[Théorème des restes chinois|théorème chinois]], le [[petit théorème de Fermat]] et sa [[Théorème d'Euler (nombres)|généralisation]] par Euler.

Avec le développement de l'[[informatique]], l'arithmétique modulaire devient un domaine de recherche actif : les applications nécessitent l'utilisation d'opérations sur des grands nombres, et la mise en œuvre d'algorithmes efficaces<ref>Par exemple Thomas Plantard, ''[http://tel.archives-ouvertes.fr/docs/00/11/21/21/PDF/plantard.pdf Arithmétique modulaire pour la cryptographie]'', thèse de l'[[université Montpellier 2]], 2005.</ref>.
-->
==== 情報理論 ====
{{main|情報理論}}
<!--
[[Image:P-MMX.JPG|right|thumb|Un [[Processeur]] [[Pentium (microprocesseur)|Pentium]] contenant une [[unité arithmétique et logique]] fondée sur l'arithmétique modulaire.]]
La cryptographie n'est pas l'unique domaine utilisant le vocable« arithmétique modulaire ». La fin de la [[Seconde Guerre mondiale]] voit l'apparition d'une nouvelle science : la [[théorie de l'information]]. En  [[1948 en science|1948]], sous l'impulsion de [[Claude Shannon]], elle devient<ref>{{cite journal|language=en|last=Shannon|title=A Mathematical Theory of Communications|journal=Bell Syst. Tech. J.|volume=27|year=1948|pages=379-423 et 623-656}}.</ref> une branche des [[mathématiques appliquées]].

Si la [[confidentialité]] est l'un des sujets abordés, la fiabilité est aussi un thème majeur. [[Richard Hamming]] propose un premier [[Algorithmique|algorithme]]<ref>{{cite journal|language=en|first=R.|last=Hamming|title=Error Detecting and Correcting Codes|journal=Bell Syst. Tech. J.|volume=29|year=1950|pages=150-163}}.</ref> dès [[1950 en science|1950]]. Une fois encore, les moduli sur les entiers sont utilisés pour une des plus simples techniques de code : les [[somme de contrôle|sommes de contrôle]]. En [[1960 en science|1960]], de [[code cyclique|nouveaux codes]] plus puissants sont développés<ref>{{cite journal|language=en|author1={{仮リンク|Raj Chandra Bose|de|Raj Chandra Bose}}|author2={{仮リンク|D. K. Ray-Chaudhuri|en|D. K. Ray-Chaudhuri}}|title=On a class of error-correcting. Binary group codes|journal=Inform. Control|volume=3|year=1960|pages=68-79}}.</ref>, sur la base de polynômes à coefficients dans un corps fini. L'arithmétique utilisée prend souvent le nom de« modulaire »<ref>Jacques Vélu, ''Méthodes mathématiques pour l'informatique'', Dunod informatique, 1987.</ref>.

L'informatique devient un sujet<ref name="Denning_cs_discipline">{{Chapitre|lang=en|nom1={{Lien|Peter J. Denning}}|année=2000|titre=Computer Science: The Discipline|url=https://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf|titre ouvrage=Encyclopedia of Computer Science}}.</ref> universitaire au début des [[années 1960]]. Les contraintes inhérentes à la structure des [[processeur]]s imposent la représentation des nombres sous forme d'une suite finie d'informations, justifiant l'utilisation des moduli. Le terme d'« arithmétique modulaire » apparaît souvent<ref>Jean Berstel, Jean-Éric Pin et Michel Pocchiola, ''Mathématiques et informatique : exercices résolus, vol. 2'', [[McGraw-Hill]] France, 1991.</ref>, on y trouve même les [[entier de Gauss|entiers de Gauss]] ou les polynômes, par exemple, pour des calculs sur des grands entiers.

Les techniques développées pour la cryptographie, la théorie des codes et l'arithmétique informatique reposent sur les mêmes concepts, offrant une relative unité aux mathématiques de la théorie de l'information.
-->

== 合同算術の道具立て ==
=== 整数の合同 ===
{{main|整数の合同}}
「合同算術」の歴史的な例は[[整数]]に基づくものである。一つの自然数 {{mvar|n}} を固定して「法 {{mvar|n}} で考える (modulo {{mvar|n}})」とは、任意の整数をそれを {{mvar|n}} で[[ユークリッド除法|割った]]剰余と同一視するものである。例えば {{math|1= ''n'' = 12}} のときは時計算として詳しく知られるものになる。これは 12 時間だけことなる時刻において時針は同じ位置にあるということと理解すれば、例えば 13 時間と 1 時間は同一視される。そのような集合上で算術を行うには、その加法および乗法が上記のような同一視と両立することを確かめねばならない。そうしてルジャンドル<ref>Legendre, ''Recherches d'Analyse Indéterminée'' dans ''Hist. Acad. Roy. des Sciences'' (1785/1788).</ref>によって「剰余」を数とは異なる対象を与えるものして定式化された。

ガウスの貢献はこの集合、今日[[整数]]の[[整数の合同|合同類]] の[[単位的環|環]] [[剰余類環|{{math|ℤ/''n''ℤ}}]] と呼ばれる[[代数系]]、の構造を詳らかにするものであった。第一に加法に関して考えれば、これは {{math|[[1]]}} を生成元とする[[巡回群]]を定める。第二に乗法に関しては、これは法 {{mvar|n}} に依存して性質が異なり、法 {{mvar|n}} が[[素数]]ならば[[可換体|体]]が得られる。このような方法により、計算の記述は簡素化される。その歴史的な例が、ガウスの著書 ''[[Disquisitiones Arithmeticae]]'' に載っている[[ウィルソンの定理]]{{sfn|Gauss|1801|p=56}}および[[フェルマーの小定理]]{{sfn|Gauss|1801|p=34}}である。

法 {{mvar|n}} が素数でない場合の合同算術はより複雑なものとなるが、その構造を明らかにするのに[[中国の剰余定理]]が利用できる。この場合の合同類環は[[整域]]を成さず、[[零因子]]（それ自身は非零だが、ほかの非零元に掛けると零になる元）が存在する。この環における可逆元の数は[[オイラーのφ函数|オイラー数]] {{math|φ(''n'')}} で与えられ、例えば[[オイラーの定理 (数論)|一般化されたフェルマーの小定理]]が成り立つ。

=== 多項式の割り算 ===
{{main|円分多項式}}
[[Image:Heptadecagone.jpg|thumb|right|[[正十七角形]]の[[定規とコンパスによる作図|作図]]を示した図。合同算術の手法を強調するものである。]]
ガウスは[[有理数|有理]]係数多項式の集合にも（そこでは加法、乗法および[[ユークリッド除法]]ができるから）合同算術の論理を持ち込めることを指摘している。多項式の合同は、特定の多項式によって多項式を割った剰余によって与えられる。

ガウスはそのような方法論を[[円分多項式]]と呼ばれる多項式 {{math|''X{{exp|n}}''– 1}} に適用してその[[多項式の因数分解|既約元分解]]を得ている。またガウスはその結果を以って[[正十七角形]]の[[定規とコンパスによる作図]]を発見した。

ガウスはこれらの業績を算術と看做すことを躊躇っており、{{quotation|« 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 »{{sfn|Gauss|1801|p=XV}}.（訳:「この円あるいは正多角形の分割理論は……「それ自身」は算術ではない、が「その原理」は超越的な算術に拠ってしか描くことはできない」）}}と記している。この論法の論理は今日も有効である。

=== 代数的整数 ===
{{main|ガウス整数}}
整係数多項式の場合は少し事情が異なり、除法がうまく行くには最高次係数が {{math|&plusmn;1}} でなければならない。多項式 {{math|''X''<sup>2</sup> + 1}} を法とする算術を考えれば、その商構造はやはり環を成し、整数 {{math|α, β}} と[[虚数単位]] {{mvar|i}} に対して {{math|α + ''i''β}} の形に書ける数全体の成す集合と同一視することができる（{{mvar|i}} と単項式 {{mvar|X}} が対応する）。このような数の集合は'''ガウスの整数'''環である。

[[Image:Entier de Gauss division.jpg|thumb|right|[[ガウス整数]]環における[[ユークリッド除法]]の視覚的説明]]
[[Image:Fermat deux carrés.jpg|thumb|left|ガウス整数環における[[フェルマーの二平方和定理]]の視覚的説明]]

ガウス整数環は[[合成代数|ノルム]]を考えることができる。ガウス整数 {{math|1= ''a'' = α + {{mvar|i}}β}} には（[[複素数の絶対値]]から導かれる）ノルム {{math|α<sup>2</sup> + β<sup>2</sup>}} が割り当てられる。このノルムを用いて（右図のように）[[ユークリッド除法]]が定義できる。ガウス整数はガウス平面上の（成分が整数の）格子点として表すことができることに注意する。ガウス整数 {{mvar|a, b}} の複素数としての商 {{mvar|{{fraction|a|b}}}} は {{mvar|b}} が非零ならば存在するが、それは必ずしもガウス整数ではない。ユークリッド除法が可能であるというのは、{{mvar|{{fraction|a|b}}}} との差のノルムが最小となるガウス整数がただ一つ存在するということである（右図ではその候補が少なくとも三点、一般には一点から四点の候補が考えられる）。

ユークリッド除法が可能であることからこの整数環の性質がいくつか導かれる（[[ベズーの等式]]、[[ガウス素数]]の存在、および[[算術の基本定理|素因数分解の一意性]]などを挙げることができる）。ガウス素数を用いて[[リヒャルト・デーデキント|デテキント]]は[[フェルマーの二平方和定理]]の平易な証明を与えている（左図はそれを視覚的に示したもの）。[[素数]] {{mvar|p}} が二つの平方の和に表すことができるのは、{{mvar|p}} の平方根を半径とする単位円が少なくとも一つのガウス整数と交わるときである。

[[ゴットホルト・アイゼンシュタイン]]は1844年にガウスと邂逅し<ref>Voir par exemple {{MacTutor|id=Eisenstein|title=Ferdinand Gotthold Max Eisenstein}}</ref>、[[アイゼンシュタイン整数|新たな整数環]]を発見している<ref>{{en}} [[André Weil]], ''Elliptic Functions according to Eisenstein and Kronecker'', Springer, 1999 {{ISBN2|978-354065036-2}}</ref>。アイゼンシュタインの整数環の算術は[[フェルマーの最終定理]]の {{math|1= ''n'' = 3}} の場合の厳密な証明に利用できる。そういった意味合いからも、このような一般化された合同算術の理論の必要性が正当化される。

=== ディリクレ指標 ===
{{main|ディリクレ指標}}
[[Image:Dirichlet.jpg|thumb|right|[[ペーター・グスタフ・ディリクレ|ディリクレ]]は[[剰余類環]] {{math|ℤ/''n''ℤ}} の文脈における本質な理論を確立した。]]

ディリクレは[[互いに素 (整数論)|互いに素]]な整数 {{mvar|n, m}} と正整数を亙る変数 {{mvar|λ}} に対して {{math|''n'' + λ''m''}} の形に書ける数について注目し、このような数の世界における素数が実際に無数に存在することを示そうと試みた。そのような問題に対して合同算術は有効な道具であり、それはつまり剰余類における素数全体の成す集合の[[濃度 (数学)|濃度]]を知ることに同じである。

ディリクレは、法 {{mvar|m}} に関して[[可逆元|可逆な元]]全体の成す[[群 (数学)|群]]（環 {{math|ℤ/''m''ℤ}} の[[単元群]]、つまり既約合同類群 {{math|(ℤ/''m''ℤ){{msup|×}}}}）を考え、その群から非零[[複素数]]全体の成す乗法群への[[群準同型]]（すなわち、群の元 {{mvar|a, b}} に対して {{math|1= ''f''(''ab'') = ''f''(''a'')''f''(''b'')}} を満たす写像）全体の成す集合について調べた。このような写像をディリクレ指標という。ディリクレ指標は {{math|φ(''n'')}} 個存在し、二つの指標の積はまた一つの指標であり、乗積表を書けばそれは既約合同類群のものと[[同型|全く同じ]]になる。

このような写像を計算することは[[ジョゼフ・フーリエ|フーリエ]]が先駆的に為した仕事の形式的なアナロジーであった<ref>{{cite journal|first=Jean Baptiste Joseph|last=Fourier|title=Mémoire sur la propagation de la Chaleur dans les corps solides|journal=Nouveau Bulletin des sciences par la Société philomathique de Paris|volume=6|year=1807|pages=112-116}}</ref>。にも拘らず、これら二つのやり方を統一する理論（それは[[調和解析]]と呼ばれる）の登場は20世紀を待たねばならない。

== 理論の展開 ==
数学において、ある文脈で発展した概念がまた別の領域で再利用されることは常であり、例えば[[群論]]は[[算術]]や[[幾何学]]に応用される。それは合同算術の道具についても同じであり、これらの道具は[[抽象代数学]]や[[ガロワ理論]]などを含む[[純粋数学]]の広汎な分野において影響を与えた。これらの理論は、もはや合同算術の特別の場合とは考えられることがないほどに、合同算術には無い多くの概念を含んでいる。

=== 商構造 ===
{{main|同値関係}}
現代的な言葉で言えば、合同算術は[[ユークリッド環]]の商の概念によって定式化できる。この概念は[[同値関係]]の概念により、多くの[[代数的構造]]に対して一般化される。例えば[[群 (数学)|群]]の[[正規部分群]]による[[剰余群|商]]は{{仮リンク|ジョルダン&ndash;ヘルダーの定理|fr|Théorème de Jordan-Hölder|redirect=1}}を通じて[[有限群]]の分類の基本的な道具であり、また[[代数的位相幾何学]]においても[[代数多様体]]の分類に利用される。[[環論]]においては[[イデアル (環論)|イデアル]]が正規部分群の役割を果たし、合同算術を含むもっと広い文脈において用いられる[[剰余環|商環]]の概念が定式化される。[[可換環論]]と[[代数幾何学]]の橋渡しを為す[[体上有限生成環の理論|ヒルベルトの零点定理]]はイデアルの言葉で表される。

とはいえ、合同や法といった語はユークリッド環の商の場合のために用いるのが普通である。

=== 多項式の割り算とガロワ理論 ===
{{main|{{仮リンク|多項式の算術|fr|Arithmétique des polynômes}}|ガロワ理論}}
[[Image:evariste galois.jpg|thumb|right|[[エヴァリスト・ガロワ]]は今日彼の名を以って呼ばれる理論の創始者である。]]

[[可換体]]に係数を持つ多項式環は、{{仮リンク|多項式の除法|en|Polynomial long division|fr|division d'un polynôme|label=除法}}が可能であるから、合同算術を考えることができる。[[ガロワ理論]]の出発点は[[多項式]]を[[既約多項式]]（これが数の場合の素数に相当）で割った合同類の集合を体系的に扱うことにある<ref>{{cite journal|first=Évariste|last=Galois|title=Sur les conditions de résolubilité des équations algébriques|journal=Journal de Liouville|year=1846}}</ref>。これら集合は今日では[[代数拡大]]と呼ばれる。

これら拡大により[[代数方程式]]（つまり、多項式の等式として書かれる方程式）の可解性が調べられるようになる。与えられた多項式が既約ならば、それを法とする合同類の集合は少なくとも一つその多項式の[[多項式の根|根]]を含む[[可換体|体]]を成す。これを[[根体]]と呼ぶ。これを繰り返して与えられた多項式の根をすべて含む体（[[分解体]]）が構成できる。合同に関する商を考える論法はこの問題に適した代数的構造を与えるのである。

ガロワ理論では他に様々な概念を利用する。方程式の可解性は、[[ガロワ対応]]と呼ばれる部分体と部分群の間の対応により、ガロワ群と呼ばれる体の[[自己同型]]群の研究を通じて調べられる。代数方程式の可解性の研究に留まらず、ガロワ理論は算術、{{仮リンク|ディオファントス幾何学|label=数論幾何学|fr|géométrie arithmétique}}や[[代数幾何学]]の様々な問題の解法の自然な一部を成し、また時にそういった様々な領域における新しい広汎な問題の定式化をもたらした。

同様の理論をより一般の[[ユークリッド環]]の商の概念を用いて記述するとき、合同算術の特定の道具からの繋がりにおいて、本項の主題とは大きく異なる別の領域が生じてくる。このような理論の成果の一つが、ガロワ体とも呼ばれる[[有限体]]であり、これは合同算術の様々な応用において自然な設定を与える。

=== 代数的整数と代数的整数論 ===
{{main|代数的整数論}}
[[Image:Ernst Eduard Kummer.jpg|thumb|right|[[エルンスト・クンマー]]は非常に多くの {{mvar|n}} に対する[[フェルマーの大定理]]を解決し、代数的整数論の基礎を作った。]]
合同算術はフェルマーの大定理を分析するためのよい枠組みを与えた。しかし、{{mvar|n}} が {{math|10}} より大きいとき、ガウスの方法に準じて構成される[[代数的整数]]の環を、ディリクレは ''obstruction''（邪魔なもの）と呼んだ。これらの整数環ではその（乗法逆元を持つ元全体の成す）[[単数群]]が、ガウスの研究とは異なり、もはや[[巡回群]]や[[有限アーベル群]]ではないことが示せる。それは整数の加法群のコピーを含み、無限群である。この結果は[[ディリクレの単数定理]]と呼ばれる。このような新しい状況では、付随する環がユークリッド環でないため、ガウス整数に用いた合同算術の道具が使えないという障害 (obstruction) を生じる。

素数が存在しない環における素数の代替として、[[エルンスト・クンマー]]は、今日ではイデアルを用いて定式化される商の一般化に関する道具を用いた。代数的整数論ではそれまでと異なるいくつかの手法が取り入れられる。基本的な道具は、その元が[[代数的整数]]と呼ばれ、[[デデキント環]]と呼ばれる構造を持つ環である。クンマーは {{mvar|n}} が[[正則素数]]と呼ばれる特定の種類の素数であるときのフェルマーの大定理を証明した<ref>{{cite journal|first=Ernst|last=Kummer|title=Sur la théorie des nombres complexes|journal=CRAS|year=1847}}</ref>。{{math|100}} 以下の値でこれに相当しないものは {{math|37, 59, 67}} の三つのみである。

そのほかの道具や数学的対象としては、[[アデール環]]、ガロワ理論の各概念、[[楕円曲線]]、[[ディリクレのL-函数|ディリクレの L-級数]]と[[モジュラー形式]]などが挙げられる。有限体などの合同算術にほぼ由来するいくつかの概念は20世紀においても広く用いられ、ときどき同様の手法をそのまま使うことはあるけれども、代数的整数論は合同算術の範囲を大きく超えた分野である。

=== ディリクレ指標と解析数論 ===
{{main|解析数論}}
[[Image:Riemann zeta function absolute value.png|thumb|left|[[リーマンゼータ函数]]の[[複素数の絶対値|絶対値]]を図示したもの。]]
[[Image:Georg Friedrich Bernhard Riemann.jpeg|thumb|right|[[ベルンハルト・リーマン]]はリーマンゼータ函数 ζ の[[零点]]の位置に関する仮説を立てた。]]
オイラーにより、素数を亙るある[[オイラー積|無限積]]が単位円の面積の平方の{{fraction|1|6}}（つまり、{{math|{{π}}{{exp|2}}/6}}）に等しいことが発見され、数の理解に対する新たなアプローチの仕方が生まれた。ディリクレはこれを用いて整数の合同類環の単数群が素数を無限に含むことを示した。今日ではこれは[[ディリクレの算術級数定理]]と呼ばれる。

この証明を得るためにディリクレは[[ディリクレのL-函数|ディリクレの L-級数]]という特別な道具を発明した。その一つは有名な[[リーマンゼータ函数]]に対応するものである。証明においてもっとも困難であったのは、この函数が点 {{math|1}} に根を持たないことであった。そのためにディリクレは合同類環の単数群上で[[有限アーベル群上の調和解析|調和解析]]を用いた<ref>{{cite journal|authorlink=Allen Lowell Shields|first=Allen Lowell|last=Shields|title=Lejeune Dirichlet and the birth of analytic number theory : 1837-1839|journal=The Mathematical Intelligencer|volume=11|year=1989|pages=7-11}}</ref>。

ここでもやはり、合同算術は定理に至るには不十分であり、ディリクレは[[冪級数|整級数]]や[[複素解析]]など種々の解析的手法を用いている。そうして新たな数学の分野である、解析数論が生まれた。解析数論の重要な通過点が[[ベルンハルト・リーマン]]の一つの論文 {{lang|de|''Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse''}}（「[[与えられた数より小さい素数の個数について]]」）によってもたらされる。リーマンは[[リーマン予想|ゼータ函数の根の位置に関する予想]]を提示した。ディリクレによってはじめられた根の位置の研究は、この分野の中心的な関心となり、現代の数学においても最も解決の難しい予想の一つとして残されている{{sfn|Delahaye|texte=Delahaye 2000|pp=222-224}}。{{clr}}

== 暗号理論 ==
{{main|暗号理論}}
<!--
[[Image:PhishingTrustedBank.png|right|thumb|L'[[hameçonnage]] est une technique visant à obtenir des informations confidentielles sur [[internet]] en vue d'une escroquerie. La nécessité de communication d'informations confidentielles représente un danger en [[cryptographie]].]]

L'objet de la cryptographie est d'assurer sécurité dans la transmission des messages. La [[confidentialité]] ainsi que l'[[authentification]] de ceux-ci sont deux exemples du sens donné au terme sécurité. On peut citer deux exemples : la protection des messages qu'utilise une armée pour empêcher une anticipation de l'ennemi, ou la carte bleue proposée par le système bancaire, offrant à un usager une bonne sécurité.

En termes plus mathématiques, l'opération de chiffrement se traduit par un [[Algorithmique|algorithme]], c'est-à-dire une fonction ''f'' qui, à un message en clair ''m'' et une [[Clé de chiffrement|clé]] ''k'', associe un message chiffré ''f''(''k'', ''m''). La connaissance du message chiffré et de l'algorithme doit être insuffisante pour reconstituer le message en clair sans une clé de déchiffrement. Dans le cas de la cryptographie traditionnelle, dite [[cryptographie symétrique]], la clé de déchiffrement est identique à la clé de chiffrement ou s'en déduit aisément. Cette clé doit alors rester secrète.

La [[cryptographie asymétrique]] s'appuie sur le constat que seule la clé de déchiffrement doit rester secrète, et connue du seul récepteur du message. Elle n'a pas besoin d'être communiquée à ses correspondants. Alice utilise la clé de chiffrement de Bob, que celui-ci a rendu publique, pour lui envoyer un message. Seul Bob peut le déchiffrer, même Alice, si jamais elle avait perdu le message en clair, en serait incapable. Bob doit répondre en utilisant la clé de chiffrement d'Alice.

L'objectif est donc de définir une fonction simple à évaluer mais difficile à inverser sans la connaissance d'un secret. L'arithmétique modulaire a été la première à offrir des solutions, et elle est toujours à la base de beaucoup de solutions commerciales. Par exemple l'[[échange de clés Diffie-Hellman]], premier exemple historique<ref name="DiffieHellman" />, exploite la difficulté pratique à inverser l'[[exponentiation modulaire]]. Cette dernière, ou ses généralisations à d'autres [[groupe (mathématiques)|groupes]], reste fondamentale dans le domaine.

La cryptographie asymétrique résout en particulier le délicat problème de la distribution des clés en cryptographie symétrique. Si plusieurs correspondants communiquent, en cryptographie symétrique, une clé différente s'avère nécessaire pour chaque couple d'intervenants, alors qu'en cryptographie asymétrique chaque correspondant dispose d'une clef qu'il garde secrète, et d'une clef qu'il rend publique. Cependant elle n'a pas fait disparaître les codes symétriques, qui offrent des algorithmes beaucoup plus efficaces. Pour une sécurité équivalente, les codes symétriques présentent l'avantage de nécessiter des clés nettement plus petites, 128 [[bit]]s pour la version courante de [[standard de chiffrement avancé|AES]], contre plus d'un millier pour le [[Rivest Shamir Adleman|RSA]], mais surtout le chiffrement comme le déchiffrement sont de cent à mille fois plus rapide<ref>Christine Bachoc, ''[http://archive.wikiwix.com/cache/?url=http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/crypto.pdf&title=Cours%20de%20cryptographie%20sym%C3%A9trique Cours de cryptographie symétrique]'', [[université Bordeaux I]], p. 3.</ref>. Les systèmes cryptographiques modernes, comme ceux utilisés par les [[Carte de paiement|cartes bancaires]], ou le protocole de communication cryptée [[Transport Layer Security|SSL/TLS]] très utilisé sur [[Internet]]<ref>{{chapitre|lang=en|
 | nom1=[[David Wagner]] et [[Bruce Schneier]]
 | titre = Analysis of the SSL 3.0 Protocol
 | titre ouvrage= The Second USENIX Workshop on Electronic Commerce Proceedings
 | éditeur= USENIX Press
 | année= 1996
 | passage= 29-40
 | url = http://www.schneier.com/paper-ssl.pdf
}}.</ref>, n'utilisent qu'en début de communication la cryptographie asymétrique, pour échanger les clés d'un chiffrement symétrique qui prendra ensuite le relais.
-->
=== 非対称暗号 ===
{{main|公開鍵暗号}}
<!--
Le code [[Rivest Shamir Adleman|RSA]] est un exemple largement répandu de cryptographie asymétrique. Le chiffrement utilise deux clés, une clé publique pour le [[chiffrement]], et une clé privée, pour le [[déchiffrement]]. La force d'un tel système réside dans le fait que la connaissance de la clé publique ne permet pas le [[Chiffrement|décryptage]]. Il se décrit de la manière suivante :

Alice (le choix des prénoms est traditionnel) souhaite pouvoir recevoir des messages de Bob sans qu'Ève puisse les déchiffrer. Alice choisit deux grands [[nombre premier|nombres premiers]] ''p'' et ''q'', dont elle calcule le produit ''n = pq'', et un entier ''e'', [[Nombres premiers entre eux|premier]] avec φ(''n'') = (''p'' – 1)(''q'' – 1), et strictement inférieur à ce nombre ; la fonction [[indicatrice d'Euler]] φ, donne l'ordre du groupe des [[inverse modulaire|éléments inversibles]] de ℤ/''n''ℤ. Le couple (''n'', ''e'') constitue alors la ''clé publique'' d'Alice, c'est-à-dire qu'elle peut être librement accessible, en particulier à Bob qui doit tout de même pouvoir s'assurer que cette clef est bien celle d'Alice.

Parallèlement Alice calcule l'inverse de ''e'' modulo ''n'', soit un entier ''d'' strictement inférieur à ''n'' vérifiant
<center><math>de + k\varphi(n)  = 1</math></center>
ce qui se fait de façon efficace par l'|[[algorithme d'Euclide étendu]] connaissant ''p'' et ''q'', donc φ(''n''). L'entier ''d'' constitue la ''clef privée'' d'Alice. On montre que la connaissance de ''d'' permet de retrouver la factorisation de ''n'' de façon efficace, le calcul de ''d'' et la factorisation de ''n'' sont donc calculatoirement équivalents<ref>{{Ouvrage|id=Menezes, van Oorschot et Vanstone 1996|lang=en|nom1={{Lien|Alfred Menezes}}|nom2={{Lien|Paul van Oorschot}}|nom3={{Lien|Scott Vanstone}}|titre=Handbook of Applied Cryptography|lien éditeur=CRC Press|éditeur=CRC Press|mois=10|année=1996|isbn=0-8493-8523-7|numéro chapitre=8|url=http://cacr.uwaterloo.ca/hac/about/chap8.pdf|passage=287}}.</ref>.

Les messages sont des entiers strictements inférieurs à ''n'', que l'on voit comme des éléments de l'anneau ℤ/''n''ℤ.
Si Bob souhaite transmettre le message ''m'' à Alice, il transmet la valeur de ''m<sup>e</sup> ''modulo ''n''. Alice a rendu au préalable publiques les valeurs de ''n'' = ''pq'', ''e'' et donc la fonction ''f'' de [[chiffrement]], qui est ici égale à :
<center><math> f(m) \equiv\ m^e \pmod n</math></center>
Ève peut connaître ''e'', ''n'' et donc ''f'', ces informations sont en effet publiques. En revanche, elle ne peut intercepter les valeurs de ''p'' et ''q'' qui n'ont jamais été communiquées.

Pour Bob, la fonction de codage est aisée : il s'agit d'une [[exponentiation modulaire]] qui se calcule de façon efficace. Pour Alice la lecture l'est aussi pour les mêmes raisons. En effet le [[théorème d'Euler (nombres)|théorème d'Euler]] montre que :
<center><math>m  \equiv f(m)^{d} \pmod n </math></center>
En revanche Ève ne connaît pas ''a priori'' les entiers ''p'' et ''q''.  Si ''n'' est grand (et si les entiers ''p'' et ''q'' sont bien choisis) il n'existe pas, à ce jour, d'algorithme assez efficace pour la [[décomposition en produit de facteurs premiers|factorisation]] de ''n''{{sfn|Menezes, van Oorschot et Vanstone 1996|loc=[http://cacr.uwaterloo.ca/hac/about/chap3.pdf chap. 3], section 3.2|ps=: ''The integer factorisation problem''}}. Plus généralement on ne connait pas de façon efficace de résoudre le [[problème RSA]], qui est celui d'inverser la fonction de chiffrement (dont on ne sait pas s'il est ou non plus facile à résoudre que le problème de la factorisation de ''n''){{sfn|Menezes, van Oorschot et Vanstone 1996|loc=chap. 3, section 3.3|ps=: ''The RSA problem''}}.
-->
=== 対称暗号 ===
{{main|共通鍵暗号}}
<!--
La cryptographie asymétrique n'existerait pas sans les méthodes issues de l'arithmétique modulaire. Celle-ci ne joue pas le même rôle fondateur en cryptographie symétrique, mais n'en est pas absente pour autant. Les chiffrements symétriques se divisent en deux grandes familles dont l'une, les [[chiffrement de flux|chiffrements par flot]], utilise souvent comme composant de base les suites récurrentes linéaires sur un corps fini (voir ci-dessous) ; l'autre, celle des [[chiffrement par bloc|chiffrements par blocs]], comprend entre autres le DES et son successeur, le [[standard de chiffrement avancé]], appelé couramment AES (pour ''Advanced Encryption Standard''). Ces derniers opèrent sur des blocs de données d'une taille fixe comptée en [[octet]]s, huit pour le DES par exemple. Une suite d'opérations primitives assez simples est appliquée de façon répétée pour coder un bloc. Un octet, ou plus généralement un bloc de ''n'' bits, peut être vu comme les coefficients d'un polynôme sur les entiers modulo deux, de degré maximal ''n ''– 1. Cela  a conduit les cryptologues à s'intéresser à certaines opérations sur les [[corps fini]]s de [[Caractéristique d'un anneau|caractéristique]] 2. Ainsi il s'avère que l'opération d'inversion sur le corps fini '''F'''<sub>2<sup>''n''</sup></sub>, composée avec une transformation affine, a de bonnes propriétés cryptographiques pour en faire l'une des primitives des chiffrements par blocs<ref>{{Chapitre|lang=en|nom1={{Lien|Kaisa Nyberg}}|url=http://cs.ucsb.edu/~koc/ccs130h/projects/05-shash/diffuni.pdf|titre=Differentially uniform mappings for cryptography|titre ouvrage=Advances in Cryptology - EUROCRYPT'93|numéro dans collection=765|collection=Lecture Notes in Computer Science|éditeur=Springer-Verlag|année=1994}}.</ref>. Ceci a été exploité par les auteurs du chiffrement [[Rijndael]], qui est devenu l'AES. La publication officielle de ce dernier par le [[National Institute of Standards and Technology|NIST]] (agence fédérale américaine) contient d'ailleurs quelques préliminaires mathématiques sur le sujet<ref>{{en}} ''[http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf Announcing the ADVANCED ENCRYPTION STANDARD (AES)]'', p. 10-12.</ref>. Cependant il n'est nul besoin d'algorithmique sur l'arithmétique ou les corps finis pour l'implémentation : ces opérations sont représentées par des tables, comme les opérations analogues du DES obtenues elles de façon beaucoup plus heuristique. Certains cryptologues ont vu une faiblesse potentielle dans la caractérisation trop algébrique de Rijndael, qui le rendrait plus accessible à l'imagination des mathématiciens<ref>{{Chapitre|lang=en|prénom=Niels|nom=Ferguson|nom2={{Lien|Richard Schroeppel}}|prénom3=Doug|nom3=Whiting|url=http://th.informatik.uni-mannheim.de/people/lucks/papers/Ferguson/RdAlgEq.pdf|titre=A simple algebraic representation of Rijndael|titre ouvrage=Proceedings of Selected Areas in Cryptography|année=2001|collection=Lecture Notes in Computer Science|passage=103-111}}.</ref>, ce qui n'a pas empêché son adoption pour l'AES.
-->
=== 素数判定 ===
{{main|素数判定}}
<!--
Les codes RSA utilisent comme clés les nombres premiers ''p'' et ''q'' du paragraphe précédent. L'usage, pour les trouver, consiste à choisir un nombre ''presque'' au hasard, de tester s'il est premier ou non et de recommencer s'il ne l'est pas.

Le [[crible d'Ératosthène]] est une méthode rapide pour les petits nombres. Utilisé habilement, 46 tests suffisent pour vérifier la primalité d'un nombre inférieur à {{formatnum:39000}}. En revanche, il est inefficace pour une application industrielle employant des nombres qui s'écrivent avec plusieurs centaines de chiffres.

La majorité des tests de l'industrie se fondent sur des variantes du [[petit théorème de Fermat]]<ref>Sur la page {{lien web|url=https://archive.today/raNDQ|titre=RSA Le plus connu des algorithmes asymétriques|année=2003|site=Cryptosec}}, on lit : {{Citation|La plupart des implémentations ont donc recours à des algorithmes probabilistes de test de primalité pour déterminer p et q, comme le test de primalité de Miller-Rabin.}}</ref>. Si un nombre ''p'' est premier, alors pour tout entier ''a'', ''a''<sup>p</sup> est congru à ''a'' modulo ''p''. La réciproque est fausse : il existe des nombres non premiers, appelés [[nombres de Carmichael]] (par exemple 561 = 3 × 11 × 17), pour lesquels la congruence est vraie pour toute valeur de ''a''. Toutefois, si ''p'' n'est ni un nombre de Carmichael, ni un nombre premier, la congruence est fausse pour au moins la moitié des valeurs de ''a'' comprises entre ''un'' et ''p''. Que la congruence soit vérifiée pour un grand nombre de valeurs de ''a'' indique une très forte probabilité de primalité pour ''p'', s'il n'est pas un nombre de Carmichael.

Le [[test de primalité de Solovay-Strassen]] et surtout le [[test de primalité de Miller-Rabin]] sont deux exemples largement utilisés. Ils se fondent sur une analyse plus poussée du petit théorème de Fermat et n'admettent pas d'analogues aux nombres de Carmichael, ce qui lève l'un des problèmes du [[Test de primalité de Fermat|test de Fermat]]. Pour ces deux méthodes, un [[Test de primalité#Tests déterministes rapides|test de primalité déterministe]] consiste à vérifier la propriété pour un nombre de valeurs de ''a'' garantissant une preuve irréfutable. Le nombre de calculs à effectuer étant rédhibitoire, on se contente d'un [[Test de primalité#Tests probabilistes|test probabiliste]]. Il consiste à vérifier la congruence sur un ensemble de valeurs de ''a'', choisi pour assurer une probabilité de primalité supérieure à une valeur donnée, souvent<ref>''[http://www.bibmath.net/crypto/complements/gdspremiers.php3 Comment fabriquer de grands nombres premiers ?]'' sur le site bibmath.net de F. Bayart.</ref> égale à 1 – (1/2){{exp|100}}.
-->
=== 積の素因数分解 ===
{{main|素因数分解}}
{{仮リンク|秘匿による安全性|en|Security through obscurity}}は、RSA暗号には及ばない。重要なことは、整数の素因数への分解の様子を明確に知ることである。{{仮リンク|RSA Factoring Challenge|en|RSA Factoring Challenge}}と呼ばれる、公開されたリストにある整数を選んで因数分解できたものを表彰するコンペが、2007年5月まで開かれた。

エラトステネスの篩は分解の方法を与える素数判定法であるが、しかし巨大な整数には時間が掛かり過ぎて適用できない{{sfn|Delahaye|texte=Delahaye 2000|p=215}}.

現在では[[平方剰余]]に基づく別な方法がしばしば用いられる{{sfn|Delahaye|texte=Delahaye 2000|p=302}}。少なくとも二つの完全平方数を代表元に含む平方剰余が[[零因子]]になり、その二つの平方数を求めることが目標となる。このような方法が{{仮リンク|二次篩法|en|Quadratic sieve}}および[[一般数体篩法]]であり、後者は2007年時点で最速である<ref>{{cite journal|language=en|authorlink=Carl Pomerance|first=Carl|last=Pomerance|url=http://www.ams.org/notices/199612/pomerance.pdf|title=A Tale of Two Sieves|journal= [[Notices of the American Mathematical Society]]|volume=43|year=1996|pages=1473-1485}}</ref>。また、[[ポラード・ロー素因数分解法|ポラードの ρ アルゴリズム]]は[[誕生日のパラドクス]]に用いられる。

=== 有限体 ===
{{main|有限体}}
素数による商体 {{math|ℤ/''p''ℤ}} の構成は他の構造へ一般化される。情報処理において、数は {{mvar|n}} [[ビット]]でコードされる（つまり、数は {{math|0}} と {{math|1}} からなる長さ {{mvar|n}} の数列に対応する）。それは[[二元体]] {{math|'''F'''{{sub|2}}}} 上の {{mvar|n}}-[[次元 (線型代数学)|次元]][[ベクトル空間]]のベクトルと見なすことができる。この構造はしばしば {{math|'''F'''{{sub|2}}}} に係数を持つ次数が {{mvar|m}} より真に小さい多項式全体の成す空間と見なされる。乗法について[[閉じている]]ためには、この空間は次数 {{mvar|n}} の適当な多項式 {{mvar|f}} で割られなければならない。その多項式 {{mvar|f}} が既約（素数に対応するもの）であるとき、得られる構造は位数 {{math|2{{sup|n}}}} の有限体になる。数 {{math|''a'' modulo 2{{sup|''n''}}}} と多項式 {{math|''P'' modulo ''f''}} はよく似ており、事実 <math display="block">a = \sum_{i=0}^{n-1} a_i2^i \quad\text{ and }\quad P = \sum_{i=0}^{n-1} \alpha_iX^i \quad (a_i,\alpha_i \in \mathbf F_2)</math> のように書ける。

用例の一つは {{math|'''F'''{{sub|2}}}} 上の[[疑似乱数]]生成器である。そのような生成器は例えば[[携帯電話]]での音声通信の文脈で[[ストリーム暗号]]<ref>{{lang-en}} Anne Canteaut, ''[http://www-rocq.inria.fr/codes/Anne.Canteaut/encyclopedia.pdf Stream Cipher]'', extrait de ''{{Lien|Encyclopedia of Cryptography and Security}}'', H. van Tilborg, Springer, 2005.</ref> [[A5/1]] によって使われる。これは[[線形帰還シフトレジスタ]] (LFSR) の後ろの成分を持つ。{{math|'''F'''{{sub|2}}}} の元の長さ {{mvar|n}} の二つの有限列として、係数列および初期化列が <math display="block">(c_1, \dots, c_n) \quad\text{ and }\quad (u_0,\dots, u_{n-1})</math> で与えられるとき、LFSRは疑似乱数列 {{math|(''u{{sub|j}}'')}} を[[線形回帰数列]] <math display="block">u_j = \sum_{i=1}^n c_iu_{j-i}\quad (j\geq n)</math> によって得る。係数列はしばしば固定される。ゆえに鍵は、整数 {{math|''a'' modulo 2{{sup|''n''}}}} で表される初期化列 <math display="block">a = \sum_{i=0}^{n-1} u_i2^i</math> を与える。得られた結果は周期的だが、係数列を適切に選べば周期は {{math|2{{sup|''n''}} – 1}} と非常に長くなる。この状況は、<math display="block">R = 1-\sum_{i=1}^nc_i X^i</math> で与えられる「帰還多項式」{{mvar|R}} が[[巡回群]] {{math|('''F'''{{sub|2{{sup|''n''}}}})*}} の生成元の[[最小多項式 (体論)|最小多項式]]であるときに生じる。

=== 有限アーベル群上の調和解析 ===
{{main|[[有限可換群上の調和解析]]}}
<!--
Les idées de Dirichlet s'appliquent sur le système modulaire du paragraphe précédent. Pour l'addition, l'espace vectoriel ''V'' précédent est un [[groupe abélien fini]]. Les [[Caractère d'un groupe fini|caractères]] de ce groupe forment une [[base orthonormale]] de l'ensemble des fonctions de ''V'' dans celui des [[nombre complexe|nombres complexes]]. Il est à noter<ref>[[Douglas Stinson]], ''Cryptographie théorique et pratique'', Int. Thomson Pub. France, 1996.</ref> que l'ensemble d'arrivée choisi n'est pas toujours celui des complexes mais parfois le corps ''F''<sub>2</sub>. Les résultats sont strictement identiques. Une telle structure dispose d'une analyse harmonique. Si l'ensemble d'arrivée est choisi égal à '''F'''<sub>2</sub>, la [[transformée de Fourier]] prend le nom de [[transformée de Walsh]]. Cette approche est utilisée à la fois pour les systèmes DES, RSA et certains [[chiffrement de flux|chiffrements de flux]].

Un [[registre à décalage à rétroaction linéaire]] est trop aisément déchiffrable. Pour un registre de longueur ''n'', même si la suite engendrée est de période 2<sup>''n''</sup> – 1, l'algorithme de ''Berlekamp-Massey'' permet de déterminer celle-ci grâce la connaissance de ''2n'' valeurs consécutives, avec une [[Théorie de la complexité (informatique théorique)|complexité]] quadratique. Ainsi, si la clé est composée de 128 bits, il suffit de 128 × 128 · ''k'' = 16 384 · ''k'' étapes pour le décrypter, où ''k'' est suffisamment « petit » pour que cela représente une sécurité insuffisante. La solution adoptée consiste à utiliser plusieurs registres à décalage. Les différents résultats sont vus comme un élément d'un nouvel espace vectoriel sur '''F'''<sub>2</sub>. Une [[fonction booléenne]] associe à chaque élément de cet espace la valeur ''un'' ou ''zéro''. Si une telle fonction est bien choisie, le meilleur algorithme de déchiffrement connu demande de l'ordre de 2<sup>''n''</sup> étapes pour trouver le signal apportant la confusion. La détermination de cette fonction est obtenue à l'aide des outils de l'analyse harmonique.

Pour un code RSA et à la fin du {{s-|XX}}, la clé est souvent un nombre{{sfn|Singh|2001|p=345}} dépassant 10{{exp|308}}. Il est important de disposer d'une multiplication rapide sur les grands moduli. La technique consiste à identifier les moduli aux polynômes sur un corps fini. La multiplication de deux polynômes de degré ''n'' est une opération qui, si elle est réalisée de manière naïve, impose une complexité quadratique. Les caractères du groupe additif associés étant orthogonaux, la complexité devient linéaire si une telle base est utilisée. Un calcul plus rapide consiste à réaliser une [[transformée de Fourier rapide]], à multiplier les deux résultats et à opérer la transformée de Fourier inverse. La complexité totale est alors en ''n''{{math|log}}(''n'') où {{math|log}} désigne ici le [[logarithme]] de base 2.
-->

== 誤り訂正符号 ==
{{main|誤り検出訂正}}
<!--
[[Image:CD autolev crop.jpg|thumb|left|Les ''[[Disque compact|CD]]'' utilisent comme [[code cyclique]] une variante du [[code de Reed-Solomon]] appelée « code C.I.R.C. »]]
Un code correcteur n'a pas la vocation d'assurer la sécurité, mais la fiabilité de la transmission d'un message. Il permet de restituer le texte original même si une perturbation aléatoire et modérée se produit durant la transmission. Le message « encodé » est transmis sous une forme appelée « mot du code ». Il contient non seulement les informations du message initial mais aussi les  [[Code correcteur#Redondance et fiabilité|redondances]] permettant la validation d'une bonne communication et parfois la correction automatique d'éventuelles erreurs.

Un mot du code est composée d'une famille de ''n'' « lettres » choisies dans un « alphabet », en général binaire. Le cas industriel le plus fréquent est celui du [[code linéaire]], la valeur ''n'' est constante pour chaque mot du code et est appelée ''dimension'' du code. L'ensemble des mots du code est muni d'une structure d'[[espace vectoriel]] de [[Dimension d'un espace vectoriel|dimension]] ''n''.

Les codes linéaires utilisent essentiellement l'arithmétique modulaire comme base mathématique. Beaucoup enrichissent la structure d'espace vectoriel par celle d'un anneau de polynômes sur un [[corps fini]]. Ce corps est parfois le corps binaire, souvent un corps de cardinal une puissance de deux. On parle alors de [[code cyclique]].

Les codes linéaires sont largement présent dans l'industrie. {{Référence nécessaire|La [[Télécommunications|télécommunication]] les utilise pour le [[Téléphone mobile|téléphone portable]] ou [[internet]], l'informatique pour notamment la communication entre la mémoire et de [[processeur]], l'audio-visuel pour les [[disque compact|disques compacts]] ou d'autres formats de même nature comme les [[DVD]].}}
-->
=== チェックサム ===
{{main|チェックサム}}
<!--
[[Image:Bit de parité.jpg|thumb|right|Code de longueur deux avec une somme de contrôle.]]

Une somme de contrôle est un [[code linéaire]] particulièrement utilisé. Il correspond à un [[code correcteur]] dont seule la détection est automatisable, la correction est obtenue par une demande de répétition du message.

Au message initial est ajoutée une information codée sur une lettre. La lettre est choisie de telle manière que la congruence de la somme des lettres du mot du code soit égale à une valeur donnée, souvent zéro. Dans l'exemple illustré sur la figure de droite, le message initial est composé de deux lettres, un mot du code en contient trois, si le message initial est 00, le mot du code transmis est 00'''0''', si le message est 01, le mot du code devient 01'''1'''. Les quatre mots possibles du code sont illustrés par les points verts de la figure.

Si une unique erreur se produit, sur n'importe laquelle des trois lettres du mot du code, le message reçu correspond à un point noir. Le récepteur sait qu'il doit demander le renouvellement de la transmission. Cette configuration est analogue quelle que soit la longueur du mot du code. Une longueur égale à huit est souvent choisie, elle permet la transmission d'un message de sept lettres. Le résultat est identique, chaque mot licite du code ne possède pour voisin que des mots hors du code, une unique erreur durant la transmission est ainsi détectée. En revanche une double anomalie est systématiquement passée sous silence.
-->
=== 巡回符号 ===
{{main|巡回符号}}
<!--
[[Image:Code correcteur parfait.svg|thumb|left|Illustration d'un [[Code parfait et code MDS|code parfait]].]]
Il existe certaines situations où la demande de répétition n'est pas possible, par exemple pour un [[DVD]], lorsqu'une poussière masque une information. Il est nécessaire d'imaginer des codes correcteurs qui, non seulement détectent, mais corrigent automatiquement les erreurs.

La méthode utilisée consiste à éloigner les mots du code à une [[distance de Hamming|distance]] suffisante pour repérer le bon message d'origine. La distance entre deux points correspond au nombre de lettres à modifier pour passer de l'un à l'autre. Le graphique de gauche illustre cette situation. Les points verts correspondent aux mots du code, par définition sans erreur. Les bleus sont ceux obtenus lorsqu'une unique lettre est altérée dans la transmission et les rouges quand deux lettres sont modifiées. Dans le schéma, on remarque que chaque point bleu contient un unique point vert à une distance de ''un'' et à chaque point rouge correspond un unique point vert situé à une distance de ''deux''. Si une ou deux erreurs se sont produites, l'unique point vert le plus proche correspond nécessairement au message initial. Un tel code est capable de protéger jusqu'à deux erreurs.

L'arithmétique modulaire fournit des solutions [[Code parfait et code MDS|optimales]] pour construire la géométrie d'un [[code linéaire]] correcteur. Comme un espace vectoriel ne constitue pas une structure suffisante pour définir des moduli, il est enrichi d'une structure d'anneau de polynômes quotienté par ''X''<sup>n</sup> - 1, où ''n'' désigne la dimension de l'espace vectoriel. Dans cet espace de modulo, le monôme X<sup>n</sup> est identifié au polynôme constant ''un''. Si la chaîne (a<sub>0</sub>, a<sub>1</sub>…, a<sub>n</sub>) est un mot du code, alors il en est de même de la suivante : (a<sub>n</sub>, a<sub>0</sub>, a<sub>1</sub>…, a<sub>n-1</sub>). On parle pour cette raison de ''code cyclique''. La logique est la même que celle d'un code correcteur, à la différence près que la congruence est définie non pas sur un entier mais sur un [[polynôme cyclotomique]] à coefficients dans un corps fini.

L'exemple le plus simple correspond au [[Code de Hamming (7,4)|code de Hamming]] dont les messages à transmettre comportent quatre lettres et trois lettres supplémentaires décrivent les [[Contrôle de redondance cyclique|redondances]].
-->
=== マクウィリアムス恒等式 ===
{{main|{{仮リンク|マクウィリアムス恒等式|fr|Identité de MacWilliams}}}}
<!--
Le contexte d'un code linéaire est analogue à celui de la cryptographie, on y trouve aussi des espaces vectoriels de dimension ''n'' sur un corps fini et un système de modulo de polynômes<ref>{{cite journal|language=de|first=Michael|last=Klemm|title=Über die Identität von MacWilliams für die Gewichtsfunktion von Codes|journal=Archiv der Mathematik|volume=49|issue=5|year=1987|pages=400-406|url=http://link.springer.com/article/10.1007/BF01194097}}.</ref>, le polynôme choisi étant souvent : ''X''<sup>n</sup> + 1. Les caractères du groupe sont utilisés, ainsi que l'[[analyse harmonique sur un espace vectoriel fini|analyse harmonique]] associée.

L'[[identité de MacWilliams]]<ref>{{en}} [[Jessie MacWilliams]] et [[Neil Sloane]], ''The Theory of Error-Correcting Codes, '' [[Elsevier (éditeur)|North-Holland]], 1977 {{ISBN2|9780444850096}}.</ref> est un exemple archétypal. Elle permet la détermination du ''polynôme énumérateur des poids'' du ''code dual'' ou encore l'étude des caractéristiques du [[code de Hamming]]. Elle est obtenue grâce à l'analyse harmonique, à l'aide d'un [[produit de convolution]].
-->
== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist|2}}

== 参考文献 ==
* {{ouvrage|prénom=Carl Friedrich|nom=Gauss|lien auteur1=Carl Friedrich Gauss|titre=Recherches arithmétiques|titre original=[[Disquisitiones arithmeticae]]|année=1801|traducteur=A.-C.-M. Poullet-Delisle, éd. Courcier, 1807}}
* {{Merveilleux nombres premiers}}
* {{Lang1}}
* [[Simon Singh]], ''Le Dernier Théorème de Fermat'', [[Hachette Livre]] Littérature, 1999 {{ISBN2|9782709618540}}
* {{Ouvrage|prénom1=Simon|nom1=Singh|titre=[[Histoire des codes secrets]]|éditeur=Poche|année=2001|isbn=978-225315097-8}}
* Gilles Zémor, ''Cours de cryptographie'', Cassini, 2000 {{ISBN2|9782842250201}}
* {{Demazure1}}
* {{en}} {{Lien|Gavin Flood}}, ''The Blackwell Companion to Hinduism'', [[Blackwell Publishing]], 2005 {{ISBN2|9781405132510}}
* {{en}} [[Michael Sean Mahoney]], ''The Mathematical Career of Pierre De Fermat, 1601-1665'', [[Princeton University Press]], {{2e}} éd., 1994 {{ISBN2|978-0-691-03666-3}}
* {{en}} {{Lien|lang=de|Waldo Dunnington}}, ''Carl Friedrich Gauss: Titan of Science'', [[Mathematical Association of America]], 2003 {{ISBN2|0-8838-5547-X}}

== 関連項目 ==
* [[冪剰余]] - [[剰余演算]]
* [[ペル方程式]]
* [[中国の剰余定理]]
* [[モジュラ逆数]]
* [[Category:算術]]

== 外部リンク ==
* {{MathWorld|urlname=CongruenceArithmetic|title=Congruence Arithmetic}}
* Quelques phrases extraites de la [http://www.beaumont-de-lomagne.fr/fermat/lettre.php correspondance de Fermat], sur le site de la commune de [[Beaumont-de-Lomagne]]
* [http://www.dma.ens.fr/culturemath/maths/pdf/histoire/gauss.pdf Carl Friedrich Gauss. Le Prince des Mathématiciens] par Farouk Boucekkine, sur le site CultureMATH
* [https://web.archive.org/web/20070929121816/http://laic.u-clermont1.fr/~richard/crypto.pdf Arithmétique modulaire et cryptographie], Denis Richard, [[Université Clermont-Ferrand-I]]
* [https://web.archive.org/web/20070930043827/http://comelec.enst.fr/~rioul/documents/200609corpsfinis.pdf Corps finis], Olivier Rioul, [[Télécom ParisTech|ENST]]
* [http://www-rocq.inria.fr/codes/Anne.Canteaut/crypto_moderne.pdf La cryptologie moderne], Anne Canteaut ([[Inria]]) et Françoise Levy-dit-Vehel ([[ENSTA ParisTech]])

{{DEFAULTSORT:こうとうさんしゆつ}}
[[Category:合同算術|*]]
[[Category:数学に関する記事]]