Arithmétique modulaire

Infos
Recherches arithmétiques de Gauss, livre fondateur de l'arithmétique modulaire En mathématiques et plus précisément en théorie algébrique des nombres, 'arithmétique modulaire' est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l'étude du reste obtenu par une division euclidienne. Si ses origines remontent à l'antiquité, les historiens associent généralement sa naissance à l'année 1801, date de la publicat
Arithmétique modulaire

Recherches arithmétiques de Gauss, livre fondateur de l'arithmétique modulaire En mathématiques et plus précisément en théorie algébrique des nombres, 'arithmétique modulaire' est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l'étude du reste obtenu par une division euclidienne. Si ses origines remontent à l'antiquité, les historiens associent généralement sa naissance à l'année 1801, date de la publication du livre Disquisitiones arithmeticaeCarl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier 1807 de Carl Friedrich Gauss (1777 - 1855). Sa nouvelle approche permet d'établir de célèbres conjecturesPar exemple la loi de réciprocité quadratique page 96 ou la construction à la règle et au compas de l'heptadécagone page 429 à 489 des Recherches arithmétiques et simplifie les démonstrations d'importants résultatsOn peut citer le théorème de Wilson page 56 ou le petit théorème de Fermat page 50 des Recherches arithmétiques, au prix d'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 modifie le statut de l'arithmétique modulaire. D'une part, d'autres méthodes sont nécessaires pour progresser en théorie des nombres. D'autre part, le développement de nombreuses applications industrielles impose la mise au point d'algorithmes issus des techniques modulaires. Ils résolvent essentiellement des questions soulevées par la théorie de l'information. Cette branche est maintenant surtout considérée comme des mathématiques appliquées. L'article congruence sur les entiers propose une introduction plus mathématique, anneau Z/nZ traite le même sujet de manière moins didactique et plus exhaustive.

Usages

En mathématiques pures, ce terme est très peu utilisé. Le vocable proche le plus fréquent est théorie algébrique des nombres, qui désigne un domaine plus large, contenant par exemple les notions d'entiers algébriques ou de théorie de GaloisA. Fröhlich, Galois Module structure of Algebraic integers, Springer-Verlag, Berlin, 1983.. 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 algorithmes entrent dans ce champ d'étude. On y trouve les tests de primalités, la décomposition en produit de facteurs premiersChantal David Université Concordia Quebec pp 11-17, l'utilisation des caractères d'un groupe par exemple pour la transformée de Fourier discrèteJ-M Muller J-C Bajard Calcul arithmétique des ordinateurs Traité Hermes CNRS 2004 pp 142-150 et pp 181-201 ou encore l'étude d'autres quotients que ceux des entiers, comme celui des polynômesPascal Giorgi Arithmétique modulaire entière en base polynomiale Séminaire de l'université de Perpignan 2005 . 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 modulaireThomas Plantard L'arithmétique modulaire pour la cryptographie Université de Montpelier 2005 , soit comme des applications, voire ne sont pas citées du tout. Sous sa forme simple, elle prend parfois le nom darithmétique de l'horlogeSimon Sing Histoire des codes secrets p 324-329. Le terme de système modulaire est utiliséP. Paillier Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor GEMPLUS, ENST Lecture notes in computer science Springer, Berlin 1973 pour désigner une arithmétique modulaire sur d'autres ensembles que les entiers.

Histoire

Origines

