L'arithmétique modulaire et ses applications : exemples et exercices corrigés

Auteur(s) :

Lamoitier, Jean-Pierre Découvrir l'auteur

Résumé

De nombreuses notions : les congruences, les polynômes en arithmétique modulaire, les résidus quadratiques, cubiques et biquadratiques, les symboles de Legendre et de Jacobi, les racines primitives, le logarithme discret, les équations en arithmétique modulaire, les grands nombres premiers et pseudo-premiers et une ouverture vers la cryptographie.

Éditeur(s)
- Hermann
Date
- impr. 2009
Notes
- Bibliogr. et webliogr. p. 257-258. Index
- Bibliogr. Index
Langues
- Français
Description matérielle
- 1 vol. (261 p.) : ill., couv. ill. ; 21 cm
Collections
- L'arithmétique
Sujet(s)
- Problèmes et exercices
- Arithmétique
ISBN
- 978-2-7056-6918-8
Indice
- 511.9 Arithmétique, théorie des nombres
Quatrième de couverture
- L'arithmétique classique existe depuis l'Antiquité, et s'est développée tout au long des siècles. Pierre de Fermat l'a marquée de son empreinte. Gauss a beaucoup développé l'arithmétique modulaire notamment avec les notions de congruences, de résidu quadratique, etc, et a démontré de nombreuses propriétés dans ce domaine. Pendant environ deux siècles, cette discipline s'est développée sans aucune application concrète. La seconde moitié du XX^e siècle a elle été caractérisée par l'arrivée de nombreuses applications dont la cryptographie et, dans une moindre mesure, les techniques de codes correcteurs d'erreurs qui sont maintenant très utilisées en transmission. Cette arithmétique s'est immiscée un peu sournoisement dans notre vie courante : numéro de sécurité sociale, transmissions sécurisées par Internet pour les transferts d'argent, et bien d'autres choses encore.
  Divers problèmes amusants se traitent assez facilement avec ces techniques.
  L'arithmétique modulaire tome III est également utilisée pour démontrer des propriétés de l'arithmétique classique, ce qui explique les liens entre ces trois tomes complémentaires.
  Ce tome III présente de nombreuses notions : les congruences, les polynômes en arithmétique modulaire, les résidus quadratiques, cubiques et biquadratiques, les symboles de Legendre et de Jacobi, les racines primitives, le logarithme discret, les équations en arithmétique modulaire, les grands nombres premiers et pseudo-premiers et une ouverture vers la cryptographie.
  Cette discipline est souvent présentée sous une forme difficile à assimiler, et même parfois rebutante, en partie à cause du vocabulaire utilisé et en grande partie par la quasi-absence d'exemples et d'exercices. Pour ces raisons, l'auteur a délibérément choisi de privilégier l'aspect pédagogique avec de nombreux exemples et exercices corrigés quitte à omettre certaines démonstrations trop longues ou trop difficiles.
