Arithmétique modulaire - Définition

Histoire

Origines

Au III^e siècle av. J.-C., 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 parfaits dans la proposition 36 de son livre IX. Diophante d'Alexandrie é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ématique dont le problème 26 du chapitre 3 est le suivant : « 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 ? ».

Qin Jiushao développe le théorème des restes chinois. Son traité est remarquablement avancé, il traite d'un système d'équations linéaires de congruences dans le cas où les moduli ne sont pas premiers entre eux deux à deux. Ses travaux sur les systèmes de congruences dépassent en sophistication ceux de Leonhard Euler . On peut citer George Sarton pour qui : « Qin Jiushao était l'un des plus grands mathématiciens de race chinoise, de son temps et à vrai dire de tous les temps ».

Le XIV^e 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 XX^e siècle. 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.

L'Inde possède aussi une tradition forte en arithmétique. Âryabhata recherche de manière systématique les solutions entières de l'équation linéaire à deux inconnues à coefficients entiers. Il utilise pour cela un algorithme appelé « Kuttaka » publié dans son livre appelé Aryabhatiya. Les équations diophantiennes de degré deux sont étudiées par Brahmagupta à l'aide de la méthode chakravala.

La civilisation islamique joue un double rôle en arithmétique : elle véhicule le savoir acquis par les Grecs, Indiens, Chinois et Européens, et elle apporte des connaissances nouvelles notamment sur l'étude des propriétés de certains ensembles d'entiers, comme les nombres premiers, parfaits, amicaux ou figurés. 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'Euclide ; son collègue al-Khuwārizmī écrit un livre sur la numération indienne. Si le livre est perdu, il reste connu par une traduction latine Algoritmi de numero Indorum. Thābit étudie les nombres amicaux et les nombres parfaits. Alhazen continue ses travaux sur les nombres parfaits et découvre le théorème de Wilson.

Apparition en Europe

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, particulièrement les Français. Pierre de Fermat 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 : « un nombre carré qui, ajouté à la somme de ses parties aliquotes (i.e. ses diviseurs), fasse un cube. » Il conclut par : « 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 ». Marin Mersenne recherche des nombres premiers particuliers. Fermat lui écrit : « 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 ». 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 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² + 2y².

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 : « J'ai trouvé une solution merveilleuse ... »

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 : « ... mais la place me manque ici pour la développer » (la première preuve reconnue apparaîtra en 1994, 1995). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec : « 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... »

Méthodes utilisées

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. 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. 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 , la solution reste hors de portée.

Jusqu'à l'aube du XIX^e siècle 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² et b² 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 2c + 1, son carré est égal à 4c² + 4c + 1, la division de b² 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 2c + 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. Cette méthode fut déjà utilisée par Fermat pour démontrer son 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 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

À l'âge de 17 ans, Carl Friedrich 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 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.

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

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ématiciens comme Legendre ont bien imaginé qu'il en 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 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, Charles Gustave Jacob Jacobi écrit, dans une lettre à son frère : « 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. » 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 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 XIX^e siècle, ces mathématiques sont dénommées arithmétique transcendante. 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 nombres. 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 avec l'apparition des nombres transcendants.

XX^e siècle

Cryptologie

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, Auguste Kerckhoffs énonce que : « la sécurité d'un système de cryptographie ne doit pas reposer sur le secret de l'algorithme. La sécurité ne repose que sur le secret de la clé ». Cette approche est à l'origine d'une modification profonde de cette science. Au milieu du XX^e siècle, elle devient une branche des mathématiques appliquées.

Au début des années 1930, le bureau du chiffre polonais fait appel au mathématicien Marian Rejewski 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 moduli de Gauss sur les nombres entiers. Le terme d'« arithmétique modulaire » est utilisé pour décrire ces techniques. Durant les années 1970, Horst Feistel développe un système à clé privée, le Data Encryption Standard ou DES, qui devient le standard des applications non classifiées. 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 1976 une nouvelle famille de codes est découverte, 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'Euler. Le terme « arithmétique modulaire » est, dans ce contexte, utilisé pour décrire 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 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 XXI^e siècle. Une mise en œuvre efficace nécessite l'utilisation d'opérations sur des grands ensembles de moduli. 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'entiers, par exemple pour la cryptanalyse.

Théorie de l'information

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, sous l'impulsion de Claude Shannon , elle devient 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 algorithme dès 1950. Une fois encore, les moduli 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és, sur la base de polynômes à coefficients dans un corps fini. L'arithmétique utilisée prend souvent le nom de « modulaire ».

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 moduli. Le terme d'« arithmétique modulaire » apparaît souvent, 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.