Couverture de l'édition de 1621 de Arithmetica de Diophante, traduite en latin par Claude-Gaspard Bachet de Méziriac. Au Euclide formalise, dans son livre les Éléments, les fondements de l'arithmétique. On y trouve le lemme portant son nom, une version datée du théorème fondamental de l'arithmétique et une étude sur les nombres parfaitsT L Heath The thirteen books of Euclid's Elements The Mathematical Gazette, Vol. 6, No. 92 pp. 98-101 Mai 1911 dans la proposition 36 de son livre IXEuclide . Diophante d'Alexandrie (env. 250Les dates de naissance et de mort de Diophante sont mal connues cf par Norbert Schappacher 2005) écrit Arithmetica contenant 130 équations. Il traite essentiellement de problèmes ayant une unique solution numérique et à valeur fractionnaire ou entière. On y trouve le fait que les nombres sommes de deux carrés parfaits ne sont jamais de la forme 4n
+ 3. Les équations, à coefficients entiers et dont les solutions recherchées sont entières prennent aujourd'hui le nom d'équations diophantiennes. La Chine développe parallèlement une arithmétique modulaire. Sun Zi écrit vers l'an 300 un traité de mathématiqueSun Zi Sunzi suanjing Manuel de mathématiques de Sun Zi vers 300 dont le problème 26 du chapitre 3 est le suivant : J.-C. Martzloff, Histoire des mathématiques chinoises, p. 129 Masson 1987. Alhazen découvre le théorème de Wilson dès le XIe siècle. Qin Jiushao (1202 - 1261) développe le théorème des restes chinoisQin Jiushao Shushu Jiuzhang, Traité de mathématique en neuf chapitres 1247. Son traité est remarquablement avancé, il traite d'un système d'équations linéaires de congruences dans le cas où les modulo ne sont pas premiers entre eux deux à deux. Ses travaux sur les systèmes de congruences dépassent en sophistication ceux de Leonhard Euler (1707 - 1783). On peut citer George Sarton pour qui : Ho Peng Yoke Li, Qi, and Shu An Introduction to Science and Civilization in China, p 89 Hong Kong University Press, 1985. Le 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 . 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édentesK. Chemla Similarities between chineese and arabic mathematical writings : (I) root extraction, Arabic science and Philosophy, 4, n° 2, p207 266 1994. L'Inde possède aussi une tradition forte en arithmétique. Âryabhata (476 - 550) recherche de manière systématiqueH-J Ilgauds, Aryabhata I, in H Wussing and W Arnold Biographien bedeutender Mathematiker Berlin 1983 les solutions entières de l'équation linéaire à deux inconnues à coefficients entiers. Il utilise pour cela un algorithme appelé publié dans son livreA. Keller Un commentaire indien du VIIe siècle Thèse de l'Université de Paris VII appelé Aryabhatiya. Les équations diophantiennes de degré deux sont étudiées par Brahmagupta (598 - 668) à l'aide de la méthode chakravalaS S Prakash Sarasvati A critical study of Brahmagupta and his works, Delhi 1986). La civilisation islamique joue un double rôle en arithmétique : elle véhicule le savoir acquis par les Grecs, Indiens, Chinois et EuropéensS Pines Studies in Arabic versions of Greek texts and in Medieval science, Leiden 1986, et elle apporte des connaissances nouvellesR Rashed Entre arithmétique et algèbre: Recherches sur l'histoire des mathématiques arabes, Paris 1984 notamment sur l'étude des propriétés de certaines catégories d'entiers, comme les nombres premiers, parfaits, amiables ou figurésL'âge d'or des sciences arabes p 69. Dans ce contexte, Qusta ibn Lûqâ réalise une traduction partielle de l'Arithmetica de Diophante d'Alexandrie à la fin du IXe siècle et Al-Hajjaj traduit à la même époque les Éléments d'EuclideJ L Berggren Episodes in the Mathematics of Medieval Islam pp 70-71 Springer 1986 ; son collègue al-Khuwārizmī (env 783 - env 850) écrit un livre sur la numération indienne. Si le livre est perdu, il reste connu par une traduction latine Algoritmi de numero IndorumJ N Crossley and A S Henry Thus spake al-Khwarizmi : a translation of the text of Cambridge University Library Historia Math. 17 (2) pp 103-131 1990. Thābit (836 - 901) étudie les nombres amicaux et les nombres parfaitsF J Carmody Thabit b. Qurra, Four Astronomical Tracts in Latin Berkeley 1941. Alhazen (965 - 1039) continue ses travaux sur les nombres parfaits et découvre le théorème de WilsonR. Rashed bn al-haytham et le théorème de Wilson, Archive for History of Exact Sciences Springer Berlin Vol 22 N° 4 pp 305-321 Déc 1980.

Apparition en Europe

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 (1581 - 1638) traduit le livre de Diophante en latin. Les questions soulevées intéressent les mathématiciens de l'époque, particulièrement les Français. Pierre de Fermat (1601 - 1665) propose un grand nombre d'énoncés, les trois plus célèbres étant probablement son grand théorème, son théorème des deux carrés et son petit théorème. La communauté scientifique se lance des défis sur ce sujet, ainsi Fermat demande : Il conclut par : Pierre de Fermat Correspondance 3 janvier 1657. Marin Mersenne (1588 - 1648) recherche des nombres premiers particuliers. Fermat lui écrit : Pierre de Fermat Correspondance Marin de Mersenne 25 Décembre 1640. Ces nombres sont maintenant appelés nombres de Fermat et sa phrase s'avère être l'unique conjecture fausse proposée par l'auteur. René Descartes (1596 - 1650) 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 x2 + 2
y2. 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 plaisans et delectables qui se font par les nombres, on peut citer encore la remarque de Fermat à propos de son grand théorème : Pierre de Fermat Remarques sur Diophante par Pierre Samuel fils de Fermat 1670 :
- Les problèmes posés sont difficiles. Malgré quelques succès comme l'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 : (la première preuve reconnue apparaîtra en 1994, 1995Andrew Wiles , Annals of Mathematics (
141) (3), 443-551 (1995)). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec : Pierre de Fermat Correspondance à Frénicle de Bessy 18 octobre 1640

Méthodes utilisées

