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.
ithprime(27)
M:=select(x->(! is_pseudoprime(x)),seq(2^ithprime(k)-1,k,1,27))
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 ?
naif(n):=for(j:=3;j<=n;j++) { if (!irem(n,j)) return(j); }
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 ?
facteur_premier(n) := {
local(p:=2);
for(k:=1;p<n;p:=ithprime(k++)) {
if(!irem(n,p)) return(p);
}
}
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\).
scatterplot(seq([ithprime(k),k],k,1,100))
plot(x/log(x),x,2,ithprime(100))
É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\).
1 2 3 4 5 6 7 8 9 10 11 12 | pollard_rho(n) := {
local x,y,g;
x := 1; y := 1;
g := 1;
while(g == 1) {
x := irem(x^2+1,n);
y := irem(y^2+1,n);
y := irem(y^2+1,n);
g := gcd(x-y,n);
}
g;
}
|
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | pollard_rho2(n) := {
local x,y,g,loops,l;
x := 1; y := 1;
g := 1; loops := 50;
while(g && g == 1) {
for(l:=1;l<loops;l++) {
x := irem(x^2+1,n);
y := irem(y^2+1,n);
y := irem(y^2+1,n);
g := irem(g*(x-y), n);
}
g := gcd(g,n);
}
g;
}
|
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\) ?
Pour \(k\) tirages \(a_1,\dots a_k\), la probabilité de tirer des éléments tous distincts vaut
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.
On considère l’entier n := 10001
et la base de premiers
\((p_1,\dots p_6) = (-1,2,3,5,7,11)\).
friable(a)
qui renvoie 1 si a est 11-friable, 0
sinon.