Cours d'algèbre et d'algorithmique, 2e édition
Auteur :
Collection :
Comment savoir si un nombre entier est composé ou premier, et dans le cas où il est composé, comment obtenir sa factorisation primaire ?
Ces questions essentielles de la théorie des nombres sont au centre des préoccupations de tous ceux qui étudient une discipline frontière entre les mathématiques et l'informatique : la cryptologie.
Commande avant 16h,
expédié le jour même (lu. - ve.)
Livraison express sous 48h.
Rubrique :
Pierre Meunier Series - Maths
ISBN :
9782364930971
Référence :
1097
Année de parution :
2014
Comment savoir si un nombre entier est composé ou premier, et dans le cas où il est composé, comment obtenir sa factorisation primaire ?
Ces questions essentielles de la théorie des nombres sont au centre des préoccupations de tous ceux qui étudient une discipline frontière entre les mathématiques et l'informatique : la cryptologie.
Science des écritures secrètes, elle utilise des protocoles mathématiques nécessitant une connaissance approfondie en algèbre : groupes, anneaux, corps finis, fractions continues, courbes elliptiques, mais aussi en algorithmique : tests de primalité, algorithmes de factorisation.
Puissamment aidés par l'ordinateur et la très grande qualité de leurs travaux, les mathématiciens ont permis à la cryptologie moderne, « moteur de la théorie des nombres », d'acquérir des lettres de noblesse incontestables que cet ouvrage souhaite faire partager au public scientifique le plus large possible : étudiants en Classes Préparatoires, étudiants, candidats au CAPES ou à l'Agrégation, ingénieurs, enseignants.
| Référence : | 1097 |
| Nombre de pages : | 360 |
| Format : | 14,5x20,5 |
| Reliure : | Broché |
| Rôle | |
|---|---|
| Meunier Pierre | Auteur |
Table des matières
Introduction
CHAPITRE 1 Les groupes
1.1 Monoïdes et groupes
1.1.1 Définitions
1.1.2 Sous-groupes et groupes quotients :
1.2 Groupes monogènes et groupes cycliques
1.2.1 Introduction
1.2.2 Générateurs d’un groupe cyclique
1.2.3 Sous-groupes d’un groupe cyclique
1.2.4 Produit de groupes cycliques
1.2.5 Exposant d’un groupe fini; cas où ce groupe est abélien
1.3 Le problème du logarithme discret dans un groupe cyclique
1.3.1 Instance du problème
1.3.2 Algorithme de Shanks (algorithme de collision)
1.3.3 Algorithme de Pohlig-Hellman
1.4 Sous-groupes additifs de Zn ; application à la struc¬ture des groupes abéliens; cas particuliers des groupes
abéliens finis
1.4.1 Sous-groupes additifs de Zn
1.4.2 Les diviseurs élémentaires d’une matrice à coefficients entiers
1.4.3 Retour aux sous-groupes de (Zn +)
1.4.4 Structure des groupes abéliens finis
1.5 Indicatrice d’Euler
1.6 Couplages de groupes
1.6.1 Définition
1.6.2 Exemples de couplages
1.6.3 Intérêt de la notion de couplage
CHAPITRE 2 Anneaux et corps; Corps finis
2.1 Définitions
2.1.1 Les anneaux
2.1.2 Anneaux quotients
2.1.3 Idéaux maximaux d’un anneau commutatif
2.2 Les corps - Caractéristique d’un corps - Polynômes cyclotomiques sur un corps K - Racines primitives de l’unité dans un corps
2.2.1 Le groupe multiplicatif d’un corps K
2.2.2 Caractéristique d’un corps
2.2.3 Les polynômes cyclotomiques sur un corps K
2.3 Les corps finis; le corps à pm éléments
2.3.1 Un lemme fondamental et ses conséquences
2.3.2 Le corps à pm éléments
2.3.3 Les sous-corps d’un corps fini
2.4 Clôture algébrique d’un corps
2.4.1 Elements algébriques; extension algébrique d’un corps K
2.4.2 Généralisation
2.4.3 Clôture algébrique d’un corps
2.4.4 Etude d’un exemple
2.4.5 Un résultat utile pour les courbes elliptiques
2.4.6 Des remarques pour finir
CHAPITRE 3 Anneaux Z et K[X] - Résiduosité quadratique
3.1 Anneaux quotients de Z
3.1.1 Généralités
3.1.2 Condition nécessaire et suffisante pour que (Gn, .)soit cyclique
3.2 Anneaux quotients dans K[X]
3.3 Le théorème chinois dans Z ou dans K[X]
3.4 Algorithmes d’Euclide dans Z, ou dans K [X] ; applications 3.5 Résidus quadratiques modulo p premiers - Symbole de Legendre
3.6 Application à la décomposition de Fn(X) en facteurs premiers sur un corps premier de Frobénius IFp dans un cas particulier utile en cryptologie
3.6.1 Les polynômes g1 et g2 de Fp[X]
3.6.2 Détermination des polynômes g1 et g2
3.6.3 Etude du cas particulier où n > 7 et p = 3 (mod 4)
3.7 Généralisation: le symbole de Jacobi
3.7.1 Définition
3.7.2 La réciprocité relative au symbole de Jacobi
CHAPITRE 4 Algorithmes - Complexités
4.1 Définitions
4.2 Coût (ie complexité) d’un algorithme - Exemples
4.2.1 Définitions
4.2.2 Quelques exemples (de base)
4.2.3 L’exponentiation rapide dans un monoïde (E, *)
4.2.4 Cas des algorithmes probabilistes de type (i), c’est-à-dire fournissant toujours une réponse
4.3 Algorithmes (ou tests) de primalité de Miller et de Solovay-Strassen
4.3.1 Test de primalité de Miller-Rabin
4.3.2 Test de primalité de Solovay-Strassen
4.4 Coût des algorithmes génériques de Shanks et de Pohlig-Hellman
4.5 Algorithmes de type "index calculus"
4.6 Compléments mathématiques indispensables pour l’étude des algorithmes de calcul d’index
4.6.1 Les fonctions de type sous-exponentiel
4.6.2 Les entiers B-friables
4.6.3 Les polynômes à coefficients entiers
4.6.4 Le résultant de deux polynômes
4.7 L’algorithme de type index calculus de Kraitchik dans Fp
4.7.1 Fonctionnalité et description de cet algorithme
4.7.2 Complexité en temps de cet algorithme probabiliste
4.7.3 Des schémas mesurant les performances
4.7.4 Etude d’un exemple
4.8 L’algorithme de type index-calculus de Schirokauer
4.8.1 Fonctionnalité et schéma du mécanisme
4.8.2 Calcul de a modulo q
4.8.3 Détermination d’un couple (s, t)
4.9 Généralisation : algorithmes de calcul des log-discrets dans les corps non premiers : ?p.. , avec n > 2
4.9.1 Instance du problème
4.9.2 Quelques records de calcul de logarithme discret dans un corps non premier
4.10 Algorithme de factorisation du crible algébrique général (GNFS=General Number Field Sieve)
4.10.1 L’idée
4.10.2 Concrétisation de l’idée
4.10.3 Mise en forme pratique de l’idée : le corps de nombres et le polynôme P
4.10.4 Le crible
4.10.5 L’algèbre linéaire
4.10.6 Exemple d’un cas particulier : les nombres de Cunningham
4.10.7 Résumé et bilan
4.11 Des algorithmes déterministes de primalité : les tests APR-CL et AKS
4.11.1 Le test APR-CL (Ademan-Pomerance Rumely-Cohen-Lenstra)
4.11.2 Le test AKS (Agrawal-Kayal-Saxena)
CHAPITRE 5 Les deux grands cryptosystèmes à clé publique: le RSA et le cryptosystème El-Gamal
5.1 Définitions
5.1.1 Définition d’un cryptosystème à clé publique
5.1.2 Définition de la cryptologie
5.1.3 Les deux principales fonctions "à sens unique"
5.2 Le cryptosystème RSA
5.2.1 La clé K du cryptosystème
5.2.2 Le chiffrement et le déchiffrement
5.2.3 Des considérations pratiques
5.3 Le cryptosystème El-Gamal (logarithme discret)
5.3.1 Création de la clé du cryptosystème
5.3.2 Le chiffrement et le déchiffrement
5.3.3 Le logarithme discret et le standard de signature numérique: le DSS
5.4 Remarques pour finir
5.4.1 Cryptographie symétrique et cryptographie symétrique
5.4.2 Dis-moi ce que tu veux chiffrer, je te proposerai alors un protocole adapté
CHAPITRE 6 Cryptanalyse du RSA
6.1 Quelques compléments mathématiques indispensables
6.1.1 Proposition
6.1.2 Les réduites d’un rationnel
6.2 L’attaque de Wiener du protocole RSA
6.3 Une autre attaque du RSA
6.4 Le théorème de Coppersmith
6.4.1 Instance du problème
6.4.2 Une première application
6.4.3 Une variante de la proposition précédente
6.5 Autres attaques du RSA - Attaque de Hàstad
6.5.1 Cas de deux RSA du type:
6.5.2 Attaque de Hàstad
6.6 Des recommandations et quelques résultats concernant le RSA
6.6.1 Des recommandations
6.6.2 Des résultats
6.6.3 Des records
CHAPITRE 7 Cryptosystème El-Gamal dans (Kn', *) où * est la loi de convolution, Kn étant un corps fini ayant q éléments et n un entier, n = 2
7.1 La loi de convolution * dans Kn '
7.2 Le groupe (G, *)
7.3 Etude du cardinal du groupe (G, *) quand q ? n = 1. Applications; c.n.s. pour que (G, *) soit cyclique
7.3.1 Cardinal de G
7.3.2 Application : cas où (G, *) est cyclique
7.3.3 Exposant du groupe (G, *)
7.4 Cryptosystème El-Gamal dans Kn ' relativement à un sous-groupe cyclique H de (G, *)
7.4.1 Définition
7.4.2 Sécurité selon le choix de H
7.5 Cryptosystème El-Gamal dans K' associé au groupe (G, *) lorsque celui-ci est cyclique; cryptosystèmes induits associés
7.5.1 Observations générales
7.5.2 Mise en forme pratique du cryptosystème
7.5.3 Coût du chiffrement et du déchiffrement
7.5.4 Amélioration du coût du déchiffrement
7.5.5 Cryptosystèmes induits associés
7.6 Exemple de cryptosystème proposé
7.7 Un cryptosystème dans Fnp lorsque (G, *) n’est pas cyclique
7.7.1 Fabrication d’un tel groupe (G, *) et d’un sous groupe cyclique H permettant d’élaborer le cryptosystème
7.7.2 Autre procédé de fabrication d’un sous groupe cyclique H d’ordre maximum dans le cas où le groupe (G, *) n’est pas cyclique
7.8 Quelques observations algébriques pour finir
7.9 Annexes numériques et justifications éditoriales
7.9.1 Une estimation
7.9.2 Des factorisations (utiles pour un cryptosystème de ce chapitre)
7.9.3 Des générateurs (utiles pour un cryptosystème de ce chapitre)
7.9.4 Des "explications" concernant la première de couverture de cet ouvrage
CHAPITRE 8 Les courbes elliptiques
8.1 Introduction
8.1.1 Quelques préliminaires
8.1.2 Le discriminant d’un polynôme de la forme X3+pX + q
8.2 Les courbes elliptiques sur un corps fini ou non de caractéristique distincte de 2 et de 3
8.2.1 Définitions et premières conséquences
8.2.2 Cas où le corps JK est fini
8.2.3 Loi de groupe (additif) sur une courbe elliptique
8.2.4 La n-addition dans (E(JK), +) : polynômes de division
8.2.5 Utilisation d’une clôture algébrique JK du corps JK : le morphisme de Frobénius
8.2.6 Les couplages de Weil
8.2.7 L’algorithme de Schoof
8.2.8 Utilisations cryptographiques des courbes elliptiques
8.2.9 Algorithme de factorisation de Lenstra à l’aide des courbes elliptiques
8.2.10 Des perspectives et une ébauche de généralisation
CHAPITRE 9 Chapitre de conclusion
9.1 Introduction
9.2 Les deux modes de chiffrement
9.2.1 Cryptographie symétrique
9.2.2 Cryptographie asymétrique
9.3 Quelques règles et recommandations
9.4 Des justifications et des perspectives
9.4.1 Clés symétriques
9.4.2 Clés du RSA ou d’un cryptosystème El-Gamal
sur un IFP
9.5 En conclusion
Annexe : Philosophie du cryptosystème du chapitre 7
Postface
Index
Les clients qui ont acheté ce produit ont également acheté...
Livres de l'auteur Pierre Meunier