Leonhard Euler, théoricien des nombres du , résoud plusieurs é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ésLeonhard Euler Correspondance à Goldbach 12 avril 1749. 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 fausseLeonhard Euler Algèbre 1770. Il soulève d'autre questions comme la loi de réciprocité quadratique en 1782. Là encore, et malgré une tentativeAdrien-Marie Legendre Théorie des nombres, Paris Duprat 1798 d'Adrien-Marie Legendre (1752 - 1833), la solution reste hors de portée. Jusqu'à l'aube du 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 trois et qui est somme de deux carrés ? Soit a 2 et b 2 ces deux carrés. Seul l'un est pair car sinon leur somme serait paire et sa division par 4 aurait soit 0 soit 2 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 à 4c 2 + 4c + 1, la division de b 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 descente infinie utilisée dans la 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. . Le caractère rustique des outils se traduit par des démonstrations longues et techniques, comme par exemple la 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

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 (1777-1855) démontreP. Naudin, C. Quitté, Algorithmique algébrique Masson 1992 la loi de réciprocité quadratique. Un an plus tard, le 30 mars 1796 il prend conscience que ses calculs arithmétiques permettent de construire à la règle et au compas l'heptadécagone, c'est-à-dire le polygone régulier à dix-sept cotés, problème resté ouvert depuis l'Antiquité. Enfin en 1801, il publie Disquisitiones arithmeticae (
Recherches arithmétiques en français) et est surnommé le prince des mathématiciens. 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 entiers de Gauss. Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) découvre un ensemble analogue, celui des entiers de Dirichlet. Il lui permet d'initier la preuve du théorème de Fermat pour n = 5 qu'il envoie à l'académie des sciences en 1825. Elle est analysée par Legendre qui met quelques mois pour la mener à bonne finDirichlet 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. 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 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ématicien comme Legendre ont bien imaginé qu'il en existe une infinité mais ne parvient 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émonstrationDirichlet Recherches de diverses applications de l'analyse infinitésimale à la théorie des nombres J. Reine Angew math. (19) 1839 ibid (21) 1840 du théorème de la progression arithmétique en développant le concept des caractères et en formalisant les bases de la théorie analytique des nombres. Son raisonnement est un joyau de l'arithmétique modulaire, C. G. J. Jacobi (1804 - 1851) écrit, dans une lettre à son frère : W. Ahrens Briefwechsel zwischen C. G. J. Jacobi und M. H. Jacobi The Mathematical Gazette, Vol. 4, No. 71 pp. 269-270, 1908 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 similairesAdrien-Marie Legendre Essai sur la théorie des nombres, Duprat, Paris 1798 sur les réels, formalisant ce qui est maintenant appelé le symbole de Legendre. Gauss enfin, généralise cette approche aux nombres complexes dans son livre de 1801. Ses calculs portent le nom de somme de Gauss et période de Gauss. Au , ces mathématiques sont dénommées arithmétique transcendanteFerdinand Eisenstein Application de l'Algèbre à l'Arithmétique transcendante, Journal de Crelle. Berlin 1845. Si le terme d'arithmétique reste largement usité, Legendre considère, en 1830, cette branche comme suffisamment développée pour mériter le terme de théorie des nombresAdrien-Marie Legendre Théorie des nombres, Firmin Didot 3 édition, 1830. L'apparition de nouvelles techniques, différentes de celle 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 avec l'apparition des nombres transcendants.

Cryptologie

Auguste Kerckhoffs énonce un principe fondateur de la cryptologie moderne. 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 de 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, Auguste Kerckhoffs (1835 - 1903) énonce que : Auguste Kerckhoffs La cryptographie militaire, Journal des sciences militaires, vol. IX, pp. 5–83 et pp. 161–191, 1883 . Cette approche est à l'origine d'une modification profonde de cette science. Au milieu du XXe siècle, elle devient une branche des mathématiques appliquéesClaude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, pp. 656-715, 1949. . Au début des années 1930, le bureau du chiffre polonais fait appel au mathématicien Marian Rejewski (1905 - 1980) pour percer le code du système 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 modulo de Gauss sur les nombres entiers. Le terme d'Alain Tapp Cryptographie Laboratoire d’informatique théorique et quantique Université de Montréal est utilisé pour décrire ces techniques. Durant les années 1970, Horst Feistel (1915 - 1990) développeHorst Feistel Cryptography and Computer Privacy Scientific American, Vol. 228, No. 5, 1973. un système à clé privée, le Data Encryption Standard ou DES, qui devient le standard des applications non classifiéesDon Coppersmith The data encryption standard (DES) and its strength against attacks, IBM Journal of Research and Development; 38(3), p 243–250 1994 . Les cryptanalystes du DES, et plus généralement des chiffrements symétriques, utiliseront des mathématiques issues des travaux de Dirichlet sur les caractères, dans le cadre d'un espace vectoriel sur un corps fini à deux éléments. En 1978 une nouvelle famille de codes est découverteWhitfield Diffie Martin Hellman New directions in cryptography, IEEE Trans. Inform. Theory, IT-22, 6, pp. 644-654 1976, fondée sur une clé publique. Des solutions industrielles sont rapidement développées, la plus célèbre est dénommée R.S.A.. Elle se fonde sur les travaux de Fermat et d'EulerR. Rivest, A. Shamir, L. Adleman. , Communications of the ACM, Vol. 21 (2), pp.120–126. 1978. Le terme est, dans ce contexte, utilisé pour décrireLaurent Bloch, Les systèmes d'exploitation des ordinateurs. Histoire, fonctionnement, enjeux, Vuibert, 2003, ISBN 2-7117-5322-2 non seulement la structure des modulo 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 chinois, le petit théorème de Fermat et sa généralisation par Euler. L'arithmétique modulaire est un domaine de recherche actif au début du . Une mise en œuvre efficace nécessite l'utilisation d'opérations sur des grands ensembles de modulo. L'approche de Gauss est utilisée sur des polynômes à coefficients dans un corps fini. L'arithmétique modulaire se généralise à d'autres ensembles que les quotients d'entiersThomas Plantard Arithmétique modulaire pour la cryptologie Thèse de l'Université de Montpellier II, 2005 , par exemple pour la cryptanalyse.

