Primalité¶

tests de composition¶

On augmente la précision flottante à 10000 chiffres via \p10000.

Trouver la première occurrence d’un nombre premier de 1000 chiffres dans la suite des décimales de e=2.71828….

Par exemple, 71 est la première occurrence d’un nombre premier de deux chiffres.

solution ⇲ ⇱ solution

\p10000
e = exp(1); e *= 10^999; n = floor(e);
while(!ispseudoprime(n), e *= 10; n = floor(e) % 10^1000); n

3136020572481765851180630364428123149655070475102544650117272115551948668508003685322818315219600373562527944951582841882947876108526398139559900673764829224437528718462457803619298197139914756448826260390338144182326251509748279877799643730899703888677822713836057729788241256119071766394650706330452795466185509666618566470971134447401607046262156807174818778443714369882185596709591025968620023537185887485696522000503117343920732113908032936344797273559552773490717837934216370120500545132638354400018632399149070547977805669785335804896690629511943247309958765523681285904138324116072260299833053537087613893963917795745401613722361878936526053815584158718692553860616477983402543512843961294603529133259427949043372990857315802909586313826832914771163963370924003168945863606064584592512699465572483918656420975268508230754425459937691704197778008536273094171016343490769642372229435236612557250881477922315197477806056967253801718077636034624592787784658506560507808442115296975218908740196609

Combien d’entiers (non premiers) inférieurs à \(10^5\) échouent au test de Fermat pour le témoin \(a=2\) ?
solution ⇲ ⇱ solution
r = 0 { forstep(n=3,10^5,2, if( Mod(2,n)^(n-1) == 1 && !ispseudoprime(n), r++) ); } r
78

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) = {
  if(ispseudoprime(n),0,
    for(a=2,n-1,
      if(Mod(a,n)^n!=a,return(0))
      );
    return(1)
   );
 }

select(n->iscarmichael(n),[1..2000]);
[1, 561, 1105, 1729]

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\]

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

solution ⇲ ⇱ solution

korselt(n) = {
  f = factor(n);
  l = #f[,1];
  if(l<3,return(0));
  for(k=1,l,
    if(f[k,2]>1||(n-1)%(f[k,1]-1),return(0))
    );
  return(1);
}
all_korselt(nmax,nmin=3) = {
  r = [];
  for(n=nmin,nmax,if(korselt(n),r = concat(r,n)));
  r;
}
all_korselt(10^4)
[561, 1105, 1729, 2465, 2821, 6601, 8911]

Vérifier que si trois entiers de la forme 6k+1, 12k+1 et 18k+1 sont premiers, leur produit est un nombre de Carmichael. Trouver un nombre de Carmichael de plus de 512 bits…

solution ⇲ ⇱ solution

carmichael6(kmin=1) = {
  k = kmin;
  while(!(  ispseudoprime(6*k+1)
          &&ispseudoprime(12*k+1)
          &&ispseudoprime(18*k+1)
          ),k++);
    (6*k+1)*(12*k+1)*(18*k+1);
  }
carmichael6(2^170)
4344129769301401460261984099418694145303314525900028760822128448914427231094150784813606434296173246812928418275038069952188826321552187933279119120093693401

Le nombre suivant est un nombre de Carmichael. Le factoriser (cf. la démonstration du test de Miller-Rabin).

N=97813455129498842710230400113630498245881558640567324287104213932102879660880918510887014947755835163495934221548629874517823291634609692559980761686417054526911479906757730974279888813085068366706684350679371195216107796622788103816872261267574522679027667584478176395367282018185395042343786246489184709293340088800945590372506799692922338445090533706879732239021648221527977637074573468077956302878299881403477258759211883733416172941492391255621065960620525189669354603939131440572613006343278733269222848184032588169555553263214874906789767857843662899311528428991287722486261737025592761803861732590617556287449483169212157338026787562556548998043501534490393822763987452254202911484976829613770404898364887113402459655527257670225007659729

solution ⇲ ⇱ solution

