Les nombres de Mersenne sont les nombres 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.
Écrire une table des non-premiers de Mersenne \(M_p = 2^p-1\), pour \(p\) premier inférieur à 103.
Ecrire une fonction facteur_naif(n) qui renvoie le plus petit facteur premier de
\(n\), en calculant la division par tous les entiers impairs inférieurs à \(n\).
Quelle taille d’entiers peut-on factoriser ? Quels sont les nombres de Mersenne que l’on factorise en moins de dix secondes ?
Améliorer la technique avec une fonction facteur_premier(n) n’effectuant
de division que par les nombres premiers donnés par la fonction ithprime
(laquelle utilise une base de nombres premiers précalculés).
Quels sont les nombres de Mersenne qui résistent ?
Illustrer graphiquement le théorème des nombres premiers, qui énonce que \(\pi(x)\sim \frac{x}{\log x}\), où \(\pi(x)\) est le nombre de premiers inférieurs à \(x\).
Écrire une fonction pollard_rho(n) qui calcule les
\(\pgcd(x_{2k}-x_k,n)\),
où \(x_k\) est donné par la suite récurrente \(x_0=1\), \(x_{k+1}=x_k^2+1\bmod n\),
jusqu’à obtenir un facteur premier de \(n\).
Tester la fonction en factorisant les entiers de Mersenne.
Faire afficher le rapport \(i/\sqrt{p}\) où \(i\) est le nombre d’itérations effectuées pour trouver le facteur \(p\).
Vérifier graphiquement que cette méthode a une complexité de \(O(\sqrt p)\) itérations.
Changer de polynôme d’itération : examiner le comportement pour un polynôme linéaire, quadratique, cubique.
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.
Quelle est la probabilité qu’un couple de nombres \(a,b\) tirés uniformément modulo \(n\) soient congrus modulo \(n\) ? soient congrus modulo \(p\) ? Quelle est la probabilité que \(k\) nombres tirés uniformément modulo \(n\) soient tous distincts modulo \(p\) ?
Créer la fonction P:=i0->product(1-j/p,j=1..i0-1);.
En utilisant limit en +infinity, montrer
que \(\log P(2)\) est équivalent à \(-1/p\), \(\log P(3) \sim -3/p\)…
Deviner une formule pour \(\log P(i)\).
En utilisant cette formule, montrer que \(P(k) > 1/2\) dès que \(k\) est de l’ordre \(1.18\sqrt p\).
Note
On rappelle la méthode : si \(n\) possède un facteur premier \(p\) tel que \(p-1\) n’a que de petits facteurs premiers inférieurs à une borne \(B\) (on dit que \(p-1\) est \(B\)-friable), alors puisque \(a^{p-1}=1\bmod p\) on a également \(a^M=1\bmod p\) pour tout multiple \(M\) de \(p-1\), en particulier si l’on prend \(M\) égal à un produit de puissances de tous les petits nombres premiers inférieurs à \(B\).
Concrètement, on part d’un résidu \(a\) premier à \(n\), et pour chaque premier \(p_i\leq B\) on calcule un exposant \(b_i\) tel que \(p_i^{b_i}<n<p_i^{b_i+1}\). On pose \(M_i = M_{i-1}\times p_i^{b_i}\), et on calcule \(pgcd(a^{M_i}-1,n)\). Dès que l’on atteint la borne de friabilité d’un diviseur premier \(p\) de \(n\), \(p\) divise le pgcd.
Implanter la méthode \(p-1\) de Pollard. L’utiliser pour factoriser les premiers nombres de Mersenne.
Expliquer ce qui se passe lorsque l’on essaie de factoriser \(M_{29}\).
Trouver une technique pour adapter la méthode \(p-1\) aux nombres semblables à \(M_{29}\).
On considère l’entier n := 10001 et la base de premiers
\((p_1,\dots p_6) = (-1,2,3,5,7,11)\).
Écrire une fonction friable(a) qui renvoie 1 si a est 11-friable, 0
sinon.
Déterminer 7 entiers \(y\) au voisinage de \(\sqrt{n}\) tels que les \(y^2\bmod n\) sont 11-friables.
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}}\).
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\).
Factoriser 10001.
Généraliser l’algorithme.