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.

Tests de composition¶

test de Fermat et nombres de Carmichael¶

On pose

n := prevprime(10^1000)*nextprime(10^1000)

Montrer que n n’est pas premier à l’aide du test de Fermat.

solution xcas ⇲ ⇱ solution xcas

n := prevprime(10^1000)*nextprime(10^1000);
(2 % n)^n == 2

On appelle nombres de Carmichael les contre-exemples à 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 xcas ⇲ ⇱ solution xcas

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\) non premier est un nombre de Carmichael si et seulement si

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

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

solution xcas ⇲ ⇱ solution xcas

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;

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 xcas ⇲ ⇱ solution xcas

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 xcas ⇲ ⇱ solution xcas
nb_faux(n) := sum(miller(n,a),a,0,n-1); 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\). Cette borne est atteinte, par exemple

nb_faux(1891); euler(1891)/4;
nb_faux(8911); euler(8911)/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,999\%\) de certitude ?
solution xcas ⇲ ⇱ solution xcas
ntests:=ceil(log(1-99.999/100)/log(1/4));

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

solution xcas ⇲ ⇱ solution xcas

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 2013.
solution xcas ⇲ ⇱ solution xcas
p := 1:; while( !rabin(p) ) { p := rand(10^996)*10^4+2013;}:; 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.
Démontrer que
```
n := 3245449974875834596959672820248144244558730938369
```
est un nombre premier.

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

Primalité¶

Tests de composition¶

test de Fermat et nombres de Carmichael¶

test de Miller-Rabin¶

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

Table Of Contents

Plan

Langage