Théorie de l'information

Processeur Pentium contenant une unité arithmétique et logique fondé sur l'arithmétique modulaire La cryptographie n'est pas l'unique domaine utilisant le vocable . La fin de la Deuxième Guerre mondiale voit l'apparition d'une nouvelle science : la théorie de l'information. En 1948, sous l'impulsion de Claude Shannon (1916 - 2001), elle devientClaude Shannon A Mathematical Theory of Communications, Bell System Technical; Journal, vol. 27, pp. 379-423, 623-656 1948 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 (1915 - 1998) propose un premier algorithmeRichard Hamming Error Detecting and Correcting Codes, Bell System Tech. Jour., 29, 150-163 1950 dès 1950. Une fois encore, les modulo sur les entiers sont utilisés pour une des plus simples techniques de code : les sommes de contrôle. En 1960, de nouveaux codes plus puissants sont développésR. C. Bose and D. K. Ray-Chaudhuri On a class of error-correcting. binary group codes Inform. Control, vol. 3, pp. 68-79 1960, sur la base de polynômes à coefficients dans un corps fini. L'arithmétique utilisée prend souvent le nom de J. Velu Méthodes mathématiques pour l'informatique Dunod informatique 1987. L'informatique devient un sujet universitaire au début des années 1960. Les contraintes inhérentes à la structure des processeurs imposent la représentation des nombres sous forme d'une suite finie d'informations, justifiant l'utilisation des modulo. Le terme d' apparait souventJean Berstel, Jean-Éric Pin et Michel Pocchiola Mathématiques et informatique : exercices résolus, vol. 2 McGraw-Hill France, 1991, on y trouve même les 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

Congruence et les entiers

L'exemple historique de l' repose sur les 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', 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 formalisationAdrien-Marie Legendre Recherches d'Analyse Indéterminée Hist Acad Roy des Sciences (1785/1788) 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 de congruences et noté
Z/nZ. 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 premier, on obtient un corps. Cette approche simplifie les démonstrations arithmétiques. Les deux exemples historiques du livre Disquisitiones arithmeticae sont le théorème de WilsonCarl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p56 1807 et le petit théorème de FermatCarl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p 34 1807. Le calcul modulaire, dans le cas où le modulo n'est pas premier, est plus complexe. Le théorème des restes chinois permet d'élucider la structure. L'anneau n'est pas intègre, il existe des diviseurs de zéro, ce sont des nombres qui, multipliés par un certain autre nombre, donnent zéro. Le nombre d'éléments inversibles est en général donné par la fonction indicatrice d'Euler. Elle permet, par exemple, de généraliser le petit théorème de Fermat.

Résidu et polynôme

à la règle et au compas: Heptadécagone, un polygone régulier de 17 cotés, mis en évidence avec les techniques de l'arithmétique modulaire Gauss remarque que l'ensemble des polynômes à coefficients rationnels peut se voir appliquer la logique du calcul modulaire, puisqu'il dispose d'une addition, d'une multiplication, et d'une 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 n - 1 et trouve sa décomposition en produit de facteurs irréductibles, qui prennent le nom de polynôme cyclotomique. Gauss utilise ces résultats pour trouver un nouveau polygone régulier constructible à la règle et au compas l'heptadécagone. Il hésite à considérer ces travaux comme de l'arithmétique ; il écrit : Carl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p XV 1807. Le terme d'arithmétique « transcendante » de Gauss est maintenant remplacé par celui d'arithmétique « modulaire ». La logique de cet argument est toujours d'actualité.

Entier algébrique

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 modulo du polynôme X 2 + 1 est envisagé : la structure modulaire obtenue est encore celle d'un anneau, s'identifiant à l'ensemble des nombres de la forme α + i.β où α et β sont des entiers et i désigne le nombre imaginaire, correspondant au monôme X. Cet ensemble est celui des entiers de Gauss. Illustration de la division euclidienne pour les entiers de Gauss démonstration du théorème des deux carrés par les entiers de Gauss Il peut être muni d'une norme. À l'entier de Gauss a = α + i.β est associée la norme α2 + β2, qui provient du 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'identité de Bézout, l'existence de nombres premiers de Gauss et un analogue du théorème fondamental de l'arithmétique. Ces nombres premiers permettent à Richard Dedekind (1831-1916) de proposer une 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. Ferdinand Eisenstein (1823 1852), un élève de Gauss, découvre un nouvel anneau d'entiers ; l'arithmétique sur cet anneau offre une 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.

