GALOIS INVERSE AVEC POLYNÔMES ARITHMÉTIQUE MODULAIRE ET NOMBRES PREMIERS

Bernard Sourd

Description

L'ouvrage utilise deux thèmes : la théorie de Galois et l'arithmétique modulaire. Pour qu'un lecteur non suffisamment familiarisé avec ceux-ci puisse aborder les sujets traités sans difficultés majeures, les bases sont présentées de façon approfondie avec exercices et problèmes. Le problème dit de Galois inverse est alors présenté. Il utilise des polynômes dit de Galois formant pour la composition le groupe de Galois.Une approche constructive est proposée ; elle ramène l'étude à la résolution d'un système polynomial à l'aide de fonctions symétriques fondamentales. Dans une deuxième partie est introduite l'extension algébrique du crible d'Eratosthène. Les nombres premiers y jouent un rôle capital et diverses propriétés ainsi que des algorithmes sont présentés. En particulier on a mis en évidence un algorithme qui conduit au calcul de pi(x) nombre de nombres premiers jusqu'à x, avec seulement la connaissance des nombres premiers jusqu'à x^{2/3}.L'arithmétique modulaire permet aussi de construire deux systèmes symétriques homomorphes. Des solutions des exercices et problèmes proposés terminent l'ouvrage.

Informations

• Publié par: Rue des écoles
• Date de parution: 01 janvier 2023
• Nombre de lectures: 11
• EAN13: 9782820814500
• Langue: Français

Extrait

GALOIS INVERSE AVEC POLYNÔMES ARITHMÉTIQUE MODULAIRE ET NOMBRES PREMIERS

Bernard Sourd

EAN : 9782820814500 © rue des écoles, 2022 Éditions rue des écoles, 15 boulevard Bourdon, 75004 Paris Achevé d’imprimer en France en décembre 2022 Dépôt légal : janvier 2023

Table des matières

Avant propos

Chapitre 1. Bases de la théorie de Galois 1. Extensions algébriques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Théorème de l’élément primitif. . . . . . . . . . . . . . . . . . . . . . . . . 3. Corps conjugués . Éléments conjugués. . . . . . . . . . . . . . . . . . . . . 4. Architecture et théorie de Galois. Les Théorèmes Fondamentaux.. . . . . 5. Compléments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 2. Bases de l’arithmétique modulaire 1. Notions Essentielles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. ExercicesProblèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Complément :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

9 9 23 25 30 53

68 68 88 93

Chapitre 3. Polynômes de Galois et Galois inverse 102 1. Préambule : Polynômes de Galois. . . . . . . . . . . . . . . . . . . . . . . .102 2. Galois inverse surQ: nouvelle approche constructive. . . . . . . . . . . .115 3. Exercices  Problèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126

Chapitre 4. Résolution par radicaux et Résolvantes de Lagrange 128 1. Préambule sur une équation de degré5surQ. . . . . . . . . . . . . . . . .128 2. Obtention des racines de (E) par radicaux avec les résolvantes de Lagrange 132

Chapitre 5. Extension algébrique du crible d’Ératosthène 140 ∗ 1. Groupes de classes de congruences dansN. . . . . . . . . . . . . . . . . .141 2. Méthode d’extension du crible d’Ératosthène. . . . . . . . . . . . . . . . .143 3. Extension de groupes et nombres premiers. . . . . . . . . . . . . . . . . .154

Chapitre 6. Récurrence algorithmique pour la suite des nombres premiers 157 1. Fondements arithmétiques. . . . . . . . . . . . . . . . . . . . . . . . . . . .157 2. Successeur premier d’un nombre premier sans crible. . . . . . . . . . . . .159

Chapitre 7. Calcul de la fonction pi 166 1. Calcul deπ(x)par une méthode du type de celle de MeisselLehmer. . . .166

3

4

2.

Exemples Numériques. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . .170

Chapitre 8. Deux Cryptosystèmes Symétriques Homomorphes 174 1. Mathématiques : Arithmétique Modulaire. . . . . . . . . . . . . . . . . .174 2. Implémentation des cryptosystèmes. . . . . . . . . . . . . . . . . . . . . .179 3. Homomorphismes et calculs de monômes. . . . . . . . . . . . . . . . . . .183 4. Remarques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183

Chapitre 9. Solutions des Exercices et Problèmes

Bibliographie

185

219

Avant propos

