On appelle nombres de Carmichael les entiers \(n\) non premiers vérifiant l’égalité de Fermat
Déterminer le plus petit nombre de Carmichael.
iscarmichael(n):={
local k;
if(isprime(n)) return(0);
for(k:=2;k<n;k++) {
if( powermod(k,n,n) != k ) return(0);
}
return(1);
}:;
iscarmichael(91);
iscarmichael(1729);
premiercarmichael():={
local (n:=3);
while(!iscarmichael(n)) n++;
return(n);
}:;
n:=premiercarmichael();
def is_carmichael(n):
if is_prime(n):
return False
return all( Mod(k,n)^n == k for k in range(2,n))
is_carmichael(91);
is_carmichael(1729);
def next_carmichael(n=2):
while not is_carmichael(n):
n += 1
return n
next_carmichael()
On donne le critère suivant (Korselt, 1899) : \(n\) est un nombre de Carmichael si et seulement si
Donner la liste des nombres de Carmichael inférieurs à \(10^4\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | korselt(n):={
local k,F;
if(isprime(n)) return(0);
F:=ifactors(n);
for(k:=0;k<length(F);k+=2) {
if(F[k+1]>1) return(0);
if(irem(n-1,F[k]-1)>0) return(0);
}
return(1);
}:;
korselt(561);
korselt(1891);
L:=[]:;
for(n:=3;n<=10000;n++) {
if(korselt(n)) L:=append(L,n);
}:;
L;
|
def korselt(n):
if n < 2 or is_prime(n):
return False
for p,e in factor(n):
if e > 1 or (n - 1) % (p - 1):
return False
return True
[ n for n in range(10000) if korselt(n) ]
On définit un module RSA \(n=pq\), avec
Calculer les racines carrées de \(1\) dans \(\Z/n\Z\). Combien y en a-t-il ?
D’après le lemme chinois, ce sont \((\pm1,\pm1)\in\Z/p\Z\times\Z/q\Z\). On les relève modulo \(n\) par une relation de Bezout \(up+vq=1\) en \(\set{\pm1 up+ \pm1 vq}\).
p := (15^73-1)/14:; q := (11^73-1)/10 :;
g := egcd(p,q);
Montrer que si \(a\neq\pm1\bmod n\) vérifie \(a^2=1\bmod n\), alors \(n\) n’est pas premier, et \(\pgcd(a-1,n)\) est un facteur non trivial de \(n\).
410041 est un nombre de Carmichael. Le factoriser en déterminant une telle valeur de \(a\).
Supposons que l’on connaisse les exposants de chiffrement et de déchiffrement \(ed\) du système RSA. On pose \(ed-1=2^rm\). Montrer qu’au plus la moitié des \(a\in(\Z/n\Z)^\ast\) vérifie \(a^m=1\) ou \(a^{2^jm}=-1\) pour \(0\leq j<m\).
Comme \((-1)^m=1\), soit \(q\) la plus grande puissance de la forme \(2^im\) telle qu’il existe \(a_0\), \(a_0^q=-1\). Alors l’ensemble des \(a\) cherché est contenu dans \(H=\set{a, a^q=\pm1}\), et \(H\) est un sous-groupe d’indice \(2\) de \(\set{a,a^q=\pm1\bmod p\text{ et }a^q=\pm1\bmod q}\).
En déduire un algorithme pour factoriser \(n\).
Faire le test avec votre voisin : construire et échanger des clefs RSA, et les casser quand on connaît \(e\) et \(d\).
Soit \(n\) un entier impair, on pose \(n-1=2^km\) avec \(m\) impair. Si \(n\) est premier, alors pour tout entier \(a<n\) on a
Écrire une fonction miller(n,a) qui vérifie que \(n\) passe le test
de Miller pour l’entier \(a\). On ne factorisera pas \(n-1\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | miller(n,a):={
local m,k,b,j;
m:= n-1; k:= 0;
while(irem(m,2)==0) {
m/=2; k+=1;
};
b := powmod(a,m,n);
if(b==1) return(1);
for(j:=0;j<k;j++) {
if(b==n-1) return(1);
b := irem(b^2,n);
};
return(0);
}:;
|
Combien y a-t-il d’entiers \(a\) permettant de prouver la non primalité de \(n=1729\) ?
nb_faux(n):={
local (k:=0),a;
for(a:=0;a<1729;a++){
if(miller(n,a)) k++;
};
return(k);
}:;
nb_faux(1729);
nb_faux(1891);
On appelle faux témoin de primalité pour l’entier \(n\) non premier tout entier \(a\) qui passe le test de Miller.
Le théorème de Rabin énonce que si \(n\) n’est pas premier, le nombre de faux-témoins est inférieur à \(\frac{\phi(n)}4\).
Au bout de combien d’essais d’entiers \(a\) qui passent le test de Miller peut-on affirmer que \(n\) est premier avec \(99,99\%\) de certitude ?
ntests:=ceil(log(1-99.99/100)/log(1/4));
Écrire un test rabin(n) qui effectue ce test.
1 2 3 4 5 6 7 8 9 10 11 | rabin(n):={
local k,a;
for(k:=0;k<ntests;k++) {
a := rand(n);
if(miller(n,a)==0) return(0);
}
return(1);
}:;
rabin(1729);
rabin(1891);
rabin(nextprime(1234567890));
|
On considère un cas plus compliqué
La méthode précédente permet-elle de calculer les racines carrées de \(6\) modulo \(n=pq\) ?
Cet algorithme consiste à passer par l’extension \(\F_{p^2}\), dans laquelle tout élément de \(\F_p\) possède une racine carrée. Pour tout \(a\in\F_p\), en notant \(x\in\F_{p^2}\) une racine de \(x^2-a\), on a la disjonction
de sorte que pour tout \(u\) dans \(\F_p\) et \(v\in\F_{p^2}\) une racine d’un non résidu quadratique, on a
L’astuce de Cipolla consiste à choisir \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\), et définir \(v\) comme une racine carrée de \(u^2-a\). Alors le calcul ci-dessus montre que l’élément
est une racine carrée de \(a\), dans \(\F_{p^2}\). Il appartient en particulier à \(\F_p\) si et seulement si \(a\) est un carré dans \(\F_p\).
Le calcul de \(x\) se fait alors de la manière suivante :