Sachant que \(75569613259^2=1 \mod 98765432111\), comment peut-on en déduire une factorisation de l’entier 98765432111 ?
il s’agit d’une racine \(x\neq\pm1\bmod n\) de \(x^2-1\), donc n n’est pas premier.
Et si \(n=pq\), on a par exemple \(x\equiv 1\bmod p\) et \(x\equiv -1\bmod q\) de sorte que \(p\mid x-1\) et \(q\nmid x-1\), si bien qu’on retrouve \(p\) en calculant \(p=\pgcd(x-1,n)\).
igcd(75569613259-1,98765432111)
Connaître des racines carrées (non triviales) modulo \(n\) est équivalent à connaître une factorisation (non-triviale) de \(n\).
Trouver un nombre pseudo-premier de 1000 chiffres se terminant par 2017.
p := 1:; while( !rabin(p) ) { p := rand(10^996)*10^4+2017;}:; p;
On peut démontrer qu’un entier est premier à l’aide de la caractérisation suivante :
Proposition
\(n\) est premier ssi \((\Z/n\Z)^\ast\) est cyclique d’ordre \(n-1\).
De plus, dans ce cas, il y a \(\phi(n-1)\) générateurs du groupe multiplicatif, donc une proportion assez élevée.
Il suffit donc de tirer des résidus \(a\) au hasard, et d’être en mesure de montrer pour l’un d’eux que son ordre vaut exactment \(n-1\).
On utilise le lemme suivant
Lemme
Soit \(a\) un élément d’un groupe \(G\) et un exposant \(m\) tel que \(a^m=1\). Alors \(a\) est d’ordre exactement \(m\) si et seulement si \(a^{\frac mp}\neq 1\) pour tout diviseur premier \(p\mid m\).
Fournir une démonstration que n1 := 145531 est un nombre premier.
Démontrer ensuite la primalité de n2 := 40963336208247701473.
On peut exhiber une preuve sous forme de certificat, c’est-à-dire
une liste [n, a, F, L] où
n est le nombre dont on démontre la primalité ;a est un générateur de \((\Z/n\Z)^\ast\) ;F est la factorisation de \(n-1\) (obtenue à l’aide de la fonction
facteurs_premiers()) ;L est une liste formée de certificats de primalité pour chaque premier \(p>1000\)
de la factorisation F.Un exemple de certificat
[ 192383, 5, [ 2, 1, 43, 1, 2237, 1],
[ [2237, 2, [2, 2, 13, 1, 43, 1], [] ] ]
]
On commence par factoriser \(n-1\)
ifactor(n-1)
3245449974875834596959672820248144244558730938369
n2 = 11530154156599485404081801977007359;
ifactor(n2-1);