L’ouvrage présente principalement deux sujets . L’un concerne la théorie de Galois et surtout une nouvelle approche du problème dit de Galois inverse. Pour qu’un lecteur puisse y être à l’aise nous avons rappelé en chapitre 1 les bases de la théorie de Galois, les résultats fondamentaux à connaitre et quelques exemples (en restant en caractéristique 0). Le problème de Galois inverse avec les polynômes de Galois, définis à cette occasion, est développé au chapitre 3. Le chapitre 4 est un exemple de résolution par radicaux avec l’appui des résolvantes de Lagrange. L’autre sujet concerne les nombres premiers et l’arithmétique modulaire. Celleci a connu depuis une soixantaine d’années un essor prodigieux, surtout en raison du développement des techniques de cryptographie et de leurs utilisations massives dans le domaine des com munications écrites et surtout électroniques.

L’utilisation des nombres premiers a joué un rôle important dans ces développements en liai son avec les opérations arithmétiques modulaires, car on peut calculer, modulo un nombre, avec des additions et des multiplications dans des structures quotients : groupes, anneaux, corps, commeZ/pZ, p premier, par exemple. La structure de groupe joue un rôle primordial.

Aussi dans les chapitres de cet ouvrage, nous proposons divers développements utilisant cette arithmétique modulaire comme un outil essentiel voire indispensable. Ces notions d’arith métique modulaire ne doivent plus être seulement un recueil de propriétés dans les cursus universitaires, mais doivent être utilisées le plus tôt possible dans des situations non triviales et variées.

Nous avons rappelé dans le chapitre 2 les notions essentielles et les théorèmes importants à connaitre. Des exercices d’applications assez immédiates sont proposés afin que ceux qui ne sont pas rompus avec ces notions puissent les acquérir rapidement. Ils sont corrigés dans le chapitre 9.

Bien entendu, pour l’ensemble du livre, il est nécessaire que le lecteur connaisse les bases élémentaires de l’algèbre classique, c’estàdire la trilogie "matrimoniale" : groupes, anneaux et corps dont les outils sont utilisés constamment.

L’ouvrage est donc en deux parties.

6

La première partie comporte les chapitres 1,3 et 4, concernant Galois. La deuxième partie comporte les chapitres 2,5,6,7 et 8 concernant l’arithmétique modulaire, les nombres premiers et les applications. Le chapitre 9 donnent des corrigés d’exercices et aussi des problèmes avec solutions. La première partie concerne la théorie de Galois et son architecture pour avoir une approche du problème dit de "Galois inverse". Les bases de la théorie de Galois étant rappelées et détaillées dans le chapitre 1, le chapitre 3 introduit donc les "polynômes de Galois" et on obtient une équivalence au problème dit de Galois inverse. Nous avons d’abord rappelé la notion de groupe de Galois développé dans son mémoire et donné des explications et des exemples afin d’être familiarisé avec ces notions. Le chapitre 4 fait l’étude d’une sousextension d’une extension cyclotomique deQpour p=11. L’utilisation des résolvantes de Lagrange permet de résoudre complètement une équation de degré 5 surQpar radicaux. Pour ces chapitres des exercices sont proposés qui vont permettre d’assimiler certaines no tions et de se confronter à des situations numériques. La deuxième partie débute avec le chapitre 2. Dans le chapitre 2 nous faisons un récapitulatif des bases et des notions élémentaires et es sentielles d’arithmétique classique et modulaire, à connaitre et à employer. Nous donnons les démonstrations des théorèmes, ainsi que quelques algorithmes. Ici également pour ces révisions ou compléments, des exercices sont proposés pour conforter les bases. On donne une suite d’exercices et de problèmes. Le chapitre 2 se termine par un complément : nous revenons sur l’importance de l’irréduc tibilité des polynômes cyclotomiques surQet surZ. Deux démonstrations sont détaillées, l’une issue de Landau, l’autre de Schur. Une troisième démonstration classique est rappelée sommairement car elle figure dans beaucoup d’ouvrages.

Le chapitre 5 concerne l’extension algébrique du crible d’Eratosthène. Ce crible tant, très utile mais il nécessite de fixer une borne B pour être certain d’avoir nombres premiers inférieurs à B avec exactitude.

est impor obtenu les

