Cours 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)