Composition, primalité¶

Soit \(n\in\N\). Le théorème fondamental de l’arithmétique n’étant pas effectif, on peut se poser trois questions de difficulté algorithmique croissante :

\(n\) composé ? tests de composition
\(n\) premier ? preuves de primalité
factorisation de \(n\) ? méthodes de factorisation

Répondre oui à la première question est facile et l’on peut le faire pour des entiers de milliards de chiffres, via les tests de composition.

Si l’on n’arrive pas à montrer qu’un entier est composé, démontrer rigoureusement qu’il est premier est possible en temps polynomial (AKS, mais ce n’est pas le plus efficace). En pratique cela marche pour des entiers ayant jusqu’à quelques milliers de chiffres.

Enfin, même si l’on sait qu’un entier est composé, on ne sait pas en déterminer un facteur efficacement. Les meilleurs algorithmes sont sous-exponentiels, et en pratique

on peut factoriser en quelques millisecondes des entiers de moins de 30 chiffres
pour 100 chiffres, il faut quelques heures
le record de factorisation est le module RSA-250, soit 829 bits.
dix ans plus tôt, la mise au point du programme de factorisation Cado-nfs lors de la factorisation de RSA-768 (768 bits pour 230 chiffres) avait mobilisé une équipe d’experts pendant trois ans, et des centaines de machines.

Résultats¶

Théorème des nombres premiers

