Voir la source de Arithmétique modulaire

{{En-tête label|AdQ|année=2007}}
[[Image:Disqvisitiones-800.jpg|vignette|Couverture de l’édition originale des [[Disquisitiones arithmeticae|Recherches arithmétiques]] de [[Carl Friedrich Gauss|Gauss]], livre fondateur de l’arithmétique modulaire.]]

En [[mathématiques]], et plus précisément en [[théorie algébrique des nombres]], l’'''arithmétique modulaire''' est un ensemble de méthodes permettant la résolution de problèmes sur les [[Entier relatif|nombres entiers]]. Ces méthodes dérivent de l’étude du reste obtenu par une [[division euclidienne]].

L'idée de base de l'arithmétique modulaire est de travailler non sur les nombres eux-mêmes, mais sur les restes de leur [[division]] par quelque chose. Quand on fait par exemple une [[preuve par neuf]] à l'école primaire, on effectue un peu d'arithmétique modulaire sans le savoir : le diviseur est alors le nombre 9.

Si ses origines remontent à l’Antiquité, les historiens associent généralement sa naissance à l’année [[1801 en science|1801]], date de la publication du livre ''[[Disquisitiones arithmeticae]]''<ref>{{harvsp|Gauss|1801}}.</ref> de [[Carl Friedrich Gauss]]. Sa nouvelle approche permet d’élucider de célèbres conjectures<ref>Par exemple la [[loi de réciprocité quadratique]] {{p.|96}} ou la [[construction à la règle et au compas]] de l’[[heptadécagone]] {{p.|429-489}} de {{harvsp|Gauss|1801}}.</ref> et simplifie les démonstrations d’importants résultats<ref>On peut citer le [[théorème de Wilson]] {{p.|56}} ou le [[petit théorème de Fermat]] {{p.|50}} de {{harvsp|Gauss|1801}}.</ref> par une plus grande abstraction. Si le domaine naturel de ces méthodes est la [[théorie des nombres]], les conséquences des idées de Gauss se retrouvent dans d’autres champs des mathématiques, comme l’[[algèbre]] ou la [[géométrie]].

Le {{s-|XX}} modifie le statut de l’arithmétique modulaire. L'arithmétique de base des ordinateurs, celle qui travaille sur des [[mot (informatique)|mots mémoire]] de taille fixe, est nécessairement une arithmétique modulaire. Le développement de nombreuses applications industrielles impose la mise au point d’[[Algorithmique|algorithmes]] pour l'arithmétique modulaire. Ils résolvent essentiellement des questions soulevées par le développement de l'[[informatique]].

''L’article « [[Congruence sur les entiers]] » propose une introduction plus mathématique ;'' « [[Anneau Z/nZ|''Anneau ''ℤ/''n''ℤ]] » ''traite le même sujet de manière moins didactique et plus exhaustive.''

== Usages ==
{{section à recycler|date=décembre 2012}}
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}} [[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{{référence nécessaire}}, 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''<ref>{{harvsp|Singh|2001|p=324-329}}.</ref>.

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>.

== Histoire ==
=== Origines ===
[[Image:Diophantus-cover.jpg|gauche|vignette|Couverture de l'édition de [[1621]] de [[Arithmetica]] de [[Diophante d'Alexandrie|Diophante]], traduite en [[latin]] par [[Claude-Gaspard Bachet de Méziriac]].]]

