9. Factorisation d’entiers

Les premiers de Mersenne sont les nombres premiers de la forme \(2^p-1\).

Pour tester les factorisations, on va considérer les nombres de Mersenne \(M_p=2^p-1\) qui ne sont pas premiers.

1. Écrire une table des premiers non-premiers de Mersenne \(M_p = 2^p-1\), pour \(p\) premier inférieur à 103.

9.1. Méthode rho de Pollard

1. Écrire une fonction pollard_rho(n,a,x0) implantant la méthode rho de Pollard. Le paramètre a permet de choisir l’itération \(x^2+a\), et x0 détermine l’initialisation.

2. Tester la fonction en factorisant les entiers de Mersenne.

3. Faire afficher le rapport \(i/\sqrt{p}\) où \(i\) est le nombre d’itérations effectuées pour trouver le facteur \(p\). Vérifier que l’itération satisfait au paradoxe des anniversaires.

4. Changer également de polynôme d’itération : examiner le comportement pour un polynôme linéaire, quadratique, cubique.

5. Modifier pollard_rho en ajoutant un paramètre loops qui permet de diminuer le nombre de calculs de pgcd en accumulant le produit des u-v pour effectuer le pgcd toutes les loops itérations.

   Examiner le gain obtenu sur la factorisation des nombres de Mersenne.

9.2. Méthode p-1 de Pollard

On rappelle la méthode : on se donne une borne \(B\), et pour chaque premier \(p_i< B\) on calcule un exposant \(b_i\) tel que \(p_i^{b_i}<n<p_i^{b_i+1}\). On pose \(M\) le produit des \(p_i^{b_i}\). On sait alors que si \(p\) est un diviseur de \(n\) tel que \(p-1\) est \(B\) friable, \(p\) divise \(pgcd(a^M-1,n)\) pour tout \(a\) premier à \(n\).

1. Implanter la méthode \(p-1\) de Pollard. L’utiliser pour factoriser les premiers nombres de Mersenne.
2. Expliquer ce qui se passe lorsque l’on essaie de factoriser \(M_{29}\).

9.3. Méthode de Dixon

On considère l’entier \(n=10001\) et la base de premiers \((p_1,\dots p_6) = (-1,2,3,5,7,11)\).

1. Écrire une fonction friable(a) qui renvoie 1 si a est 11-friable, 0 sinon.
2. Déterminer 7 entiers \(y\) au voisinage de \(\sqrt{n}\) tels que les \(y^2\bmod n\) sont 11-friables.
3. Construire la matrice \(A\in M_{7,6}(\Z)\) des exposants \(e_{i,j}\) dans la factorisation des \(y_i^2 = \prod_{j=1}^7 p_j^{e_{i,j}}\).
4. Calculer le noyau de \(A \mod 2\), et en déduire deux entiers \(a\) et \(b\) tels que \(a\not\equiv b\bmod n\) mais \(a^2\equiv b^2\bmod n\).
5. Factoriser 10001.
6. Généraliser l’algorithme.