Soit \(\pi(x)=\#\set{p\leq x,p \text{ premier}}\). Alors \(\pi(x)\sim \frac{x}{\log x}\).

Tests de composition¶

Le but est de trouver un comportement qui caractérise les nombres premiers, et qui soit facile à tester.

Test de Fermat¶

Par exemple le petit théorème de Fermat

test de Fermat

Soit \(n\in\N\). S’il existe \(a\in(\Z/n\Z)^\ast\) tel que \(a^{n-1}\neq 1\bmod n\), alors \(n\) n’est pas premier.

Ce critère est très efficace en pratique : en tirant un résidu \(a\) au hasard, cela permet de démontrer la non-primalité de la plupart des nombres.

Par exemple, parmi les 100 000 premiers entiers impairs de 1024 bits, tous ceux qui ne sont pas premiers échouent au test de Fermat pour \(a=2\) ou \(a=3\) (et l’on isole 292 nombres premiers).

n = 1<<1023 + 1; c = 0;
for(i=1,10^5,if(Mod(2,n)^n==2,c++;if(!ispseudoprime(n),print(n)));n+=2);c

Toutefois, l’énoncé de Fermat ne caractérise pas les nombres premiers.

Définition

On appelle nombres de Carmichael les entiers \(n\) non premiers tels que \(\forall a\in(\Z/n\Z)^\ast, a^{n-1}\equiv 1\bmod n\).

Ces nombres existent, par exemple : \(561\), \(1729\).

{ for(n=2,2000,
  if(!isprime(n)&&sum(a=1,n-1,Mod(a,n)^n==a)==n-1,
  print(n)) ) }

Infinité démontrée en 1994 (Granville).

Théorème

Soit \(C(X)\) le nombre de nombres de Carmichaël inférieurs à \(X\). Pour \(X>10^4\), on a

\[X^{1/3} \lt X \lt X e^{-2\log(X)\log^3(X)/\log^2(X)}\]

On sait même les caractériser complètement :

Proposition

Soit \(n\) un entier non premier, et \(n=\prod_i p_i^{e_i}\) sa factorisation en produit de facteurs premiers.

Alors \(n\) est de Carmichael si et seulement si pour tout \(i\), \(e_i=1\) et \(p_i-1\mid n-1\).

Démonstration

Supposons d’abord que \(n\) vérifie le critère, alors pour tout \(a\), \(a^{n-1}=1\bmod p_i\) donc \(n\) est de Carmichael.

Réciproquement, si \(n\) est de Carmichael alors modulo chaque \(p_i^{e_i}\) on doit avoir \(a^{n-1}=1\bmod p_i^{e_i}\) pour tout \(a\), en particulier pour \(a\) un générateur de \((\Z/p_i^{e_i}\Z)^\times\), donc d’ordre \(\varphi(p_i^{e_i})\). Cela impose \(\varphi(p_i^{e_i})=(p_i-1)p_i^{e_i-1}\mid n-1\). Or \(p_i\mid n\) donc \(p_i\nmid n-1\), ce qui impose \(e_i=1\). On a bien la condition cherchée.

En exercice, montrer

que si \(n\) est de Carmichael, \(n\) a au moins 3 facteurs premiers
que si \(n\) n’est ni premier ni de Carmichael, alors la proportion de \(a\) tq \(a^n=a\bmod n\) est inférieure à \(1/2\).

Soit \(n\) un entier impair, et supposons que pour \(k\) valeurs aléatoires \(a_1,\dots a_k\) on ait \(a_i^{n-1}=1\bmod n\). Alors

soit \(n\) est premier
soit \(n\) est de Carmichael, mais la probabilité est inférieure à \(2^{-300}\) pour \(n\) de 512 bits (à \(2^{-588}\) pour \(n\) de 1024 bits)
soit chaque \(a_i\) est dans \(H\), mais la probabilité est inférieure à \(2^{-k}\).

Ainsi, le test de Fermat est bien suffisant pour trouver de grands nombres premiers en pratique, et donne une garantie parfaitement satisfaisante.

Test de Miller-Rabin¶

Néanmoins on peut affiner à peu de frais le critère et faire disparaître les exceptions de type Carmichael, en utilisant

Lemme

Si \(n\) est premier et \(a^{2m}=1\), alors \(a^m\in\set{\pm1}\).

Miller

Soit \(n\) un nombre premier impair, on écrit \(n-1=2^rm\), \(2\nmid m\). Alors pour tout \(a\in(\Z/n\Z)^\ast\),

(1)¶\[\begin{cases} \text{ soit } a^m\equiv 1\bmod n \\ \text{ soit } \exists 0\leq i\leq k-1, a^{2^im}\equiv -1\bmod n \end{cases}\]

Démonstration

si \(n\) est premier, on a \(a^{n-1}=1\), puis par récurrence descendante pour \(i\geq 0\), si \(a^{2^{i+1}m}=1\), alors \(a^{2^im}=\pm 1\) (racines carrées de 1 dans un corps).

On a à présent une réciproque partielle

Rabin

Si \(n>9\) impair n’est pas premier, alors

\[\card{ \set{ a\in(\Z/n\Z)^\ast, a\text{ vérifie :eq:`miller`} } }\leq \frac{\varphi(n)}4.\]

Démonstration

Soit \(n\) non premier, et \(S\) l’ensemble cherché. On écrit \(n=\prod_{i=1}^l p_i^{e_i}\), et on pose \(q=2^im\), où \(i\) est le plus grand exposant tel qu’il existe \(a_0\), \(a_0^q=-1\bmod n\). Un tel \(i\) existe puisque \((-1)^m=-1\)

On écrit alors la suite de sous-groupes

\[\begin{array}{ccccccccc} G_4 &\subset & G_3 &\subset & G_2 &\subset &G_1 &\subset &G_0 \\ \set{ a^q=1[n] } &\subset &\set{ a^q=\pm1[n]} &\subset &\set{ a^q=\pm1[p_i^{e_i}]} &\subset &\set{ a^{n-1}=1[n] } &\subset &(\Z/n\Z)^\ast \end{array}\]

et l’on a

par définition de \(q\), \(S\subset G_3\) ;
\([G_3:G_4]=2\) car on a une partition \(G_3=G_4\cup a_0G_4\) ;
\([G_2:G_4]=2^l\) d’après le lemme chinois, car la même partition vaut sur chaque premier;
\([G_0:G_1]\geq 2\) dès que \(n\) n’est pas de Carmichael.

Ainsi, si \(l\geq 3\) c’est bon. Si \(l=2\) c’est bon car \(n\) ne peut être de Carmichael, enfin si \(l=1\) les éléments de \(G_1\) sont ceux d’ordre divisant \(p-1\) (car \(p\) est premier à \(p^e-1\)), donc \([G_0:G_1]=\frac{(p-1)p^{e-1}}{p-1}=p^{e-1}\) qui est supérieur à \(4\) si \(p\geq5\) ou \(e\geq 3\).

D’où un test de composition

Proposition

Si \(n\) est tel que (1) est vérifiée pour \(k\) valeurs \(a\) aléatoires, alors la probabilité que \(n\) soit non premier est inférieure à \(4^{-k}\).

Ce résultat est extrèmement pessimiste : pour un entier \(n\) non premier aléatoire, la proportion de mauvais témoins est en général beaucoup plus faible, voire nulle. Si l’on fait une étude en moyenne sur les entiers d’une certaine taille on se rend compte que même avec un seul test, la probabilité de ne pas avoir détecté un entier composé est extrèmement faible. Le NIST recommande de ne faire que \(4\) tests de Miller-Rabin pour des entiers entre 512 et 1024 bits, et même seulement 3 au-delà (la proportion de couples \((n,a)\) passant le test décroît rapidement).

miller(n,a=0) = {
  if(a,a=Mod(a,n),a=random(Mod(1,n)));
  k = valuation(n-1,2); m=(n-1) >> k;
  a = a^m; if( a == 1, return(1));
  for(j=0,k,
    if(a==-1, return(1));
    a = a^2
    );
  return(0);
}

Exemple

Avec \(n=1729\) (qui est de Carmichael), on a \(n-1=2^6\times 27\). Pour \(a=2\), \(\alpha=2^{m}=645\neq \pm1\), puis \(\alpha^2=1065\neq -1\), puis \(\alpha^4=1\neq -1\), ainsi que toutes les puissances ultérieures. Ainsi \(n\) n’est pas premier.

D’autre part, on obtient dans ce cas gratuitement une solution non triviale \(x=1065\) de \(x^2-1\), donc une factorisation de \(n\) en écrivant \(n=\pgcd(n,x-1)\pgcd(n,x+1)=133\times 13\) (on a d’un côté les premiers tels que \(x=1\bmod p\) et de l’autre ceux pour lesquels \(x=-1\bmod p\)).

Exemple

Déterminer si l’entier suivant est premier, et sinon le factoriser:

n = { 8185845834785787715500975919455614329511502614694099294667
      8560866952810920232221199291120876931129919023416710799705
      8608462266924211628867527238069614177979241512780491103207
      6679384558425720022941343121103938057297224254397874444742
      03520320009 }

Preuves de primalité¶

Méthode n-1¶

Proposition

Soit \(n\in\N\), alors on a équivalence entre

\(n\) est premier ;
\(\varphi(n)=n-1\) ;
\(\exists a\in(\Z/n\Z)^\ast\) d’ordre \(n-1\) ;

De plus, dans ce cas, il y a \(\phi(n-1)\) tels éléments \(a\).

Vérifier qu’un élément est d’ordre \(n-1\) est aisé si l’on connaît la factorisation de \(n-1\).

Théorème

Soit \(n\geq1\). On suppose qu’il existe \(a\in(\Z/n\Z)^\ast\) tel que

\[\begin{cases} a^{n-1}&\equiv 1\bmod n\\ a^{\frac{n-1}q}&\not\equiv 1\bmod n \text{ pour tout }q\mid n-1,\, q \text{ premier}. \end{cases}\]

Alors \(n\) est premier.

Un certificat de primalité est alors la donnée d’un tel élément \(a\) assorti d’une factorisation de \(n-1\), où l’on peut récursivement prouver la primalité de chaque facteur.

Un exemple :

[ 192383, 5, [ 2, 1, 43, 1, [ 2237, 2, [ 2, 2, 13, 1, 43, 1 ] ] ] ]

En posant \(n_1=192383\) et \(n2=2237\), ce certificat correspond aux affirmations

\[\begin{aligned} n_1-1 &= 2^1\times 43^1\times n_2 \\ 5^{n_1-1} &= 1 \bmod n_1 \\ 5^{\frac{n_1-1}2} &\neq 1 \bmod n_1 \\ 5^{\frac{n_1-1}{43}}&\neq 1 \bmod n_1 \\ 5^{\frac{n_1-1}{n_2}}&\neq 1 \bmod n_1 \end{aligned}\]

qui prouvent la primalité de \(n_1\), sous réserve de celle de \(n_2\), laquelle procède de

\[\begin{aligned} n_2-1 &= 2^2\times 13^1\times 43^1\\ 2^{n_2-1} &= 1 \bmod n_2 \\ 2^{\frac{n_2-1}2} &\neq 1 \bmod n_2 \\ 2^{\frac{n_2-1}{13}}&\neq 1 \bmod n_2 \\ 2^{\frac{n_2-1}{43}}&\neq 1 \bmod n_2. \end{aligned}\]

On peut affiner ce résultat en ne disposant que d’une factorisation partielle de \(n\).

Pocklington

Soit \(n\geq 1\). On suppose connaître une factorisation partielle de \(n-1\) de la forme \(n-1=FQ\) où

\(F=\prod q^{e_q}\) est complètement factorisé en produit de facteurs premiers ;
le cofacteur \(Q\) satisfait \(Q<\sqrt{n}\).

Alors \(n\) est premier si et seulement si il existe \(a\) tel que

\[\begin{cases} a^{n-1}\equiv 1\bmod n\\ \pgcd(a^{\frac{n-1}q}-1,n)=1 \text{ pour tout }q\mid F, q\text{ premier.} \end{cases}\]

Généralisation : l’algorithme ECPP¶

Le test \(n-1\) ne fonctionne qu’à condition de savoir factoriser \(n-1\). Ce qui est improbable pour de grands entiers.

Mais la même technique s’applique avec d’autres groupes que \(\Z/n\Z\) : les courbes elliptiques. On sait en effet qu’une courbe sur \(\F_p\) possède au plus \((\sqrt p+1)^2\) points.

Si on montre qu’une équation de courbe \(E\) modulo \(n\) possède un point \(P\) d’ordre \(m > (\sqrt[4]{n}+1)^2\), au sens où

\(m P = 0\) modulo \(n\)
les coordonnées \([x,y,z]\) de \(\tfrac mq P\) sont inversibles modulo \(n\)

alors il ne peut pas exister de premier \(p<\sqrt n\) qui divise \(n\), sans quoi la courbe réduite aurait un point d’ordre trop élevé.

Désormais, il existe beaucoup de courbes, donc une plus grande probabilité d’en trouver une dont l’ordre se factorise. Mieux, on a des techniques (multiplication complexe) pour partir d’un nombre de points possible fixé, et construire une courbe dont c’est le cardinal.

Composition, primalité¶

Résultats¶

Tests de composition¶

Test de Fermat¶

Test de Miller-Rabin¶

Preuves de primalité¶

Méthode n-1¶

Généralisation : l’algorithme ECPP¶

Table des matières

Table des matières