Aussi nous avons mis en oeuvre une méthode pour s’affranchir de ce problème de la borne. Elle crée en quelque sorte successivement les nombres entiers et permet une certaine classi ∗∗ fication. On obtient une partition deN(Nprivé de 0 et de 1) par classes de congruences. Mais surtout on obtient un algorithme pour créer les nombres premiers. Désignons parM k le produit des nombres premiers de 2 àp k et parE k l’ensemble des entiers inférieurs àM k et copremiers àM k . On passe facilement deE k àE k+1 à l’aide d’un tableau matricielW k . De cette façon on augmente la liste des nombres premiers par un algorithme de coût meilleur que celui du crible d’Eratosthène. On utilisera cet algorithme au chapitre 7 pour le calcul deπ(x). On montre donc dans ce chapitre 5 qu’on obtient plus facilement les nombres premiers par des multiplications plutôt que par des divisions.

7

Le chapitre 6 développe une récurrence algorithmique utilisant justement la mécanique du passage deE k àE k+1 pour montrer comment on peut obtenirp k+1 successeur dep k sans crible. Le chapitre 7 est consacré au calcul deπ(x). Nous avons redécouvert, au cours de la construc tion évoquée au chapitre 5, la méthode de Meissel reprise par Lehmer, à savoir un algorithme 2/3 permettant d’obtenirπ(x)en ne connaissant que les nombres premiers jusqu’àx. Le chapitre 8 utilise encore l’arithmétique modulaire par utilisation de la notion de racine primitive modulo un nombre premier et d’indice associé, pour transformer un produit de nombres deE k en une somme. Cela permet de construire deux cryptosystèmes symétriques homomorphes et leur emploi à la cryptographie.

Le chapitre 9 propose des solutions des exercices et problèmes proposés dans les chapitres précédents. Certains exercices sont assez simples car d’applications immédiates des théo rèmes et d’algorithmes, mais d’autres sont plus délicats et nécessitent plus de recherche et de doigté. Bien entendu le lecteur doit retarder le plus longtemps possible la lecture des solutions et doit d’abord s’efforcer (voire s’acharner) à trouver des solutions personnelles.

La rédaction a été détaillée pour qu’un lecteur non rompu à l’arithmétique modulaire puisse progresser dans la compréhension et l’utilisation des résultats fondamentaux et y trouver satisfaction. Le chapitre 2 sur les bases de l’arithmétique classique et modulaire pourrait intéresser les très bons élèves de Terminales en spécialité mathématique. Les étudiants en classe préparatoire aux grandes écoles scientifiques et en premier cycle de l’université, ainsi que les futurs professeurs de mathématiques préparant le CAPES et l’AGRÉGATION seront intéressés par cet ouvrage qui devrait d’une part conforter leurs bases en arithmétique et en voir des applications non classiques, d’autre part apprendre ou réviser les bases de la théorie de Galois pour ceux qui l’ont à leur programme, avec un complément intéressant sur le problème dit de Galois inverse. Nous avons eu le plaisir de travailler avec des collègues de l’Université de Limoges et de profiter de leurs conseils éclairés et de participer au séminaire de théorie des Nombres. Nous avons nousmêmes présenté dans ce séminaire nos résultats sur l’extension algébrique du crible d’Eratosthène et du calcul deπ(x)par une méthode qui se trouva par la suite s’appa renter à celle de MeisselLehmer, reprise par l’équipe Lagarias, Miller, Odlysko. Et nous avons également plus tard présenté à ce séminaire notre approche du problème de Galois inverse avec les polynômes de Galois.

Nous avons eu la chance de pouvoir côtoyer Paul Erdös qui venait souvent à cette époque à Limoges et nous avons pu bénéficier de ses conseils. De même nous avons eu la possibilité de suivre des cours de Carl Pomerance qui était Pro fesseur invité à l’Université de Limoges et de profiter également de ses conseils. C’était à l’époque où il avait mis au point le Crible Quadratique qu’il avait exposé à la communauté des théoriciens et praticiens des nombres de Limoges.

8

Aussi nos adressons nos chaleureux remerciements à JeanLouis Nicolas, Guy Robin, Jean Pierre Massias, François Laubie, ainsi qu’aux Québécois JeanMarie De Koninck et Claude Levesque. Nous remercions également David Naccache pour ses précieux conseils concer nant les cryptosystèmes homomorphes. Que Claude Morin soit remercié pour des lectures de certains chapitres avec des corrections à effectuer, ainsi que Pierre Dusart. Nous remercions chaleureusement DENIS MONASSE qui nous a donné la possibilité de rédiger notre livre avec le système informatique qu’il dirige avec une grande maîtrise et pour ses bons conseils amicaux. Nous exprimons nos sincères remerciements à la maison d’édition RUE DES ECOLES qui nous accueille aux fins d’éditer notre livre.