Caractère de Dirichlet

J. P. G. Lejeune Dirichlet développe l'essentiel de la théorie dans le cadre de l'anneau Z/nZ. symbole : premier exemple de caractère. Dirichlet s'intéresse aux nombres premiers de la forme n + λ
.mn et m sont deux entiers 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 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 fonctions du groupe dans les nombres complexes non nuls qui vérifient, si a et b sont deux résidus : f(a.b) = 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 exactement la même que celle du groupe des unités étudié. Les calculs sur ces fonctions sont formellement analogues à ceux réalisésJoseph Fourier Mémoire sur la propagation de la Chaleur dans les corps solides, Nouveau Bulletin des sciences par la Société philomathique de Paris No 6 p. 112-116 1807 précédemment par Joseph Fourier (1768 - 1830). Il faut néanmoins atteindre le pour voir apparaître une théorie unifiant les deux approches. Elle prend le nom d'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 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 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 à bien d'autres concepts.

Structure quotient

En langage moderne, l'arithmétique modulaire se formalise par la notion de quotient d'anneaux euclidiens. Le concept de relation d'équivalence permet de généraliser ce concept aux principales structures algébriques. Le quotient, d'un groupe par un sous-groupe normal, est, par exemple, un outil de base de la classification des groupes finis, à travers le théorème de Jordan-Hölder. Les groupes quotients sont aussi utilisés en topologie algébrique pour classifier les 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 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 terme 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

Évariste Galois est le fondateur de la théorie portant maintenant son nom. L'arithmétique modulaire s'applique à l'anneau des polynômes à coefficients dans un corps. Elle est le point de départ de la théorieEvariste Galois sur les conditions de résolubilité des équations algébriques 1846 Journal de Liouville d'Evariste Galois (1811 1832) et consiste en l'étude systématique des ensembles de modulo de polynômes irréductibles, l'équivalent des nombres premiers. Ces ensembles sont maintenant appelés extensions algébriques. Ces extensions permettent l'analyse de la résolubilité des équations algébriques, c'est-à-dire des équations s'écrivant sous forme polynomiale. Si le polynôme est irréductible, son ensemble de modulo est le plus petit corps contenant au moins une 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 automorphismes du corps, appelé groupe de Galois, grâce à la correspondance de Galois entres 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. Il est à noter que l'un des fruits de cette théorie : les corps finis, encore appelés corps de Galois, fournissent un cadre naturel à de nombreuses applications en arithmétique modulaire.

Entier algébrique et théorie algébrique des nombres

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, si n est plus grand que dix, les anneaux d'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 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 (1810 - 1893) 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 entiers algébriques et qui possède une structure dite d'anneau de Dedekind. Kummer parvient ainsi à démontrerErnst Kummer Sur la théorie des nombres complexes, Comptes Rendus des Séances de l'Académie des Sciences. Paris. 1847 le grand théorème pour certaines valeur de n premier, c'est-à-dire pour les 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 courbes elliptiques, les séries L de Dirichlet ou les 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 . 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ère de Dirichlet et théorie analytique des nombres

Représentation de la valeur absolue de la fonction Zeta de Riemann. Bernhard Riemann émet l'hypothèse de localisation des racines de la fonction ζ. La découverte par Euler d'un produit infini, construit à l'aide de nombres premiers et égal au sixième du carré de la surface d'un cercle de rayon un, ouvre la voie à une approche différente pour la compréhension des nombres. Dirichlet l'utilise pour démontrer que chacun des modulo 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éries L de Dirichlet. L'une de ses séries correspond à une célèbre fonction qui prendra le nom de ζ de Riemann. Sa plus grande difficulté consiste à prouver que ses fonctions n'ont pas de racine au point un. Pour y parvenir, il utilise l'analyse harmonique sur le groupe des unités d'une classe de modulo. 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é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 (1826 - 1866) en théorie des nombres : Sur le nombre de nombres premiers inférieurs à une grandeur donnée. Il conjecture une localisation des racines de sa fonction ζ. La recherche de la position des racines, initié par Dirichlet, devient une préoccupation centrale et reste l'une des conjectures pressenties comme les plus difficiles des mathématiques de notre époque (
2007).

Cryptographie

Le 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 confidentialité dans la transmission des messages et l'authentification de ceux-ci. 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 algorithme, c'est-à-dire une fonction f qui, à un message en clair m et une 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, exploite la difficulté pratique à inverser l'exponentiation modulaire. Cette dernière, ou ses généralisations à d'autres 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 crypotographe asymétrique, une clé différente s'avère nécessaire pour chaque couple d'intervenants, alors qu'en cryptographie symé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 bits pour la version courante de AES, contre plus d'un millier pour le RSA, mais surtout le chiffrement comme le déchiffrement sont de cent à mille fois plus rapideChristine Bachoc p 3, Université de Bordeaux I. Les systèmes cryptographiques modernes, comme ceux utilisés par les cartes bancaires, ou le protocole de communication cryptée SSL/TLS très utilisé sur Internet, 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 relai.