Au {{-s|III|e}}, [[Euclide]] formalise, dans son livre les ''[[Éléments d'Euclide|Éléments]]'', les fondements de l'arithmétique. On y trouve notamment le [[Lemme (mathématiques)|lemme]] couramment nommé ''[[lemme d'Euclide]]'', une version datée du [[théorème fondamental de l'arithmétique]] et une étude sur les [[nombre parfait|nombres parfaits]]<ref>{{Article|lang=en|lien auteur=Thomas Heath|prénom=Thomas|nom=Heath|titre=The thirteen books of Euclid's Elements|revue=[[The Mathematical Gazette]]|vol=6|numéro=92|année=1911|p.=98-101}} {{Référence à confirmer|date=mars 2013}}.</ref> dans la proposition 36 de son livre IX<ref>''Éléments'' d'Euclide, {{en}} [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX36.html Livre IX, Proposition 36].</ref>. [[Diophante d'Alexandrie]] <small>(env. [[250]]<ref>Les dates de naissance et de mort de Diophante sont mal connues, cf. {{en}} [[Norbert Schappacher]], ''[http://www-irma.u-strasbg.fr/~schappa/NSch/Publications_files/Dioph.pdf Diophantus of Alexandria : a Text and its History]'', 2005.</ref>)</small> écrit son ''[[Arithmetica]]'' qui contient 130 équations. Il traite essentiellement de problèmes ayant une unique solution numérique et à valeur fractionnaire ou entière. On y trouve que les nombres sommes de deux [[carré parfait|carrés parfaits]] ne sont jamais de la forme 4''n'' + 3. Les équations, à coefficients entiers et dont les solutions recherchées sont entières, prennent aujourd'hui le nom d'[[équation diophantienne|équations diophantiennes]].

La [[Chine]] développe parallèlement une arithmétique modulaire. [[Sun Zi (mathématicien)|Sun Zi]] écrit vers l'an [[300]] un traité de mathématiques dont le problème 26 du chapitre 3 est le suivant : {{Citation|Soient des objets dont on ignore le nombre. En les comptant 3 par 3 il en reste 2, en les comptant 5 par 5, il en reste 3 et en les comptant 7 par 7, il en reste 2. Combien y a-t-il d'objets ?}}<ref>[[Jean-Claude Martzloff]], ''Histoire des mathématiques chinoises'', [[Éditions Masson]], 1988 {{ISBN|978-2-2258-1265-1}}, {{p.|129}}.</ref>.

[[Qin Jiushao]] <small>([[1202]] - [[1261]])</small> développe le [[théorème des restes chinois]]<ref>Qin Jiushao, ''Shushu Jiuzhang'', (''[[Traité mathématique en neuf sections]]''), [[1247]].</ref>. Son traité est remarquablement avancé ; il traite d'un [[système d'équations linéaires|système]] de [[Congruence linéaire|congruences linéaires]] dans le cas où les [[congruence sur les entiers|moduli]] ne sont pas [[nombres premiers entre eux|premiers entre eux]] deux à deux. Ses travaux sur les systèmes de [[Congruence sur les entiers|congruences]] dépassent en sophistication ceux de [[Leonhard Euler]]. On peut citer [[George Sarton]] pour qui : {{Citation|Qin Jiushao était l'un des plus grands mathématiciens de sa [[Race humaine|race]], de son temps et à vrai dire de tous les temps<ref>{{en}} Joseph C. Y. Chen, ''Early Chinese Work in Natural Science'', Hong Kong University Press, 1996, [https://books.google.fr/books?id=2Wxj0SW9hBgC&pg=PA224 {{p.|224}}] cite Sarton (1947), vol. 3, {{p.|626}}.</ref>.}}

Le {{XIVe siècle}} voit un déclin progressif puis un oubli de ces résultats, le savoir de Qin Jiushao ne dépasse pas les frontières chinoises avant le {{s-|XX}}. Il est redécouvert par les travaux de l'historien des sciences [[Joseph Needham]]. En revanche, de nombreuses similarités entre les notations arabes et chinoises laissent penser à des contacts durant les périodes précédentes<ref>{{Article|lang=en|lien auteur=Karine Chemla|prénom=Karine|nom=Chemla|titre=Similarities between chineese and arabic mathematical writings : (I) root extraction|revue={{Lien|Arabic Sciences and Philosophy}}|vol=4|numéro=2|année=1994|p.=207-266}}.</ref>.

L'[[Histoire de l'Inde|Inde]] possède aussi une tradition forte en arithmétique. [[Aryabhata]] <small>([[476]] - [[550]])</small> recherche de manière systématique<ref>{{de}} {{Lien|lang=de|Hans-Joachim Ilgauds}}, « Aryabhata I », dans [[Hans Wussing]] et Wolfgang Arnold, ''Biographien bedeutender Mathematiker'', Berlin, 1983.</ref> les solutions entières de l'équation linéaire à deux [[inconnue (mathématiques)|inconnues]] à coefficients entiers. Il utilise pour cela un algorithme appelé « Kuttaka » publié dans son livre<ref>Agathe Keller, ''[http://halshs.ccsd.cnrs.fr/docs/00/04/96/19/PDF/Analyse.pdf Un commentaire indien du {{s-|VII}}]'', thèse de l'[[université Paris-VII]].</ref> appelé ''Âryabhatîya''. Les équations diophantiennes de degré deux sont étudiées par [[Brahmagupta]] <small>([[598]] - [[668]])</small><ref>{{en}} S. S. Prakash Sarasvati, ''A critical study of Brahmagupta and his works'', Delhi, 1986.</ref>. Au {{s|XII}}, [[Bhāskara II]] met au point la [[méthode chakravala]].

La [[Sciences et techniques islamiques|civilisation islamique]] joue un double rôle en arithmétique : elle véhicule le savoir acquis par les Grecs, Indiens, Chinois et Européens<ref>{{en}} [[Shlomo Pinès]], ''Studies in Arabic versions of Greek texts and in Medieval science'', Leiden, 1986.</ref>, et elle apporte des connaissances nouvelles<ref>[[Roshdi Rashed]], ''Entre arithmétique et algèbre : Recherches sur l'histoire des mathématiques arabes'', [[Les Belles Lettres]], Paris, 1984 {{ISBN|2-2513-5531-6}}.</ref> notamment sur l'étude des propriétés de certains ensembles d'[[Entier relatif|entiers]], comme les [[Nombre premier|nombres premiers]], [[Nombre parfait|parfaits]], [[Nombre amical|amicaux]] ou [[Nombre figuré|figurés]]<ref name=arabes>[[Ahmed Djebbar|A. Djebbar]], [[Denis Savoie|D. Savoie]], D. Jacquart, M. El Faïz, ''L'Âge d'or des sciences arabes'', exposition d'oct. 2005 à l'[[Institut du monde arabe]], [[Actes Sud]] {{ISBN|2-7427-5672-8}}, {{p.|69}}.</ref>. Dans ce contexte, Qusta ibn Lûqâ réalise une traduction partielle de l'[[Arithmetica]] de [[Diophante d'Alexandrie]]<ref name=arabes/> à la fin du {{IXe siècle}} et Al-Hajjaj traduit à la même époque les ''Éléments'' d'Euclide<ref>{{en}} [[John Lennart Berggren]], ''Episodes in the Mathematics of Medieval Islam'', Springer, 1986, {{p.|70-71}}.</ref> ; son collègue [[Al-Khawarizmi (Mohamed Ibn Mussa)|al-Khuwārizmī]] <small>(env. [[783]] - env. [[850]])</small> écrit un livre sur la numération indienne. Si le livre est perdu, il reste connu par une traduction latine ''Algoritmi de numero Indorum''<ref>{{Article|lang=en|nom1={{Lien|trad=John Crossley (mathematician)|John Crossley (mathématicien)|texte=John Crossley}}|prénom2=Alan|nom2=Henry|titre=Thus Spake al-Khwārizimī: A Translation of the Text of Cambridge University Library Ms. li.vi.5|lien périodique=Historia Mathematica|revue=Historia Mathematica|vol=17|année=1990|p.=103-131}}.</ref>. [[Thābit ibn Qurra|Thābit]] <small>([[836]] - [[901]])</small> étudie les nombres amicaux et les nombres parfaits<ref>{{en}} Francis J. Carmody, ''Thabit b. Qurra, Four Astronomical Tracts in Latin'', Berkeley, 1941.</ref>. [[Alhazen]] <small>([[965]] - [[1039]])</small> continue ses travaux sur les nombres parfaits et découvre le [[théorème de Wilson]]<ref>{{Article|prénom=Roshdi|nom=Rashed|titre=Ibn al-haytham et le théorème de Wilson|revue=[[Archive for History of Exact Sciences]]|vol=22|numéro=4|année=1980|p.=305-321}}.</ref>.

=== Apparition en Europe ===
[[Fichier:Pierre de Fermat.jpg|vignette|droite|[[Pierre de Fermat]] développe largement l'[[arithmétique]]. Les propriétés de la [[division euclidienne]], fondement de l'arithmétique modulaire, sont largement utilisées par ce mathématicien.]]
En 1621, [[Claude-Gaspard Bachet de Méziriac]] traduit le livre de Diophante en latin. Les questions soulevées intéressent les mathématiciens de l'époque. [[Pierre de Fermat]] propose un grand nombre d'énoncés, les trois plus célèbres étant probablement son [[Dernier théorème de Fermat|grand théorème]], son [[Théorème des deux carrés de Fermat|théorème des deux carrés]] et son [[petit théorème de Fermat|petit théorème]]. La [[communauté scientifique]] se lance des défis sur ce sujet, ainsi Fermat demande : {{Citation|un nombre carré qui, ajouté à la somme de ses parties aliquotes (i.e. ses diviseurs), fasse un cube.}} Il conclut par : {{Citation|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|Fermat]], ''Correspondance'', 3 janvier 1657.</ref>. [[Marin Mersenne]] recherche des [[Nombre premier de Mersenne|nombres premiers particuliers]]. Fermat lui écrit : {{Citation|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}}<ref>Fermat, ''Correspondance'', lettre à Marin de Mersenne, 25 décembre 1640.</ref>. Ces nombres sont maintenant appelés [[nombre de Fermat|nombres de Fermat]] et sa phrase s'avère être l'unique [[conjecture]] fausse proposée par l'auteur. [[René Descartes]] recherche sans y parvenir, à démontrer que si la division par huit d'un [[nombre premier]] donne pour reste un ou trois, il s'écrit de la forme ''x''{{exp|2}} + 2''y''{{exp|2}}.

Sur ce type de problèmes, deux éléments sont remarquables :
: Les équations diophantiennes fascinent, le titre d'un des livres de Bachet de Méziriac est évocateur : ''Problèmes plaisants et délectables qui se font par les nombres'', on peut citer encore la remarque de Fermat à propos de son grand théorème : {{Citation|J'ai trouvé une solution merveilleuse …}}<ref>Remarques de Fermat insérées par Pierre Samuel (son fils) dans l'édition de 1670 de l'''[[Arithmetica]]'' de Diophante.</ref>

: Les problèmes posés sont difficiles. Malgré quelques succès comme l'[[Théorème de Bachet-Bézout|identité de Bézout]] probablement due à Bachet de Méziriac, l'essentiel des questions restent sans réponse, comme le théorème des deux carrés de Fermat, ou avec des réponses pour le moins peu convaincantes, comme celle de Fermat pour son grand théorème :«… mais la place me manque ici pour la développer » (la première preuve reconnue apparaîtra en 1995<ref>{{Article|lang=en|lien auteur=Andrew Wiles|prénom=Andrew|nom=Wiles|url=http://math.stanford.edu/~lekheng/flt/wiles.pdf|titre=Modular elliptic curves and Fermat's last theorem|lien périodique=Annals of Mathematics|revue=Ann. Math.|vol=141|numéro=3|année=1995|p.=443-551}}.</ref>). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec : {{Citation|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>Fermat, ''Correspondance'', lettre à Frénicle de Bessy, 18 octobre 1640.</ref> …}}

=== Méthodes utilisées ===
[[Fichier:Leonhard Euler 2.jpg|vignette|droite|[[Leonhard Euler]], théoricien des nombres du {{XVIIIe siècle}}, résout plusieurs [[équation diophantienne|équations diophantiennes]].]]
Le siècle suivant voit la résolution de certaines de ces questions, souvent par [[Leonhard Euler]] : il contredit Fermat en démontrant que ses nombres ne sont pas toujours premiers, et prouve le théorème des deux carrés<ref>[[Leonhard Euler|Euler]], ''Correspondance'', lettre à Goldbach, 12 avril 1749.</ref>. Il commet aussi des erreurs, sa tentative de démonstration du grand théorème de Fermat pour ''n'' égal à trois est un échec, sa première démonstration s'avère fausse<ref>Euler, ''Algèbre'', 1770.</ref>. Il soulève d'autres questions comme la [[loi de réciprocité quadratique]] en [[1782]]. Là encore, et malgré une tentative d'[[Adrien-Marie Legendre]]<ref name="LegendreThéoNomb">Legendre, ''Théorie des nombres'', Paris, Duprat, 1798 ; Firmin Didot {{3e}} éd., 1830.</ref>, la solution reste hors de portée.

Jusqu'à l'aube du {{s-|XIX}} les méthodes utilisées, si elles dénotent une grande astuce chez les mathématiciens, sont finalement peu nombreuses et de principes simples. L'exemple suivant, tiré du problème des deux carrés, en illustre trois : existe-t-il un nombre dont la division par quatre donne pour reste 3 et qui est somme de deux carrés ? Soit ''a''{{exp|2}} et ''b''{{exp|2}} ces deux carrés. Seul l'un est pair car sinon leur somme serait paire et sa division par 4 aurait 0 comme reste. Supposons ''a'' pair et ''b'' impair. ''a'' est pair donc son carré est un multiple de 4. L'entier ''b'' est impair donc s'écrit 2''c'' + 1, son carré est égal à 4''c''{{exp|2}} + 4''c'' + 1, la division de ''b''{{exp|2}} par quatre donne pour reste ''un'' et la somme des deux carrés donne aussi pour reste ''un''.

* Le premier outil utilisé est celui des nombres premiers, ce raisonnement est exact car 2 est un nombre premier.
* Le deuxième est la transformation algébrique, ''b'' est ''transformé'' en 2''c'' + 1. Utilisé avec virtuosité, il permet aux mathématiciens de l'époque de résoudre certaines équations diophantiennes. Toute l'astuce réside à choisir avec habileté les bonnes transformations.
* Le troisième est la [[division euclidienne]], les carrés et leur somme sont systématiquement divisés par 4.
* Le quatrième n'est pas illustré dans l'exemple, il correspond à la [[Méthode de descente infinie|descente infinie]] utilisée dans la [[Théorème des deux carrés de Fermat#Euler et la descente infinie|démonstration d'Euler]] du théorème des deux carrés. Elle consiste à trouver à partir d'une solution entière positive une autre solution entière positive et plus petite. La suite des solutions descend de manière infinie dans l'ensemble des entiers positifs, ce qui n'est pas possible. Cette méthode fut déjà utilisée par Fermat pour démontrer son [[Démonstrations du dernier théorème de Fermat#Cas où n est égal à quatre|grand théorème dans le cas où ''n'' est égal à 4]].

Le caractère rustique des outils se traduit par des démonstrations longues et techniques, comme la [[Théorème des deux carrés de Fermat#Euler et la descente infinie|preuve d'Euler pour le théorème des deux carrés]]. De plus, et malgré plus d'un siècle d'efforts, l'essentiel des équations diophantiennes résistent à une telle approche.

=== L'apport de Carl Friedrich Gauss ===
[[Fichier:Carl Friedrich Gauss.jpg|vignette|gauche|[[Carl Friedrich Gauss]] est le fondateur de la branche mathématique maintenant appelée ''arithmétique modulaire''.]]
À l'âge de 17 ans, [[Carl Friedrich Gauss|Gauss]] démontre la [[loi de réciprocité quadratique]]. Un an plus tard, le 30 mars 1796, il prend conscience que ses calculs arithmétiques permettent de [[construction à la règle et au compas|construire à la règle et au compas]] l'[[heptadécagone]], c'est-à-dire le polygone régulier à dix-sept côtés, problème resté ouvert depuis l'Antiquité. Enfin en [[1801]], il publie ''[[Disquisitiones arithmeticae]]'' (''Recherches arithmétiques'') et est surnommé le ''prince des mathématiciens''<ref>{{NaudinQuitté}}.</ref>.

Ces deux grandes découvertes procèdent d'une même démarche, la mise au point d'outils plus sophistiqués que ceux dont disposaient Fermat ou Euler, simplifiant les démonstrations au prix d'une abstraction plus grande. Sa démarche fonde l'arithmétique modulaire.

Elle est appliquée d'abord aux entiers puis aux polynômes puis à un nouvel ensemble d'entiers, maintenant appelés [[entier de Gauss|entiers de Gauss]].

Toutes les équations diophantiennes de Fermat sont maintenant résolues à l'exception de son grand théorème. De nouvelles conjectures apparaissent. Par exemple, si ''a'' et ''b'' sont [[nombres premiers entre eux|premiers entre eux]], la [[suite arithmétique]] de valeur initiale ''a'' et de raison ''b'' contient-elle des nombres premiers, si oui combien ? Gauss et d'autres mathématiciens comme Legendre ont bien imaginé qu'il en [[Existence (mathématiques)|existe]] une infinité mais ne parviennent pas à le démontrer. De même la loi de réciprocité quadratique doit posséder des équivalents pour les ordres supérieurs.

L'arithmétique modulaire est enrichie. Dirichlet, un élève de Gauss trouve une démonstration<ref>{{Article|nom=Dirichlet|titre=Recherches de diverses applications de l'analyse infinitésimale à la théorie des nombres|revue=[[Journal de Crelle]]|vol=19|année=1839}} et vol. 21, 1840.</ref> du [[théorème de la progression arithmétique]] en développant le concept des [[caractère de Dirichlet|caractères]] et en formalisant les bases de la [[théorie analytique des nombres]]. [[Charles Gustave Jacob Jacobi]] écrit, dans une lettre à son frère : {{Citation|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>{{Article|lang=de|nom={{Lien|lang=de|trad=Wilhelm Ahrens (Mathematiker)|Wilhelm Ahrens}}|titre=Briefwechsel zwischen C. G. J. Jacobi und M. H. Jacobi|revue=The Mathematical Gazette|vol=4|numéro=71|année=1908|p.=269-270}}.</ref> Dirichlet n'est pas le premier à utiliser des outils qui sont maintenant qualifiés de conséquence de l'[[analyse harmonique sur un groupe abélien fini]]. Legendre, pour tenter de démontrer la loi de réciprocité quadratique, développa des calculs similaires<ref name="LegendreThéoNomb"/> sur les [[nombre réel|réels]], formalisant ce qui est maintenant appelé le [[symbole de Legendre]]. Gauss enfin généralise cette approche aux [[nombre complexe|nombres complexes]] dans son livre de 1801. Ses calculs portent le nom de [[somme de Gauss]] et [[période de Gauss]].

Au {{s-|XIX}}, ces mathématiques sont dénommées ''arithmétique transcendante''<ref>{{Article|lien auteur=Gotthold Eisenstein|prénom=Gotthold|nom=Eisenstein|titre=Application de l'Algèbre à l'Arithmétique transcendante|revue=Journal de Crelle|vol=29|année=1845|passage=177-184|url=http://www.digizeitschriften.de/dms/img/?PPN=PPN243919689_0029&DMDID=dmdlog12}}.</ref>. Si le terme d'[[arithmétique]] reste largement usité, Legendre considère, en [[1830 en science|1830]], cette branche comme suffisamment développée pour mériter le terme de [[théorie des nombres]]<ref name="LegendreThéoNomb"/>. L'apparition de nouvelles techniques, différentes de celles de Gauss, introduit une subdivision avec la [[théorie algébrique des nombres]] et la [[théorie analytique des nombres]]. Le terme d'''arithmétique transcendante'' tombe ensuite en désuétude.

=== {{s-|XX}} ===
==== Cryptologie ====
[[Image:Kerkhoffs.jpg|gauche|vignette|[[Auguste Kerckhoffs]] énonce un principe fondateur de la [[cryptologie]] moderne.]]
[[Image:Enigma.jpg|vignette|''[[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>{{Article|prénom=A.|nom=Kerckhoffs|titre=La cryptographie militaire|revue=Journal des sciences militaires|vol=IX|année=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>{{Article|lang=en|lien auteur=Claude Shannon|prénom=C.|nom=Shannon|url=http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|titre={{Lien|Communication Theory of Secrecy Systems}}|revue=[[Bell System Technical Journal|Bell Syst. Tech. J.]]|vol=28|année=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>{{Article|lang=en|prénom=H.|nom=Feistel|url=http://archive.wikiwix.com/cache/?url=http://www3.edgenet.net/dcowley/docs.html&title=lire|titre=Cryptography and Computer Privacy|lien périodique=Scientific American|revue=Scientific American|vol=228|numéro=5|année=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>{{Article|lang=en|lien auteur=Don Coppersmith|prénom=Don|nom=Coppersmith|url=http://archive.wikiwix.com/cache/?url=http://www.research.ibm.com/journal/rd/383/coppersmith.pdf&title=lire|titre=The data encryption standard (DES) and its strength against attacks|revue=IBM Journal of Research and Development|vol=38|numéro=3|année=1994|p.=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">{{Article|lang=en|lien auteur1=Whitfield Diffie|prénom=Whitfield|nom=Diffie|lien auteur2=Martin Hellman|prénom2=Martin|nom2=Hellman|url=http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/diffie-hellman.pdf|titre=New directions in cryptography|revue=IEEE Trans. Inf. Theory|vol=22|numéro=6|année=1976|p.=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>{{Article|lang=en|lien auteur1=Ronald Rivest|nom1=Rivest|lien auteur2=Adi Shamir|nom2=Shamir|lien auteur3=Leonard Adleman|nom3=Adleman|url=http://people.csail.mit.edu/rivest/Rsapaper.pdf|titre=A Method for Obtaining Digital Signatures and Public-Key Cryptosystems|lien périodique=Communications of the ACM|revue=Communications of the ACM|vol=21|numéro=2|année=1978|p.=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 {{ISBN|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>.

==== Théorie de l'information ====
{{Article détaillé|Théorie de l'information}}
[[Image:P-MMX.JPG|droite|vignette|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>{{Article|lang=en|nom=Shannon|titre=A Mathematical Theory of Communications|revue=Bell Syst. Tech. J.|vol=27|année=1948|p.=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>{{Article|lang=en|prénom=R.|nom=Hamming|titre=Error Detecting and Correcting Codes|revue=Bell Syst. Tech. J.|vol=29|année=1950|p.=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>{{Article|lang=en|nom1=[[Raj Chandra Bose]]|nom2={{Lien|D. K. Ray-Chaudhuri}}|titre=On a class of error-correcting. Binary group codes|revue=Inform. Control|vol=3|année=1960|p.=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 Education|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.

== Outils de l'arithmétique modulaire ==
=== Congruences sur les entiers ===
{{Article détaillé|Congruence sur les entiers}}
L'exemple historique de l'« arithmétique modulaire » repose sur les [[entier relatif|nombres entiers]]. Un entier ''n'' étant fixé, le calcul modulo ''n'' consiste à identifier tous les entiers à leur reste dans la division euclidienne par ''n'' ; ceci peut être illustré par l'exemple de l'« arithmétique de l'horloge », qui correspond à ''n=12'' : la petite aiguille se trouve dans la même position à deux moments éloignés de douze heures, on identifie par exemple 13 h à 1 h. Pour obtenir un calcul sur un tel ensemble, on vérifie que l'addition et la multiplication sont compatibles avec les identifications. Cette formalisation<ref>Legendre, ''Recherches d'Analyse Indéterminée'' dans ''Hist. Acad. Roy. des Sciences'' (1785/1788).</ref> est l'œuvre de Legendre, qui donne le nom de ''résidu'' aux différents éléments.

L'apport de Gauss consiste à analyser la structure de cet ensemble, maintenant qualifié du nom d'[[anneau unitaire|anneau]] de [[congruence sur les entiers|congruences]] et noté [[anneau Z/nZ|ℤ/''n''ℤ]]. Elle se divise en premier lieu en l'étude de l'addition, qui définit un [[groupe cyclique]] de générateur ''1'' ; puis de la multiplication, qui dépend des propriétés du modulo. Si celui-ci est [[nombre premier|premier]], on obtient un [[corps commutatif|corps]]. Cette approche simplifie les démonstrations arithmétiques. Les deux exemples historiques du livre ''Disquisitiones arithmeticae'' sont le [[théorème de Wilson]]<ref>{{harvsp|Gauss|1801|p=56}}.</ref> et le [[démonstrations du petit théorème de Fermat|petit théorème de Fermat]]<ref>{{harvsp|Gauss|1801|p=34}}.</ref>.

Le calcul modulaire, dans le cas où le modulo n'est pas premier, est plus complexe, mais le [[théorème des restes chinois]] permet d'en élucider la structure. L'anneau n'est alors pas [[anneau intègre|intègre]] et il existe des [[diviseur de zéro|diviseurs de zéro]], ce sont des nombres qui, multipliés par un certain autre nombre non nul, donnent zéro. Le nombre d'éléments inversibles est donné par la [[indicatrice d'Euler|fonction indicatrice d'Euler]]. Elle permet, par exemple, de [[Petit théorème de Fermat|généraliser le petit théorème de Fermat]].

=== Résidus et polynômes ===
{{Article détaillé|Polynôme cyclotomique}}
[[Image:Heptadecagone.jpg|vignette|droite|Figure [[construction à la règle et au compas|à la règle et au compas]]: l'[[heptadécagone]], un polygone régulier de 17 côtés, mis en évidence avec les techniques de l'arithmétique modulaire.]]
Gauss remarque que l'ensemble des polynômes à coefficients [[nombre rationnel|rationnels]] peut se voir appliquer la logique du calcul modulaire, puisqu'il dispose d'une addition, d'une multiplication, et d'une [[Division euclidienne#Division euclidienne dans l'ensemble des polynômes|division euclidienne]]. Les congruences sont les restes de la division euclidienne des polynômes par un polynôme donné.

Il applique cette approche au polynôme ''X<sup>n</sup> ''– 1 et trouve sa [[Factorisation des polynômes|décomposition en produit de facteurs irréductibles]], qui prennent le nom de ''polynôme cyclotomique''. Gauss utilise ces résultats pour trouver une [[construction à la règle et au compas]] de l'[[heptadécagone]], polygone régulier à 17 côtés.

Il hésite à considérer ces travaux comme de l'arithmétique ; il écrit :« 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 »<ref>{{harvsp|Gauss|1801|p=XV}}.</ref>. La logique de cet argument est toujours d'actualité.

=== Entiers algébriques ===
{{Article détaillé|Entier de Gauss}}

Le cas des polynômes à coefficients entiers diffère : la propriété de division ne fonctionne que pour des polynômes dont le plus grand coefficient est égal à ''plus ou moins un''. Le cas des moduli du polynôme ''X''{{exp|2}} + 1 est envisagé : la structure modulaire obtenue est encore celle d'un anneau, s'identifiant à l'ensemble des nombres de la forme α + {{math|i}}β où α et β sont des entiers et {{math|i}} désigne l'[[unité imaginaire]], correspondant au monôme ''X''. Cet ensemble est celui des entiers de Gauss.

[[Fichier:Entier de Gauss division.jpg|vignette|droite|Illustration de la [[division euclidienne]] pour les [[entier de Gauss|entiers de Gauss]]]]
[[Fichier:Fermat deux carrés.jpg|vignette|gauche|Illustration de la [[théorème des deux carrés de Fermat|démonstration du théorème des deux carrés]] par les [[entier de Gauss|entiers de Gauss]]]]

Il peut être muni d'une [[Norme (arithmétique)|norme]]. À l'entier de Gauss ''a'' = α + {{math|i}}β est associée la norme α{{exp|2}} + β{{exp|2}}, qui provient du [[module d'un nombre complexe|module des nombres complexes]]. Cette norme permet de définir une [[division euclidienne]], comme l'illustre la figure de droite. Les entiers sont représentés par les intersections du quadrillage. La valeur ''a''/''b'' existe si ''b'' est différent de zéro, cependant cette valeur n'est pas nécessairement un entier de Gauss. Elle est représentée par le point noir de la figure. Dire qu'une division euclidienne existe, revient à dire qu'il existe un entier de Gauss à une norme strictement inférieure à ''un'' de ce point noir. L'illustration montre que, dans le cas présent, il existe au moins trois candidats. Dans le cas général, il en existe entre un et quatre et dans ce contexte seule l'existence compte.

Ce résultat de division euclidienne implique des propriétés sur cet anneau d'entiers : l'[[Théorème de Bachet-Bézout|identité de Bézout]], l'existence de [[nombre premier de Gauss|nombres premiers de Gauss]] et un analogue du [[théorème fondamental de l'arithmétique]]. Ces nombres premiers permettent à [[Richard Dedekind]] de proposer une [[Théorème des deux carrés de Fermat#Fermat et les résidus|résolution simple]] du théorème des deux carrés. L'illustration géométrique est donnée sur la figure de gauche. Un nombre premier ''p'' s'exprime comme somme de deux carrés si le cercle de rayon la racine de ''p'' croise au moins un entier Gauss.

[[Gotthold Eisenstein]], qui rencontre Gauss en 1844<ref>Voir par exemple {{MacTutor|id=Eisenstein|title=Ferdinand Gotthold Max Eisenstein}}.</ref>, découvre un nouvel [[Entier d'Eisenstein|anneau d'entiers]]<ref>{{en}} [[André Weil]], ''Elliptic Functions according to Eisenstein and Kronecker'', Springer, 1999 {{ISBN|978-354065036-2}}.</ref> ; l'arithmétique sur cet anneau offre une [[Démonstrations du dernier théorème de Fermat#Cas où n est égal à trois|démonstration rigoureuse du grand théorème de Fermat pour ''n'' égal à trois]], justifiant, encore une fois, la nécessité théorique d'une telle généralisation de l'arithmétique modulaire.{{clr}}

=== Caractères de Dirichlet ===
{{Article détaillé|Caractère de Dirichlet}}

[[Image:Dirichlet.jpg|vignette|droite|[[Johann Peter Gustav Lejeune Dirichlet|Peter Dirichlet]] développe l'essentiel de la théorie dans le cadre de l'[[Anneau Z/nZ|anneau ℤ/''n''ℤ]].]]

Dirichlet s'intéresse aux nombres premiers de la forme ''n'' + λ''m'' où ''n'' et ''m'' sont deux entiers [[Nombres premiers entre eux|premiers entre eux]] et λ une variable qui décrit l'ensemble des entiers positifs. Il souhaite en effet démontrer qu'il existe une infinité de nombres premiers de cette nature.

L'arithmétique modulaire est un bon outil pour cette problématique, qui est équivalente à trouver le [[Nombre cardinal|cardinal]] de l'ensemble des nombres premiers dans une classe de modulo.

Dirichlet considère le groupe des éléments inversibles modulo ''m'', et étudie l'ensemble des [[Homomorphisme de groupes|fonctions du groupe]] dans les [[nombre complexe|nombres complexes]] non nuls qui vérifient, pour ''a'' et ''b'' deux éléments de ce groupe, ''f''(''ab'') = ''f''(''a'')''f''(''b''). De telles fonctions sont appelées caractères de Dirichlet. Il en existe φ(''n''), le produit de deux caractères est encore un caractère, et leur table de multiplication est [[isomorphisme|exactement la même]] que celle du [[groupe des unités]] étudié.

Les calculs sur ces fonctions sont formellement analogues à ceux réalisés précédemment par [[Joseph Fourier]]<ref>{{Article|nom=Fourier|titre=Mémoire sur la propagation de la Chaleur dans les corps solides|revue=Nouveau Bulletin des sciences par la Société philomathique de Paris|vol=6|année=1807|p.=112-116}}.</ref>. Il faut néanmoins atteindre le {{s-|XX}} pour voir apparaître une théorie unifiant les deux approches. Elle prend le nom d'[[Analyse harmonique (mathématiques)|analyse harmonique]].

== Développements théoriques ==
Il est fréquent que des concepts mathématiques, développés dans un contexte, soient réutilisés dans d'autres domaines. Ainsi la [[Groupe (mathématiques)|théorie des groupes]] s'applique à l'[[arithmétique]] et à la [[géométrie]]. Il en est de même pour les outils de l'arithmétique modulaire, dont les outils alimentent de vastes champs des [[mathématiques pures]], comme l'[[algèbre|algèbre générale]] ou la [[théorie de Galois]]. Ces théories ne sont néanmoins pas considérées comme des cas particuliers d'arithmétique modulaire car elles font aussi appel à de nombreux autres concepts.

=== Structures quotient ===
{{Article détaillé|Relation d'équivalence}}
En langage moderne, l'arithmétique modulaire se formalise par la notion de quotient d'[[anneau euclidien|anneaux euclidiens]]. Le concept de [[relation d'équivalence]] permet de généraliser ce concept aux principales [[structure (mathématiques)|structures]] [[structure algébrique|algébriques]]. Par exemple, le [[groupe quotient|quotient]] d'un [[groupe (mathématiques)|groupe]] par un [[sous-groupe normal]] est, à travers le [[théorème de Jordan-Hölder]], un outil de base de la classification des [[Groupe fini|groupes finis]]. Les groupes quotients sont aussi utilisés en [[topologie algébrique]] pour classifier les [[variété (géométrie)|variétés]]. Dans la [[théorie des anneaux]], la notion d'[[idéal]] joue un rôle analogue à celui de la notion de sous-groupe normal en théorie des groupes. Elle permet de construire des [[anneau quotient|anneaux quotients]] dans un contexte plus général que celui de l'arithmétique modulaire. Le [[théorème des zéros de Hilbert]], base du lien entre l'[[algèbre commutative]] et la [[géométrie algébrique]], s'exprime en termes d'idéal.

Les termes de congruence et de modulo sont néanmoins réservés aux quotients sur un anneau euclidien.

=== Résidus de polynômes et théorie de Galois ===
{{Article détaillé|Arithmétique des polynômes|Théorie de Galois}}
[[Fichier:Evariste galois.jpg|vignette|droite|[[Évariste Galois]] est le fondateur de la théorie portant maintenant son nom.]]

Les idées de l'arithmétique modulaire s'appliquent à l'anneau des polynômes à coefficients dans un [[corps commutatif]], car cette structure dispose d'une [[division d'un polynôme|division]]. Elle est le point de départ de la [[théorie de Galois|théorie]] d'[[Évariste Galois]] et consiste en l'étude systématique<ref>{{Article|nom=Galois|titre=Sur les conditions de résolubilité des équations algébriques|lien périodique=Journal de mathématiques pures et appliquées|revue=Journal de Liouville|année=1846}}.</ref> des ensembles de congruence de [[Polynôme formel|polynômes]] modulo un [[arithmétique des polynômes|polynôme irréductible]], l'équivalent des nombres premiers. Ces ensembles sont maintenant appelés [[extension algébrique|extensions algébriques]].

Ces extensions permettent l'analyse de la résolubilité des [[Équation polynomiale|équations algébriques]], c'est-à-dire des équations s'écrivant sous forme polynomiale. Si le polynôme est irréductible, son ensemble de congruences est le plus petit corps contenant au moins une [[Racine d'un polynôme|racine]]. Il est appelé [[corps de rupture]]. En réitérant ce processus, un corps contenant toutes les racines, le [[corps de décomposition]], est construit. La logique modulaire du quotient fournit la structure algébrique adaptée à cette problématique.

La théorie de Galois fait appel à bien d'autres notions. L'étude de la résolubilité de l'équation est possible ''via'' l'étude du groupe des [[automorphisme]]s du corps, appelé [[groupe de Galois]], grâce à la [[correspondance de Galois]] entre sous-corps et sous-groupes. Au-delà de l'étude de la résolubilité des équations algébriques, la théorie de Galois est devenue un cadre naturel de résolution de nombreux problèmes en arithmétique, [[géométrie arithmétique]] ou [[géométrie algébrique]], et permet surtout de formuler de nouveaux problèmes plus généraux dans ces divers domaines.

Si cette théorie utilise le concept de quotient d'un anneau euclidien, la variété d'outils spécifiques à ce domaine en fait un champ propre, bien distinct du sujet de cet article. L'un des fruits de cette théorie, les [[corps fini]]s, encore appelés corps de Galois, fournissent un cadre naturel à de nombreuses applications en arithmétique modulaire.

=== Entiers algébriques et théorie algébrique des nombres ===
{{Article détaillé|Théorie algébrique des nombres}}
[[Fichier:Ernst Eduard Kummer.jpg|vignette|droite|[[Ernst Kummer]] démontre le [[dernier théorème de Fermat]] pour de nombreuses valeurs de ''n'' et fonde la théorie algébrique des nombres.]]
L'arithmétique modulaire offre un bon cadre conceptuel pour la résolution du grand théorème de Fermat. Cependant, les anneaux d'[[entier algébrique|entiers algébriques]], construits selon la méthode de Gauss, présentent ce que Dirichlet appelle une ''obstruction''. Il montre que le [[groupe des unités]] de cet anneau, c'est-à-dire des éléments ayant un inverse pour la multiplication, n'est plus un [[groupe cyclique]] ou [[groupe abélien fini|abélien fini]] comme celui qu'étudiait Gauss. Il contient aussi des copies de l'anneau des entiers et est donc infini. Ce résultat prend le nom de [[théorème des unités de Dirichlet]]. L'obstruction provient de cette nouvelle configuration. Elle empêche l'application des techniques modulaires utilisées pour les entiers de Gauss car l'anneau associé n'est plus euclidien.

[[Ernst Kummer]] utilise un outil lié à la généralisation du quotient maintenant formalisé par les idéaux. Ils ''remplacent'' les nombres premiers absents. La théorie algébrique des nombres prend alors le relais, avec des techniques différentes. L'outil de base est un anneau dont les éléments sont appelés [[entier algébrique|entiers algébriques]] et qui possède une structure dite d'[[anneau de Dedekind]]. Kummer parvient ainsi à démontrer<ref>{{Article|nom=Kummer|titre=Sur la théorie des nombres complexes|lien périodique=CRAS|revue=CRAS|année=1847}}.</ref> le grand théorème pour certaines valeurs de ''n'' premier, c'est-à-dire pour les [[nombre premier régulier|nombres premiers réguliers]]. Les seules valeurs inférieures à 100 non traitées sont 37, 59 et 67.

D'autres outils et objets d'étude apparaissent, comme l'[[anneau adélique]], ceux de la théorie de Galois, les [[courbe elliptique|courbes elliptiques]], les [[série L de Dirichlet|séries L de Dirichlet]] ou les [[forme modulaire|formes modulaires]]. Certains proviennent de conséquences presque directes de l'arithmétique modulaire, comme les corps finis, utilisés de manière intensive au {{s-|XX}}. La théorie algébrique des nombres est largement plus vaste que le cadre de l'arithmétique modulaire, tout en reposant ''in fine'' sur des techniques parfois similaires.

=== Caractères de Dirichlet et théorie analytique des nombres ===
{{Article détaillé|Théorie analytique des nombres}}
[[Fichier:Riemann zeta function absolute value.png|vignette|gauche|Représentation du [[Module d'un nombre complexe|module]] de la [[fonction zêta de Riemann]].]]
[[Fichier:Georg Friedrich Bernhard Riemann.jpeg|vignette|droite|[[Bernhard Riemann]] émet l'hypothèse de localisation des racines de la [[Fonction zêta de Riemann|fonction ζ (zêta)]].]]
La découverte par Euler d'un [[produit eulérien|produit]] infini, construit à l'aide de nombres premiers et égal à <math>\pi^2/6</math>ouvre la voie à une approche différente pour la compréhension des nombres. Dirichlet l'utilise pour démontrer que chacun des moduli d'entiers du groupe des unités contient une infinité de nombres premiers. Ce résultat porte maintenant le nom de [[théorème de la progression arithmétique]].

Pour mener à bien sa démonstration, Dirichlet développe un outil spécifique, les [[série L de Dirichlet|séries L de Dirichlet]]. L'une de ses séries correspond à une célèbre fonction qui prendra le nom de [[fonction zêta de Riemann|ζ (zêta) de Riemann]]. Sa plus grande difficulté consiste à prouver que ses fonctions n'ont pas de [[Racine d'un nombre|racine]] au point ''un''. Pour y parvenir, il utilise l'[[Analyse harmonique sur un groupe abélien fini|analyse harmonique]] sur le groupe des unités d'une classe de modulo<ref>{{Article|lang=en|nom={{Lien|Allen Lowell Shields|texte=Allen Shields}}|titre=Lejeune Dirichlet and the birth of analytic number theory : 1837-1839|lien périodique=The Mathematical Intelligencer|revue=The Mathematical Intelligencer|vol=11|année=1989|p.=7-11}}.</ref>.

Néanmoins, une fois encore, l'arithmétique modulaire est insuffisante pour venir à bout du théorème. Dirichlet utilise de nombreuses techniques analytiques, comme les [[Série entière|séries entières]] et l'[[analyse complexe]]. Le fruit de ces travaux donne naissance à une nouvelle branche des mathématiques : la théorie analytique des nombres. L'un des points cruciaux de cette théorie provient de l'unique article de [[Bernhard Riemann]] en théorie des nombres : ''[[Sur le nombre de nombres premiers inférieurs à une taille donnée]]''. Il conjecture une localisation des racines de sa fonction ζ. La recherche de la position des racines, initiée par Dirichlet, devient une préoccupation centrale et reste l'une des conjectures pressenties comme les plus difficiles des mathématiques de notre époque<ref>{{harvsp|Delahaye|2000|p=222-224}}.</ref>.{{clr}}

== Cryptographie ==
{{Article détaillé|Cryptographie}}
[[Image:PhishingTrustedBank.png|droite|vignette|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 la 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 (informaticien)|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.

=== Cryptographie asymétrique ===
{{Article détaillé|Cryptographie asymétrique}}
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|langue=en|auteur1=[[Alfred Menezes]]|auteur2={{Lien|Paul van Oorschot}}|auteur3=[[Scott Vanstone]]|titre=Handbook of Applied Cryptography|lieu=Boca Raton|éditeur=[[CRC Press]]|année=1996|mois=10|pages totales=780|isbn=978-0-8493-8523-0|isbn10=0-8493-8523-7|bnf=37515673|lire en ligne=http://cacr.uwaterloo.ca/hac/about/chap8.pdf|numéro chapitre=8|passage=287}}.</ref>.

Les messages sont des entiers strictement 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''<ref>{{Harvsp|Menezes, van Oorschot et Vanstone 1996|loc=[http://cacr.uwaterloo.ca/hac/about/chap3.pdf chap. 3], section 3.2}} : ''The integer factorisation problem''.</ref>. 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'')<ref>{{Harvsp|Menezes, van Oorschot et Vanstone 1996|loc=chap. 3, section 3.3}} : ''The RSA problem''.</ref>.

=== Cryptographie symétrique ===
{{Article détaillé|Cryptographie symétrique}}

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.

=== Tests de primalité ===
{{Article détaillé|Test de primalité}}
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.is/raNDQ|titre=RSA : Le plus connu des algorithmes asymétriques|année=2003|site=Cryptosec |consulté le=21 septembre 2014}}, 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}}.

=== Décomposition en produit de facteurs premiers ===
{{Article détaillé|Décomposition en produit de facteurs premiers}}
La [[sécurité par l'obscurité]] n'est pas de mise pour les codes RSA. Il est important de connaître précisément l'état de l'art de la décomposition des entiers en termes de facteurs premiers. Un concours appelé [[compétition de factorisation RSA]] fut ouvert jusqu'en mai 2007, proposant un prix pour quiconque capable de factoriser un nombre choisi dans une liste rendue publique.

Le crible d'Ératosthène est un test de primalité qui offre une méthode de décomposition. Mais une fois encore, il n'est pas applicable pour de grands nombres car trop lent<ref>{{harvsp|Delahaye|2000|p=215}}.</ref>.

Les différentes méthodes actuellement utilisées reposent souvent sur les [[résidu quadratique|résidus quadratiques]]<ref>{{harvsp|Delahaye|2000|p=302}}.</ref>. Un [[diviseur de zéro]] est un résidu quadratique contenant comme représentants au moins deux [[carré parfait|carrés parfaits]]. L'objectif est de trouver ces deux carrés. Cette approche est celle du [[crible quadratique]] et du [[crible algébrique]], le plus rapide connu en 2007<ref>{{Article|lang=en|lien auteur=Carl Pomerance|prénom=Carl|nom=Pomerance|url=http://www.ams.org/notices/199612/pomerance.pdf|titre=A Tale of Two Sieves|lien périodique=Notices of the American Mathematical Society|revue=Notices of the AMS|vol=43|année=1996|p.=1473-1485}}.</ref>. On peut encore citer l'[[algorithme rho de Pollard|algorithme ρ de Pollard]] qui utilise le [[paradoxe des anniversaires]].

=== Corps finis ===
{{Article détaillé|Corps fini}}
La construction par quotient des corps premiers ℤ/''p''ℤ se généralise à d'autres structures. En informatique, les nombres sont codés sur ''n'' [[bit]]s, c'est-à-dire qu'un nombre correspond à une suite de longueur ''n'' composée de 0 et de 1. Une telle suite peut être considérée comme un [[vecteur]] d'un [[espace vectoriel]] de [[dimension d'un espace vectoriel|dimension]] ''n'' sur le corps fini '''F'''<sub>2</sub> à deux éléments.

Cette structure est souvent considérée comme l'espace des polynômes à coefficients dans '''F'''<sub>2</sub> de degré strictement inférieur à ''n''. Pour garantir la stabilité de la multiplication, cet espace est quotienté par un polynôme de degré ''n''. Quand ce polynôme est irréductible (équivalent de nombre premier), la structure obtenue est le corps fini de cardinal 2<sup>''n''</sup>. Un nombre ''a'' modulo 2<sup>n</sup> et un polynôme ''P'' modulo un polynôme de degré ''n'' sont très semblables, ils s'écrivent en effet :
<center><math>a \ = \ \sum_{i=0}^{n-1} a_i2^i \quad et \quad P \ = \ \sum_{i=0}^{n-1} \alpha_iX^i \quad, \quad a_i,\alpha_i \in \mathbf F_2.</math></center>

Un exemple d'utilisation est la création d'un [[générateur de nombres pseudo-aléatoires]] dans '''F'''<sub>2</sub>. De tels générateurs sont utilisés par exemple, dans le contexte d'une communication orale par [[Téléphone mobile|téléphone portable]], par le [[chiffrement de flux]]<ref>{{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]]. Celui-ci a pour composants des [[registre à décalage à rétroaction linéaire|registres à décalage à rétroaction linéaire]], ou LFSR (acronyme de ''{{lang|en|linear feedback shift register}}''). Étant données deux suites finies d'éléments de '''F'''<sub>2</sub> de longueur ''n'', une suite de coefficients et une séquence d'initialisation, soient :
<center><math>(c_1, \dots, c_n)</math> et <math>(u_0,\dots, u_{n-1}).</math></center>
Un LFSR fournit une suite pseudo-aléatoire (''u''<sub>''j''</sub>), obtenue par [[suite récurrente linéaire|récurrence linéaire]] :
<center><math>u_j \ = \ \sum_{i=1}^n c_iu_{j-i}\quad (j\geq n).</math></center>
La suite des coefficients est souvent fixe. La clé fournit alors la séquence d'initialisation, qui peut être représentée par un entier ''a'' modulo 2<sup>''n''</sup> :
<center><math>a \ = \ \sum_{i=0}^{n-1} u_i2^i.</math></center>
La suite obtenue est périodique, cependant si la suite des coefficients est bien choisie, la période est très longue : 2<sup>''n''</sup> – 1. Cette situation se produit si le ''polynôme de rétroaction'' ''R'', donnée par la formule suivante, est le [[polynôme minimal d'un nombre algébrique|polynôme minimal]] d'un [[groupe cyclique|élément primitif]] du [[groupe cyclique]] ('''F'''<sub>2<sup>n</sup></sub>)* :
<center><math>R \ = \ 1-\sum_{i=1}^nc_i X^i.</math></center>

=== Analyse harmonique sur un groupe abélien fini ===
{{Article détaillé|Analyse harmonique sur un groupe abélien fini}}

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'' = {{formatnum:16384}} · ''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<ref>{{harvsp|Singh|2001|p=345}}.</ref> 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.

== Codes correcteurs ==
{{Article détaillé|Code correcteur}}
[[Fichier:CD autolev crop.jpg|vignette|gauche|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]].}}

=== Somme de contrôle ===
{{Article détaillé|Somme de contrôle}}
[[Fichier:Bit de parité.jpg|vignette|droite|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.

=== Codes cycliques ===
{{Article détaillé|Code cyclique}}
[[Fichier:Code correcteur parfait.svg|vignette|gauche|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]].

=== [[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>{{Article|lang=de|prénom=Michael|nom=Klemm|titre=Über die Identität von MacWilliams für die Gewichtsfunktion von Codes|revue=Archiv der Mathematik|vol=49|numéro=5|année=1987|p.=400-406|url=https://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 {{ISBN|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]].

== Voir aussi ==
* [[Réduction de Montgomery]]

== Notes et références ==
=== Notes ===
{{Références}}

=== Liens externes ===
{{Autres projets|wiktionary=arithmétique modulaire}}
* {{Dictionnaires}}
* 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]])

=== Références ===
* {{Ouvrage|prénom1=Carl Friedrich|nom1=Gauss|lien auteur1=Carl Friedrich Gauss|traducteur=[[Antoine Charles Marcelin Poullet-Delisle]], éd. Courcier, 1807|titre=Recherches arithmétiques|titre original=[[Disquisitiones arithmeticae]]|année=1801|isbn=}}
* {{Merveilleux nombres premiers}}
* {{Lang1}}
* [[Simon Singh]], ''Le Dernier Théorème de Fermat'', [[Hachette Livre]] Littérature, 1999 {{ISBN|9782709618540}}
* {{Ouvrage|prénom1=Simon|nom1=Singh|titre=[[Histoire des codes secrets]]|sous-titre=de l'Égypte des Pharaons à l'ordinateur quantique|éditeur=Poche|année=2001|pages totales=504|isbn=978-2-253-15097-8}}
* Gilles Zémor, ''Cours de cryptographie'', Cassini, 2000 {{ISBN|9782842250201}}
* {{Demazure1}}
* {{en}} {{Lien|langue=en|fr=Gavin Flood}}, ''The Blackwell Companion to Hinduism'', [[Blackwell Publishing]], 2005 {{ISBN|9781405132510}}
* {{en}} [[Michael Sean Mahoney]], ''The Mathematical Career of Pierre De Fermat, 1601-1665'', [[Princeton University Press]], {{2e}} éd., 1994 {{ISBN|978-0-691-03666-3}}
* {{en}} {{Lien|langue=de|fr=Waldo Dunnington}}, ''Carl Friedrich Gauss: Titan of Science'', [[Mathematical Association of America]], 2003 {{ISBN|0-8838-5547-X}}

{{Portail|informatique|arithmétique}}
{{Article de qualité|oldid=21967725|date=20 octobre 2007}}

[[Catégorie:Arithmétique modulaire]]