SOURD Bernard

Chapitre 1 Bases de la théorie de Galois

Avertissement :Dans ce chapitre nous ne faisons pas véritablement un cours, mais donnons tout de même les notions essentielles pour qu’un lecteur non familiarisé avec les connais sances nécessaires puisse se mettre au niveau. Nous n’avons donc pas cherché à faire un cours universitaire avec les notions algébriques du top niveau. Les notions introduites sont axées plutôt sur la théorie de Galois originale, c’estàdire en utilisant le théorème capital dit de l’élément primitif, car nous aurons besoin de cette utilisation pratique pour les polynômes de Galois. Cela ne veut pas dire que nous négligeons la présentation d’Artin qui a aussi ses bons côtés.

1. Extensions algébriques

Nous rappelons d’abord quelques définitions de bases.

1.1.Corps commutatifs

Définition :Un corps commutatif K est un anneau commutatif avec élément unité multipli catif dont tous les éléments non nuls sont inversibles. Ainsi K possède une loi d’addition notée + telle que (K,+) soit un groupe commutatif avec un élément neutre noté O et une loi de multiplication . avec unité, de sorte que (K,+, .) soit un anneau commutatif avec un élément unité noté 1 distinct de O. De plus l’ensemble des ” inversibles de cet anneau pour la loi . notéKest égal àK/{0}ensemble des éléments non nuls de K. Un tel corps a donc au moins deux éléments. ” ” On sait que pour un anneau avec unité,Kest stable pour la loi . et que (K, .) est un groupe appelé groupe des éléments inversibles de l’anneau. Donc pour un corps on a le groupe des éléments non nuls pour la loi multiplicative . Caractéristique d’un anneau : Soient A un anneau avec unité etϕl’homomorphisme deZdans A qui associe à n l’élément ne, e étant l’unité de A : ϕ:n ֒→ne Le noyau deϕétant un sousgroupe du groupe additif deZ, il est soit réduit à 0, soit cyclique engendré par un plus petit entier strictement positif n.

10

Dans le premier cas on dit que A est de caractéristique nulle et A contient un sousanneau isomorphe àZcar il n’existe pas d’entier n tel que ne = 0. Dans le second cas il existe un plus petit entiern >0tel que ne = 0. On dit alors que A est Z de caractéristique n et A contient un sousanneau isomorphe à . nZ Proposition .La caractéristique p d’un anneau intègre et donc d’un corps , si elle est non nulle, est un nombre premier p. Démonstration .En effet si p était composé, soit p = rs, on aurait :0 =pe= (re)(se)., mais vu l’intégrité on devrait avoir : re = 0 ou se = 0, en contradiction avec le fait que p est minimal pour la propriété ne = 0, donc p n’étant pas composé est premier. Remarque. Un corps commutatif K de caractéristique 0 contient un sousanneau isomorphe à Z, donc aussi le corps des fractions de celuici c’estàdireQ. Ainsi K contient un souscorps isomorphe àQ. Un corps commutatif de caractéristique p premier contient un souscorps isomorphe au corps Z . pZ Dans les deux cas ce souscorps contenu dans K est appelé le souscorps premier de K. Z ExemplesLes corpsQ,R,C(pour p premier) sontsont de caractéristique 0. Les corps pZ de caractéristique p.

1.2. Extensions de corps commutatifs

Si un corps L contient un corps K comme souscorps, on dira que L et uneextensionde K. Une extension de corps, du corps K est donc un couple (L,K) où L est un corps et K est souscorps de L. Cette extension pourra être notéeL/K. Il peut y avoir des corps J contenant K comme souscorps et être souscorps de L ; on dit que ce sont des corps intermédiaires entre K et L. Plus généralement une extension de corps est un couple (L,K) de corps où L contient un souscorps K’ isomorphe à K. Souvent on identifie K’ à K. ExtensionL/Kde corps comme espace vectoriel sur K et algèbre sur K : Si on considère L muni de son addition, et la multiplication des éléments de L par ceux de K uniquement comme loi externe de L sur K, on peut donc considérer L comme espace vectoriel sur le corps K. On peut aussi considérer de plus la multiplication de L et L est aussi une algèbre sur K. Cette interprétation est importante et permet de simplifier des présentations algébriques. Comme exemples le corpsCest extension deRet extension deQ.Rest extension deQ.R est corps intermédiaire entreQetC.