Tables des matières
- - L'Arithmétique une introduction ludique
  - Tome III : L'arithmétique modulaire et ses applications Exemples et exercices corrigés
  - Jean-Pierre Lamoitier
  - Hermann éditeurs
  - 1. Les congruences 1
  - 1.1. Introduction1
  - 1.2. La notion de congruence1
  - 1.3. Quelques propriétés des congruences3
  - 1.4. Opérations sur les congruences5
  - 1.4.1. L'addition 5
  - 1.4.2. La soustraction 5
  - 1.4.3. La multiplication 6
  - 1.4.4. Multiplication modulaire rapide 6
  - 1.4.5. Les nombres négatifs et les inégalités 7
  - 1.5. Les puissances en arithmétique modulaire8
  - 1.6. Rappel : le petit théorème de Fermat8
  - 1.6.1. La généralisation d'Euler 9
  - 1.7. Congruence inverse et diviseurs de zéro10
  - 1.7.1. Application aux équations diophantiennes 11
  - 1.8. Quelques lemmes11
  - 1.9. Identités et inégalités remarquables15
  - 1.10. L'arithmétique modulaire modulo 916
  - 1.10.1. Application : la preuve par 9 16
  - 1.11. Le cas des additions et multiplications modulo 217
  - 1.12. Exercices17
  - 1.13. Démonstration du théorème de Wilson20
  - 1.14. L'exponentiation modulaire rapide21
  - 1.15. Théorème de Wolstenholme22
  - 1.16. Équation aux congruences. Congruence avec exposant24
  - 1.17. Exercices24
  - 1.17.1. La date de Pâques 25
  - 1.17.2. Exercices : nombre de billes 27
  - 1.18. Entiers de Gauss et congruences ?28
  - 2. Congruence d'une puissance 29
  - 2.1. Les carrés dans l'ensemble Z/nZ29
  - 2.2. Les cubes modulo n31
  - 2.3. Propriétés de base33
  - 2.4. Congruences et puissances modulo pⁿ37
  - 2.4.1. Lemmes 37
  - 2.5. Somme des puissances dans Z/nZ39
  - 2.6. Les inverses modulo p²40
  - 2.7. Les inverses modulo pⁿ41
  - 2.8. Carré inversible modulo p41
  - 2.9. Les racines carrées modulo n42
  - 2.10. Congruence quadratique (ou de Legendre)45
  - 2.11. Exercices46
  - 2.12. Conclusion52
  - 3. Les polynômes en arithmétique modulaire 53
  - 3.1. Introduction53
  - 3.1.1. Quelques définitions 53
  - 3.2. Polynômes congrus54
  - 3.3. Les opérations de base54
  - 3.4. La division euclidienne55
  - 3.5. Le PGCD de deux polynômes55
  - 3.6. Polynômes premiers entre eux55
  - 3.7. Théorème de Gauss56
  - 3.8. Polynômes irréductibles56
  - 3.9. La factorisation des polynômes57
  - 3.9.1. Quelques propriétés en arithmétique modulaire 57
  - 3.10. Pour approfondir58
  - 3.11. Conclusion58
  - 4. Résidus quadratiques 59
  - 4.1. Introduction59
  - 4.2. Les résidus quadratiques60
  - 4.2.1. Conjecture d'Euler 61
  - 4.3. Déterminer si un nombre est résidu quadratique62
  - 4.4. Exercice65
  - 4.5. Le critère d'Euler66
  - 4.6. Propriétés élémentaires des résidus quadratiques66
  - 4.7. Quelques lemmes démontrés par Gauss68
  - 4.7.1. Tableau récapitulatif 71
  - 4.8. Sommes et produits de résidus quadratiques71
  - 4.8.1. Le produit des résidus quadratiques 72
  - 4.8.2. La somme des résidus quadratiques 72
  - 4.9. Résidus associés73
  - 4.10. Application à la résolution d'équations diophantiennes74
  - 4.11. Exercice74
  - 4.11.1. Pour approfondir 74
  - 4.12. Résidus quadratiques modulo p² ou pⁿ75
  - 4.13. Les nombres de Blum76
  - 4.13.1. Quelques propriétés des entiers de Blum 76
  - 4.14. Application aux équations diophantiennes du second degré77
  - 4.15. Exercices77
  - 4.15.1. Le second cauchemar quadratique 79
  - 4.16. Conclusion81
  - 4.17. Pour approfondir81
  - 5. Le symbole de Legendre 83
  - 5.1. Définition83
  - 5.2. La loi de réciprocité quadratique84
  - 5.3. Autres propriétés du symbole de Legendre85
  - 5.3.1. cas : 1 et - 1 86
  - 5.3.2. cas : 2 et - 2 86
  - 5.3.3. 2 ème cas : 3 et - 3 87
  - 5.3.4. 3 ème cas : 5 et - 5 88
  - 5.3.5. 4 ème cas : 7 89
  - 5.4. Méthodes de calcul90
  - 5.5. Démonstration des lemmes du chapitre précédent91
  - 5.6. Exercices92
  - 5.6.1. exercice 1 : calculer (91/107) 93
  - 5.6.2. Exercice 2 93
  - 5.6.3. Exercice 3 94
  - 5.7. Lemme de Gauss95
  - 5.8. Valeurs du symbole de Legendre96
  - 5.9. Exercices97
  - 5.10. Conclusion98
  - 6. Le symbole de Jacobi 99
  - 6.1. Définition99
  - 6.1.1. Quelques propriétés de base 100
  - 6.1.2. La loi de réciprocité quadratique pour le symbole de Jacobi 101
  - 6.1.3. Tableau comparatif entre les deux symboles 103
  - 6.2. Lien avec la factorisation103
  - 6.3. Exercices104
  - 6.4. Conclusion106
  - 7. Les résidus cubiques et biquadratiques 107
  - 7.1. Introduction107
  - 7.2. Définitions107
  - 7.3. Propriétés communes aux résidus cubiques et biquadratiques107
  - 7.4. Les résidus cubiques108
  - 7.4.1. Nombre de résidus cubiques ? 111
  - 7.4.2. Le symbole de Legendre pour les résidus cubiques 111
  - 7.4.3. La loi de réciprocité cubique 112
  - 7.5. Les résidus biquadratiques115
  - 7.5.1. Quelques propriétés 117
  - 7.5.2. Cas particulier où p est congru à 3 modulo 4 117
  - 7.5.3. Cas particulier où p est congru à 1 modulo 8 118
  - 7.5.4. Symbole de Legendre et Loi de réciprocité biquadratique : 118
  - 7.5.5. Détermination pratique des résidus biquadratiques 119
  - 7.6. Conclusion120
  - 7.7. Pour approfondir120
  - 8. Ordre d'un élément 121
  - 8.1. Ordre d'un élément121
  - 8.2. Propriétés élémentaires de l'ordre124
  - 8.3. Quelques lemmes125
  - 8.4. À propos de l'indicatrice d'Euler127
  - 8.5. La fonction Psi128
  - 8.6. L'indicatrice de Carmichaël129
  - 8.6.1. Quelques lemmes 130
  - 8.7. Exercices131
  - 8.8. Conclusion132
  - 8.9. Pour approfondir132
  - 8.10. Les nombres quadratiques133
  - 8.11. Retour sur les nombres de Carmichaël133
  - 8.12. Conclusions134
  - 9. Racine primitive 135
  - 9.1. Rappels : groupes et sous-groupes cycliques135
  - 9.2. Puissances en arithmétique modulaire135
  - 9.3. Définition137
  - 9.4. Combien de racines primitives dans un groupe138
  - 9.5. Théorème de la racine primitive139
  - 9.6. Recherche des racines primitives139
  - 9.7. Quelques propriétés élémentaires des racines primitives142
  - 9.8. Produit de racines primitives142
  - 9.9. Racines primitives et résidus quadratiques143
  - 9.10. Cas particuliers145
  - 9.10.1. Nombres premiers de la forme 2n + 1 145
  - 9.10.2. Nombres premiers de la forme 4n + 1 146
  - 9.11. Exercice147
  - 9.12. Racines primitives modulo un nombre composé148
  - 9.13. Monsieur Tompkins et les racines primitives148
  - 9.14. Pour approfondir149
  - 10. Le logarithme discret 151
  - 10.1. Rappels : la fonction logarithme151
  - 10.2. Définition151
  - 10.3. Quelques propriétés élémentaires153
  - 10.4. Cas d'un groupe non cyclique158
  - 10.5. Recherche du logarithme discret158
  - 10.5.1. Méthode de Daniel Shanks 159
  - 10.5.2. Méthode de Pohlig-Hellman 159
  - 10.5.3. La méthode de calcul de l'Index 160
  - 10.5.4. Algorithme d'Adleman 161
  - 10.6. L'échange de clés de Diffie-Hellman161
  - 10.7. Conclusion162
  - 11. Les équations du 1 er degré 163
  - 11.1. Généralités163
  - 11.2. Équations du premier degré en arithmétique modulaire163
  - 11.2.1. Équation ax = 1 modulo n 163
  - 11.2.2. Équation ax = b modulo n 164
  - 11.2.3. Méthode pratique de résolution 164
  - 11.3. Système d'équations linéaires portant sur les congruences165
  - 11.3.1. Le théorème chinois des restes 166
  - 11.4. Exercices168
  - 11.4.1. Le jour de la semaine 168
  - 11.4.2. Le code ISBN 169
  - 11.4.3. Le numéro de Sécurité Sociale 169
  - 11.4.4. L'or des pirates 169
  - 11.4.5. Trouver N entre 1 et 12 171
  - 11.4.6. Exercice 3 172
  - 12. Équation de degré 2 173
  - 12.1. Équation du second degré modulo un nombre premier173
  - 12.1.1. Un exemple intéressant et amusant 173
  - 12.1.2. Le cas particulier : x² + a (...) b modulo c 174
  - 12.1.3. Deux lemmes intéressants 175
  - 12.2. Le cas général175
  - 12.3. L'équation de Pell ou de Pell-Fermat177
  - 12.3.1. Existence de solutions 177
  - 12.3.2. Analyse du problème 178
  - 12.3.3. Exemple d'application 178
  - 12.3.4. Recherche de la solution minimale 179
  - 12.3.5. Seconde approche 180
  - 12.3.6. Équation x² - ny² = -1 181
  - 12.3.7. Exercices 182
  - 12.4. Équations de Pell généralisées185
  - 12.5. Exercices187
  - 13. Équations de degré supérieur à 2 189
  - 13.1. Équations modulo un nombre premier189
  - 13.2. Le lemme du relèvement190
  - 13.3. Équation diophantienne x² + 3y² = z³191
  - 13.4. Quelques équations du 4^ème degré192
  - 13.5. Conjecture de Catalan et dérivées192
  - 13.5.1. Conjecture de Catalan 192
  - 13.5.2. Théorème de V.A. Lebesgue : 192
  - 13.5.3. Théorème de Cassels 193
  - 13.5.4. Théorème de Ko Chao : 193
  - 13.6. Conjecture de Mordell193
  - 13.7. Résolution de quelques équations particulières193
  - 13.7.1. Pas de solution pour l'équation x⁴ - 8 y⁴ = 1 193
  - 13.7.2. Équation x² - 8y⁴ = 1 194
  - 13.7.3. Équation x⁴ - 2y² = 1 194
  - 13.7.4. Les équations x⁴ - ay² = 1 et 4x⁴ - ay² = 1 195
  - 13.7.5. Équation polynomiale 196
  - 13.8. Équation avec l'inconnue en exposant196
  - 13.9. Applications des congruences197
  - 13.10. Congruence de carrés197
  - 13.11. Exercices197
  - 13.11.1. équation x³ + 5 = 153y³ 197
  - 13.11.2. Valeur de a⁴ modulo 16 197
  - 13.11.3. Équation du 4 ème degré 198
  - 13.12. Pour approfondir199
  - 14. Les grands nombres premiers ou pseudo premiers 201
  - 14.1. Introduction201
  - 14.2. Définitions201
  - 14.3. Le test de Fermat203
  - 14.3.1. Le test probabiliste de Fermat 203
  - 14.4. Un théorème d'Euler205
  - 14.5. Le cas des nombres premiers de Mersenne205
  - 14.5.1. Le test de Lucas-Lehmer 206
  - 14.5.2. Le test pour les nombres de Proth 208
  - 14.6. Test de Pépin pour les nombres de Fermat209
  - 14.7. Théorème de Lucas ou de Lucas-Lehmer210
  - 14.7.1. L'amélioration de Pocklington 213
  - 14.8. Le test de primalité de Solovay-Strassen213
  - 14.8.1. Mise en oeuvre pratique 214
  - 14.9. Le test de non-primalité de Rabin Miller215
  - 14.9.1. Le critère d'Euler 216
  - 14.9.2. Le théorème de Miller 217
  - 14.9.3. Le théorème de Rabin 218
  - 14.9.4. Le test de Rabin-Miller 218
  - 14.10. Autres tests220
  - 14.11. Conclusion221
  - 15. La factorisation de grands nombres 223
  - 15.1. La factorisation classique223
  - 15.2. Algorithme p - 1 de John Pollard225
  - 15.3. Algorithme Rho de John Pollard228
  - 15.4. Exercice229
  - 15.5. Pour approfondir230
  - 16. La construction de grands nombres premiers 231
  - 16.1. Nombres robustes231
  - 16.1.1. Le théorème de Lucas-Lehmer 232
  - 16.2. La fabrication de nombres premiers robustes232
  - 16.2.1. La méthode de John Gordon 232
  - 16.2.2. Le générateur de Blum-Blum-Shub 233
  - 16.2.3. Méthode aléatoire 235
  - 16.2.4. Construction d'un couple (p, q) de 2 nombres premiers, tels que q divise (p - 1). 235
  - 16.3. Mise en oeuvre235
  - 16.4. Conclusion236
  - 17. Ouverture vers la cryptographie 237
  - 17.1. Introduction237
  - 17.2. Les différentes approches de la cryptographie237
  - 17.3. Les différentes techniques de chiffrement238
  - 17.3.1. Les techniques de chiffrement symétrique 239
  - 17.3.2. Les techniques de chiffrement asymétrique 239
  - 17.3.3. Clé publique 239
  - 17.4. Le principe du système RSA240
  - 17.5. Le système ElGamal242
  - 17.5.1. Principe général 242
  - 17.5.2. Les nombres de Blum 243
  - 17.6. L'authentification243
  - 17.6.1. La signature d'El Gamal 244
  - 17.7. Pour approfondir244
  - 18. Les processeurs d'arithmétiques modulaires 245
  - 18.1. Introduction245
  - 18.2. Les processeurs de ST Microelectronics245
  - 18.3. L'unité de calcul modulaire de SUN246
  - 18.4. Les processeurs d'IBM246
  - 18.5. Les opérations246
  - 18.6. Langages de programmation246
  - 18.7. Conclusion247
  - 19. Annexe A : Les nombres de mersenne 249
  - 19.1. Définition des nombres de Mersenne249
  - 19.2. Quelques théorèmes portant sur les nombres de Mersenne250
  - 19.3. Conjectures251
  - 20. Annexe B : Les nombres de fermat 253
  - 20.1. Définition253
  - 20.2. Relation de récurrence entre nombres de Fermat253
  - 21. Annexe C : Les nombres de carmichaël 255
  - 21.1. Définition255
  - 21.2. Théorème de Korselt établi en 1899255
  - 21.2.1. Conséquences 256
  - 21.3. Construction de nombres de Carmichaël256
  - 21.4. Une infinité de nombres de Carmichaël ?256
  - 22. Bibliographie 257
  - Index alphabétique 259
Origine de la notice:
- BNF