Le but de ce projet est de comparer l'efficacité de plusieurs méthodes différentes pour décomposer un nombre en produit de facteurs premiers.
Nous étudierons les algorithmes de factorisations suivants :
-
L'algorithme naïf qui consiste à vérifier si n est divisible par 2 puis, si c'est le cas, recommencer avec n/2, ou si, ce n'est pas le cas, de vérifier si n est divisible par 3 (puis 5, 7, etc...)
-
L'algorithme de Rho Pollard
-
L'algorithme de p-1 de Pollard
-
L'algorithme de Lenstra en utilisant les courbes elliptiques
-
L'algorithme du Crible Quadratique