N=97813455129498842710230400113630498245881558640567324287104213932102879660880918510887014947755835163495934221548629874517823291634609692559980761686417054526911479906757730974279888813085068366706684350679371195216107796622788103816872261267574522679027667584478176395367282018185395042343786246489184709293340088800945590372506799692922338445090533706879732239021648221527977637074573468077956302878299881403477258759211883733416172941492391255621065960620525189669354603939131440572613006343278733269222848184032588169555553263214874906789767857843662899311528428991287722486261737025592761803861732590617556287449483169212157338026787562556548998043501534490393822763987452254202911484976829613770404898364887113402459655527257670225007659729
a=Mod(2,N)
a^(N-1)
a^((N-1)/2)
a^((N-1)/4)
a^((N-1)/8)
f1 = gcd(lift(%)+1,N)
ispseudprime(f1)
N2 = N/f1
a = Mod(2,N2)
a^(N2-1)
a^((N2-1)/2)
a^((N2-1)/4)
f2 = gcd(lift(%)+1,N2)
ispseudoprime(f2)
f3 = N2/f2
ispseudoprime(f3)

Trouver un nombre de Carmichael supérieur à 2^256.

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{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}\]

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

Théorème de Rabin¶

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

Écrire une fonction card_temoins(n) qui compte le nombre de témoins de Rabin permettant de prouver la non-primalité de n, et exhiber un entier \(n\) inférieur à 5000 pour lequel ce nombre vaut \(\frac34\varphi(n)\). Étudier ce nombre.

solution ⇲ ⇱ solution

sage: def is_witness_MR(a,m,r):
...     # assume n-1 = 2^r*m and a mod n
...     ak = a^m
...     if ak == -1 or ak == 1: return False
...     for i in range(r):
...       ak = ak^2
...       if ak == -1: return False
...       if ak == 1: return True
...     return True
sage: def card_witness_MR(n):
...     r,m = 0,n-1
...     while not m%2:
...       r,m = r+1,m/2
...     return sum([is_witness_MR(Mod(i,n),m,r) for i in xrange(2,n-2)])
sage: card_witness_MR(1729)
1565
sage: card_witness_MR(991)
0
sage: prop = [ card_witness_MR(n)*1./n for n in xrange(1000,2000) ] # long time
sage: list_plot(prop) + line([(,0.75),(1000,0.75)]) # long time

On remarque le nombre 1891.

sage: card_witness_MR(991)
sage: factor(1891)
31 * 61
sage: 1890/2
945

Calculons le nombre de non-témoins de Rabin pour ce nombre : ce sont les résidus a tels que a^{(n-1)/2}=±1. En décomposant selon p et q, il y a (p-1)/2 racines de chaque modulo p, et (q-1)/4 modulo q. Ce qui fait (p-1)(q-1)/4=phi(n)/4 non témoins, ce qui constitue un cas otimal du théorème de Rabin.

Produire une suite d’entiers \(n\) pour lesquels on a exactement \(\varphi(n)/4\) non-témoins de Rabin.
solution ⇲ ⇱ solution
Les observations précédentes sont valides dès que n est un produit pq avec q=2p-1 et pequiv 3 mod 4. On recherche de tels entiers.
sage: def bad_MR_numbers(M=100000,m=7): ... for p in primes(m,M): ... if p%4==1: continue ... q = 2*p-1 ... if not is_pseudoprime(q): continue ... yield p*q sage: list(bad_MR_numbers(400)) [91, 703, 1891, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903]
Remarque : il est très raisonnable de conjecturer qu’il y a une infinité de tels nombres, mais c’est un problème difficile (analogue à la conjecture des nombres premiers jumeaux).

On considère l’entier

n = 11954476132467023197222680729531533414649277025136974764434677668343207602785272295739927522285789903

Démontrer que c’est un mauvais entier de Rabin.

solution ⇲ ⇱ solution

On a en quelques essais du test de Fermat

>>> Mod(2,n)^(n-1)
11954476132467023197222680729531533414649277025136665514036036476312847379568940676246713752939995588
>>> Mod(3,n)^(n-1)
1
>>> Mod(3,n)^((n-1)/2)
309250398641192030360223216331619493213769345794315
>>> gcd(lift(_)-1,n)
154625199320596015180111608165809746606884672897157
>>> n/_
77312599660298007590055804082904873303442336448579

Ainsi \(n\) est de la forme \(pq=p(2p-1)\) avec \(p=3\bmod 4\), c’est un mauvais entier de Rabin.

Primalité¶

tests de composition¶

Nombres de Carmichael¶

Test de Miller-Rabin¶

Théorème de Rabin¶

Table des matières

Table des matières