Cryptographie asymétrique

Une Carte à puce utilisant un algorithme RSA Le code RSA est un exemple largement répandu de cryptographie asymétrique. 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 nombres premiers p et q et un entier e, premier avec l'ordre g du groupe des unités de Z/
pqZ. Ici g est égal à (p - 1)( q - 1), soit la valeur de la fonction indicatrice d'Euler en n=pq. Les messages sont supposés être des éléments de cet anneau. Si Bob souhaite transmettre le message m à Alice, il transmet la valeur de me modulo n. Alice a rendu au préalable publiques les valeurs de n = p.q, e et donc la fonction f de chiffrement, qui est ici égale à : f(m) \ \equiv\ m^e \quad \pmod n Ève a pu intercepter la connaissance de f, e et n, 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 simple exponentiation modulaire. Pour Alice la lecture l'est aussi, il lui suffit de trouver une solution à l'identité de Bézout : x.e + y.(p-1)(q-1) \ = \ 1\; Si (x0, y0) est une solution, alors le théorème d'Euler montre que : m \equiv \ f(m)^ \mod n En revanche Ève ne connaît pas a priori la décomposition en produit de facteurs premiers de n. Elle doit calculer le logarithme discret de f(m), ce qui constitue un problème ardu. La méthode la moins lente connue correspond à déterminer les valeurs de p et de q. Si n est grand, il n'existe pas, en 2007, d'algorithme efficace pour résoudre cette question. La clé permettant le chiffrement est la donnée de e et n. La force d'un tel système réside dans le fait que la connaissance de cette clé ne permet pas le décryptage, elle peut donc être publique. Les valeurs de p et q constituent la clé du décryptage.

Cryptographie symétrique

La cryptograpie asymétrique n'existerait pas sans les méthodes issues de l'arithmétique modulaire, ce qui, pour des raisons historiques évidentes, n'est pas le cas de la cryptographie symétrique. Elle se divise en deux grandes familles donnt l'une, les chiffrements par flot, utilise comme composant de base les suites récurrentes linéaires sur un corps fini (voir ci-dessous). L'autre, celle des chiffrements par bloc, comprend entre autres le DES et son successeur, le standard de chiffrement avancé appelée AES pour Advanced Encryption Standard. Ces derniers opèrent sur des blocs de données d'une taille fixe comptée en octets, 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 finis de caractéristique 2. Ainsi il s'avère que l'opération d'inversion sur le corps fini F2n, composée avec une transformation affine, a de bonnes propriétés cryptographiques pour en faire l'une des primitives des chiffrements par blocKaisa Nyberg. Differentially uniform mappings for cryptography. In Advances in Cryptology - EUROCRYPT'93, volume 765 of Lecture Notes in Computer Science. Springer-Verlag, 1994, http://www.tcs.hut.fi/~knyberg/publications/diffuni.pdf. Ceci a été exploité par les auteurs du chiffrement Rijndael, qui est devenu l'AES. La publication officielle de ce dernier par le NIST (agence fédérale américaine) contient d'ailleurs quelques préliminaires mathématiques sur le sujetlire http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf pp 10-12. 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ématiciensNiels Ferguson, Richard Schroeppel, Doug Whiting, A simple algebraic representation of Rijndael, Proceedings of Selected Areas in Cryptography, 2001, Lecture Notes in Computer Science, pp 103–111, http://www.macfergus.com/pub/rdalgeq.html, ce qui n'a pas empêché son adoption pour l'AES.

Test de primalité

Les codes RSA utilisent comme clé 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 à 39 000. 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 FermatCryptosec 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. 2003. Si un nombre p est premier, alors pour tout entier a, ap est congru à a modulo p. La réciproque est fausse : il existe des nombres non premiers, appelés nombres de Carmichaël (par exemple 1729), pour lesquels la congruence est vraie pour toute valeur de a. Toutefois, si p n'est ni un nombre de Carmichaël, 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 Carmichaël. 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 Carmichaël, ce qui lève l'un des problèmes du test de Fermat. Pour ces deux méthodes, un 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 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, souventPhilippe Bayart Comment fabriquer de grands nombres premiers? Bibmath.net égale à 1 - (1/2)100.

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 est en permanence ouvert, 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. Les différentes méthodes actuellement utilisées reposent souvent sur les résidus quadratiques. Un diviseur de zéro est un résidu quadratique contenant comme représentants au moins deux carrés parfaits. L'objectif est de trouver ces deux carrés. Cette approche est celle du crible quadratique et de l' algorithme de factorisation par crible sur les corps de nombres généralisé, le plus rapide connu en 2007. On peut encore citer l'algorithme ρ de Pollard, il utilise le paradoxe des anniversaires.

Corps fini

