Mini-cours sur l'arithmétique algorithmique
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)

X.-F. Roblot Dernière modification : 27 February 2017, 10:03