Arithmétique 2

Nombres de Carmichael

On appelle nombres de Carmichael les entiers \(n\) non premiers vérifiant l’égalité de Fermat

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

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

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

3. 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;
   

Sécurité de RSA

On définit un module RSA \(n=pq\), avec

\[p = \frac{15^{73}-1}{14}, \; q = \frac{11^{73}-1}{10}\]

1. Calculer les racines carrées de \(1\) dans \(\Z/n\Z\). Combien y en a-t-il ?
2. 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\).
3. 410041 est un nombre de Carmichael. Le factoriser en déterminant une telle valeur de \(a\).
4. 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\).
5. En déduire un algorithme pour factoriser \(n\).
6. Faire le test avec votre voisin : construire et échanger des clefs RSA, et les casser quand on connaît \(e\) et \(d\).

Test de primalité 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}\]

1. É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);
   }:;
   

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

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

2. É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));
   

Racines modulo p

Le cas impair

1. On pose \(p = \frac{6^{127}-1}{5}\). Déterminer un carré (non trivial) \(a\bmod p\).
2. Vérifier que \(a^{\frac{p+1}4}\) est une racine carrée de \(a\).
3. Quelles sont les racines carrées de \(6\) modulo \(n=pq\), où

\[p = \frac{6^{127}-1}{5}, \; q = \frac{6^{271}-1}{5}\]

On considère un cas plus compliqué

\[p = \frac{15^{73}-1}{14}, \; q = \frac{11^{73}-1}{10}\]

La méthode précédente permet-elle de calculer les racines carrées de \(6\) modulo \(n=pq\) ?

Algorithme de Cipolla

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

\[\begin{split}x^p = x &\Leftrightarrow a \in \F_p^2 \Leftrightarrow x\in\F_p \\ x^p = -x &\Leftrightarrow a \in \F_p\setminus \F_p^2 \Leftrightarrow \F_{p^2} = \F_p[x]\end{split}\]

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

\[(u+v)^{p+1} = (u+v)(u^p+v^p) = (u+v) (u-v) = u^2 - v^2\]

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

\[x = (u+v)^{\frac{p+1}2}\]

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 :

• déterminer \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\)
• construire \(\F_{p^2}\) comme \(\F_p[v]/(v^2-(u^2-a))\)
• calculer \(x=(u+v)^{\frac{p+1}2}\) par exponentiation rapide
• le résultat \(x\) est dans \(\F_p\) et est une racine carrée de \(a\).

1. Programmer cet algorithme et calculer les racines de \(6\).