Primalité¶

Note

Quelques rappels d’arithmétique : l’anneau \(\Z/n\Z\), le groupe des inversibles \((\Z/n\Z)^\ast\), petit théorèmes de Fermat et d’Euler, isomorphisme chinois, \((\Z_{p^e}\Z)^\ast\) est cyclique pour \(p>2\).

Tests de composition¶

Le petit théorème de Fermat énonce que si \(p\) est premier, tout entier \(a\) vérifie

\[a^p \equiv a\bmod p\]

test de Fermat et nombres de Carmichael¶

On appelle nombres de Carmichael les exceptions à la réciproque de l’énoncé de Fermat, c’est-à-dire les entiers \(n\) non premiers vérifiant

\[\forall a\in\N, a^n \equiv a\bmod n.\]

Déterminer le plus petit nombre de Carmichael.

solution ⇲ ⇱ solution

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();

On donne le critère suivant (Korselt, 1899) : \(n\) est un nombre de Carmichael si et seulement si

\[\forall p\mid n, p^2\nmid n \text{ et } p-1\mid n-1\]

Donner la liste des nombres de Carmichael inférieurs à \(10^4\).

solution ⇲ ⇱ solution

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;

Plus généralement (théorème d’Euler), on a \(a^{\phi(n)}\equiv 1\bmod n\) pour tout \(a\in(\Z/n\Z)^\ast\).

Montrer que pour tout entier \(p\) premier impair et tout entier \(a\) premier à \(p\), \(a^{p-2}\equiv a^{-1}\bmod p\).

racines carrées¶

Résoudre l’équation \(x^2=1\) dans \(\Z/19\Z\).

solution ⇲ ⇱ solution
Puisque \(\Z/19\Z\) est un corps, \(x^2-1\) n’a que deux racines \(\pm1\).
Résoudre l’équation \(x^2=1\) dans \(\Z/15\Z\).

solution ⇲ ⇱ solution
Cette fois on peut avoir plus de deux racines. On résout en décomposant selon le lemme chinois \(\Z/15\Z\simeq\Z/3\Z\times\Z/5\Z\), où le membre de droite fait apparaître deux corps, de sorte que \(x\) est solution si et seulement si \(x\equiv\pm1\bmod 3\) et \(x\equiv \pm1\bmod 5\), soit les \(4\) solutions \(1,-1,4,11\).
Déterminer les racines carrées de \(1\) modulo 2325781.
solution ⇲ ⇱ solution
on factorise:
ifactor(2325781)
et on récupère comme précédemment les 4 solutions via le lemme chinois, les deux solutions évidentes \(\pm1\) et \(\pm x\) où \(x\) vaut
ichrem([1,523],[-1,4447])
Sachant que \(75569613259^2=1 \mod 98765432111\), comment peut-on en déduire une factorisation de l’entier 98765432111 ?
solution ⇲ ⇱ solution
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\).
Soit \(p\) un nombre premier congru à 3 modulo 4. Montrer que pour tout entier \(y\), en posant \(x=y^{\frac{p+1}4}\) :
- ou bien \(x\) et \(-x\) sont les racines carrées de \(y\) ;
- ou bien \(y\) n’a pas de racines carrées et \(x\) et \(-x\) sont celles de \(-y\).
Programmer une fonction squareroots(y,p) qui calcule les racines de \(y\) modulo \(p\), si elles existent.
Déterminer toutes les racines carrées de 1522756 modulo 2325781.

test de Miller-Rabin¶

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

\[\begin{split}\begin{cases} \text{ou bien } a^m \equiv 1\bmod n\\ \text{ou bien } \exists i\in[0..k-1], a^{2^im}\equiv -1\bmod n. \end{cases}\end{split}\]

É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\).

solution ⇲ ⇱ solution

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\) ?

solution ⇲ ⇱ solution

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 ?
solution ⇲ ⇱ solution
ntests:=ceil(log(1-99.99/100)/log(1/4));

Écrire un test rabin(n) qui effectue ce test.

solution ⇲ ⇱ solution

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));

Trouver un nombre pseudo-premier de 1000 chiffres se terminant par 2017.
solution xcas ⇲ ⇱ solution xcas
p := 1:; while( !rabin(p) ) { p := rand(10^996)*10^4+2017;}:; p;
Le nombre suivant est un nombre de Carmichael. Le factoriser en utilisant le test de Miller-Rabin (remarquer que son échec fournit une factorisation).
```
N := 410041
```

Preuves de primalité : la méthode p-1¶

Note

On peut démontrer qu’un entier est premier à l’aide de la caractérisation suivante :

\(n\) est premier
\((\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

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 produira 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], [] ] ]
  ]

solution xcas ⇲ ⇱ solution xcas

On commence par factoriser \(n-1\)

ifactor(n-1)

3245449974875834596959672820248144244558730938369

n2 = 11530154156599485404081801977007359;
ifactor(n2-1);

On pourra vérifier avec la fonction

checkprime(C) := {
  local n,a,F,L,l,k,R,LL;
  n := C[0];
  a := C[1];
  F := C[2];
  L := C[3];
  // verification de la factorisation
  l := length(F)/2;
  if( product(F[2*k]^F[2*k+1],k,0,l-1) + 1 != n) return 0;
  // vérification de l'ordre
  if(powermod(a,,n-1,n) != 1) return 0;
  for(k:=0;k<l;k++) { if( powermod(a,(n-1)/F[2*k],n) == 1) return 0; }
  // premiers a verifier
  R  := seq( F[2*k], k, 0, l-1);
  R := select( x -> x > 1000, R);
  if( length(R) != length(L) ) return 0;
  // verification des primalites de L
  LL := select( checkprime, L);
  LL := map( LL, c -> c[0] );
  return (sort(LL) == sort(R) );
}

Faire l’inverse, construire des nombres premiers dont on démontre aisément la primalité par la méthode p-1.

Primalité¶

Tests de composition¶

test de Fermat et nombres de Carmichael¶

racines carrées¶

test de Miller-Rabin¶

Preuves de primalité : la méthode p-1¶

Table Of Contents

Plan

Langage