| Description |
|
| Partie I : Introduction |
1. Références ; 2. Complexité. (Télécharger cette partie) |
|
| Partie II : Arithmétique rapide |
1. Opérations de base sur les entiers longs ; 2. Polynômes à coefficients dans \(\mathbb{Z}/2^w\mathbb{Z}\) ; 3. Multiplication rapide par la méthode de Karatsuba ; 4. Multiplication rapide par FFT ; 5. Division euclidienne rapide par la méthode de Newton. (Télécharger cette partie) |
|
| Partie III : Algorithmes classiques |
1. Coût de la multiplication et de la division ; 2. Exponentiation rapide ; 3. Algorithme d'Euclide ; 4. Algorithme d'Euclide étendu ; 5. Reconstruction d'un nombre rationnel ; 6. Carrés dans \(\mathbb{F}_p\) : symbole de Legendre-Jacobi ; 7. Carrés dans \(\mathbb{F}_p\) : calcul des racines carrées ; 8. L'algorithme LLL ; 9. Quelques applications de LLL. (Télécharger cette partie) |
|
| Partie IV : Factorisation des entiers |
1. Énoncé du problème ; 2. algorithmes préliminaires : primalité et pseudo-primalité, reconnaissance des puissances de premiers ; 3. Quelques résultats d'arithmétique : nombre et tailles des facteurs premiers, nombres \(B\)-friables ; 4. algorithmes exponentiels : divisions successives, méthode de Fermat, méthode de Gauss, méthode \(p-1\) de Pollard, méthode \(\rho\) de Pollard, méthode des factorielles ; 5. algorithmes sous-exponentiels, crible quadratique de Pomerance, méthode ECM de Lenstra, crible du corps de nombres. (Télécharger cette partie) |
|