De même que pour l'arithmétique des mathématiques pures, d'autres structures sont nécessaires pour exploiter les capacités offertes par l'arithmétique modulaire. En informatique, les nombres sont codés sur n bits, c'est-à-dire correspondent à une suite de longueur n composée de zéros et de uns. Une telle suite peut être considérée comme un vecteur d'un espace vectoriel de dimension n sur le corps fini F2 à deux éléments. Cette structure est souvent considérée comme l'espace des polynômes à coefficients dans F2. Pour garantir la stabilité de la multiplication, la logique de Gauss est appliquée, cet espace est quotienté par un polynôme irréductible (l'équivalent d'un nombre premier) de degré n. La structure obtenue est le corps fini de cardinal 2n. Un nombre a modulo 2n et un polynôme P du système modulaire sont très semblables, ils s'écrivent en effet : a \ = \ \sum_^ a_i.2^i \quad et \quad P \ = \ \sum_^ \alpha_i.X^i \quad , \quad a_i, \alpha_i \in \mathbb F_2 Un exemple d'utilisation est la création d'un générateur de nombres pseudo-aléatoires dans F2, par exemple pour un chiffrement de flux utilisé dans le contexte d'une communication orale par téléphone portable. Un élément de l'algorithme est la constitution d'un registre à décalage. À l'aide d'une clé, ici un entier c modulo modulo 2n, un tel registre fournit une suite pseudo-aléatoire. Elle est obtenue par une suite récurrente linéaire. Si elle est notée (
u j), alors : Si \quad c \ = \ \sum_^ c_i.2^i \quad alors \quad u_j \ = \ \sum_^n c_i.u_ \quad , \quad c_i \in \mathbb F_2 La suite obtenue est périodique, cependant si la clé est bien choisie, la période est très longue : 2n - 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 élément primitif du groupe cyclique F2n
-. R \ = \ \sum_^ c_.X^i

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ères de ce groupe forment une base orthonormale de l'ensemble des fonctions de V dans celui des nombres complexes. Il est à noterD. Stinson Cryptographie théorique et pratique Int. Thomson Pub. France 1996 que l'ensemble d'arrivée choisi n'est pas toujours celui les complexes mais parfois le corps F2. Les résultats sont strictement identiques. Une telle structure dispose d'une analyse harmonique. Si l'ensemble d'arrivée est choisi égal à F2 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 chiffrements de flux. Un registre à décalage est trop aisément déchiffrable. L'algorithme de Berlekamp-Massey permet de déterminer la suite grâce la connaissance de n valeurs consécutives avec une complexité quadratique. Ainsi, si la clé est composée de 128 bits, il suffit d'un multiple de 128 x 128 = 16 384 étapes pour le décrypter, ce qui 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 F2. 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 2n é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 , la clé est souvent un nombreS. Sing Histoire des codes secrets, Poche p 345 1999 dépassant 10308. Il est important de disposer d'une multiplication rapide sur les grands modulo. La technique consiste à identifier les modulo 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 log(
n) où log désigne ici le logarithme de base deux.

Code correcteur

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 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 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. La télécommunication les utilise pour le téléphone portable ou internet, l'informatique pour notamment la communication entre la mémoire et de processeur, l'audio-visuel pour les disques compacts ou d'autres formats de même nature comme les DVD.

Somme de contrôle

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 à ce 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ée de deux lettres, un mot du code en contient trois, si le message initial est 00, le mot du code transmis est 000, si le message est 01, le mot du code devient 011. 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 renouvèlement 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.

Code cyclique

Illustration d'un 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 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 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 modulo, il est enrichi d'une structure d'anneau de polynômes quotienté par X n - 1, où n désigne la dimension de l'espace vectoriel. Dans cet espace de modulo, le monôme X n est identifié au polynôme constant un. Si la chaîne (a0, a1, …, an) est un mot du code, alors il en est de même de la suivante : (an, a1, a2, …, an-1). 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 dont les messages à transmettre comportent quatre lettres et trois lettres supplémentaires décrivent les redondances.

Identité de Mac Williams

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ômesM. Klemm Etablissement de l'identité de Mac Williams pour les codes linéaires sur l'anneau des entiers modulo m, avec une fonction poids sous forme de polynôme homogène Archiv der Mathematik vol. 49, no5, pp. 400-406 1987, le polynôme choisi étant souvent : X n + 1. Les caractères du groupe sont utilisés, ainsi que l'analyse harmonique associée. L'identité de Mac WilliamsF.J. Mac Williams et J.J.A. Sloane The theory of error correcting codes, North-Holland, 1977 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.

Notes et références

Notes

===
Sujets connexes
Académie des sciences   Adrien-Marie Legendre   Algorithme de factorisation par crible sur les corps de nombres généralisé   Algorithme rho de Pollard   Algorithmique   Algèbre   Algèbre commutative   Alhazen   Analyse complexe   Analyse harmonique sur un espace vectoriel fini   Analyse harmonique sur un groupe abélien fini   Andrew Wiles   Anneau (mathématiques)   Anneau Z/nZ   Anneau adélique   Anneau de Dedekind   Anneau euclidien   Anneau intègre   Anneau quotient   Années 1930   Années 1960   Années 1970   Arithmetica   Arithmétique   Auguste Kerckhoffs   Authentification   Automorphisme   Base orthonormale   Bernhard Riemann   Bit   Brahmagupta   Caractère d'un groupe fini   Caractère de Dirichlet   Carl Friedrich Gauss   Carré parfait   Carte à puce   Charles Gustave Jacob Jacobi   Chiffre de César   Chiffrement   Chiffrement de flux   Chiffrement par bloc   Civilisation chinoise   Claude-Gaspard Bachet de Méziriac   Claude Shannon   Clé de chiffrement   Code correcteur   Code cyclique   Code de Hamming   Code de Hamming (7,4)   Code de Reed-Solomon   Code linéaire   Code parfait et code MDS   Complexité algorithmique   Compétition de factorisation RSA   Confidentialité   Congruence   Congruence sur les entiers   Construction à la règle et au compas   Corps (mathématiques)   Corps de décomposition   Corps de rupture   Corps fini   Correspondance de Galois   Courbe elliptique   Crible d'Ératosthène   Crible quadratique   Cryptanalyse   Cryptanalyse d'Enigma   Cryptographie   Cryptographie asymétrique   Cryptographie symétrique   Cryptologie   DVD   Data Encryption Standard   Dernier théorème de Fermat   Dimension d'un espace vectoriel   Diophante d'Alexandrie   Disque compact   Disquisitiones arithmeticae   Distance de Hamming   Diviseur de zéro   Division euclidienne   Don Coppersmith   Décomposition en produit de facteurs premiers   Démonstrations du dernier théorème de Fermat   Démonstrations du petit théorème de Fermat   Enigma (machine)   Entier algébrique   Entier d'Eisenstein   Entier de Gauss   Entier relatif   Ernst Kummer   Escroquerie   Espace vectoriel   Euclide   Exponentiation modulaire   Extension algébrique   Factorisation des polynômes   Ferdinand Eisenstein   Fonction booléenne   Fonction zêta de Riemann   Forme modulaire   George Sarton   Groupe (mathématiques)   Groupe abélien fini   Groupe cyclique   Groupe de Galois   Groupe des unités   Groupe quotient   Générateur de nombres pseudo-aléatoires   Géométrie   Géométrie algébrique   Géométrie arithmétique   Hameçonnage   Heptadécagone   Histoire de l'Inde   Horst Feistel   IXe siècle   Identité de Bézout   Idéal   Indicatrice d'Euler   Informatique   Institut du monde arabe   Internet   Isomorphisme   Johann Peter Gustav Lejeune Dirichlet   Joseph Fourier   Joseph Needham   Latin   Lemme d'Euclide   Leonhard Euler   Logarithme   Logarithme discret   Loi de réciprocité quadratique   Marian Rejewski   Marin Mersenne   Martin Hellman   Mathématicien   Mathématiques   Mathématiques appliquées   Mathématiques pures   Mise en œuvre   Module d'un nombre complexe   Muhammad ibn Mūsā al-Khuwārizmī   Méthode chakravala   Niels Ferguson   Nombre cardinal   Nombre complexe   Nombre de Carmichaël   Nombre de Fermat   Nombre figuré   Nombre parfait   Nombre premier   Nombre premier de Gauss   Nombre premier régulier   Nombre rationnel   Nombre réel   Nombre transcendant   Nombres premiers entre eux   Norme (arithmétique)   Octet   Paradoxe des anniversaires   Pentium   Petit théorème de Fermat   Pierre de Fermat   Polynôme   Polynôme cyclotomique   Polynôme minimal   Processeur   Produit de convolution   Produit eulérien   Période de Gauss   Qin Jiushao   Racine (mathématiques)   Registre à décalage   Relation d'équivalence   René Descartes   Richard Dedekind   Richard Hamming   Rijndael   Rivest Shamir Adleman   Résidu quadratique   Sciences et techniques islamiques   Scientific American   Seconde Guerre mondiale   Somme de Gauss   Somme de contrôle   Sous-groupe normal   Standard de chiffrement avancé   Suite arithmétique   Suite récurrente linéaire   Sun Zi (mathématicien)   Symbole de Legendre   Système d'équations linéaires   Sécurité par l'obscurité   Série L de Dirichlet   Série entière   Test de primalité   Test de primalité de Fermat   Test de primalité de Miller-Rabin   Test de primalité de Solovay-Strassen   Théorie algébrique des nombres   Théorie analytique des nombres   Théorie de Galois   Théorie de l'information   Théorie des anneaux   Théorie des codes   Théorie des nombres   Théorème d'Euler (nombres)   Théorème de Jordan-Hölder   Théorème de Wilson   Théorème de congruence linéaire   Théorème de la progression arithmétique   Théorème des deux carrés de Fermat   Théorème des restes chinois   Théorème des unités de Dirichlet   Théorème des zéros de Hilbert   Théorème fondamental de l'arithmétique   Thābit ibn Qurra   Topologie algébrique   Transformée de Fourier   Transformée de Fourier discrète   Transformée de Fourier rapide   Transformée de Walsh   Unité arithmétique et logique   VIIe siècle   Variété (géométrie)   Vecteur   Whitfield Diffie   XIe siècle   XXe siècle  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^