Multiples, puissance dans Z/nZ et test de primalité de Miller-Rabin

mardi 14 février 2012
par  Christian Mercat

Nous visualisons les tables de multiplication et d’exponentiation dans \mathbb{Z}/n\mathbb{Z} à l’aide de Géogébra.

On choisit un entier n (par un curseur entier), et on visualise \mathbb{Z}/n\mathbb{Z} comme une séquence de points sur le cercle unité :

z=exp(2*i*pi/n)
C=Cercle[(0,0),1]
O=(1,0)
zk=Séquence[z^k,k,2,n-1]

On choisit une classe m (curseur entier) et on visualise ses multiples comme une étoile, un polygone non convexe :

zm = z^m
zkm=Séquence[z^(k*m),k,1,n]
Séquence[Segment[Elément[zkm,k],Elément[zkm,k+1]],k,1,n-1]

Si ce polygone passe par 1, m et n sont premiers entre eux, sinon, m est un diviseur de zéro. Quand n est premier, toutes les classes non nulles sont inversibles. On visualise la table de multiplication :

Tableau[Séquence[Séquence[Reste[j*k, n], k, 0, n - 1], j, 0, n - 1]]

On regarde ensuite les puissances de m :

zmk=Séquence[z^(Reste[m^k,n]),k,1,n]
Séquence[Segment[Elément[zmk,k],Elément[zmk,k+1]],k,1,n-1]

On visualise la table des puissances :

Tableau[Séquence[Séquence[Reste[j^k, n], k, 0, n - 1], j, 1, n - 1]]

L’ordre de l’élément divise l’ordre du groupe (n-1) et on a donc m^{n-1}\equiv 1[n] quand n est premier, c’est le petit théorème de Fermat.

On ne peut malheureusement pas aller très loin avec cette méthode naïve, on aboutit à des "non défini" assez rapidement, 12^14 par exemple est un entier à plus de 16 chiffres et ne peut pas être utilisé pour ce genre d’arithmétique. Il faut alors recourir au tableur :

Après avoir initialisé la première ligne et la première colonne par des entiers croissants, on colle comme expression :

B2=Reste[A2 $A2, n]

qu’on étend à tout le tableau. Ainsi, dans la ligne m, la kième case est le produit de la première colonne (m) par la case précédente à gauche (m^{k-1}), modulo n, ce qui garantit le non dépassement. On observe que, pour n premier, la colonne n-1 est bien remplie de 1, sauf aux lignes d’indices multiples de n.

La figure se trouve sur i2geo.

Test de primalité de Miller-Rabin

Remarquez bien, dans la construction précédente, dans la table des puissances, la dernière colonne, qui n’est composée que de 1 si n est premier et qui est beaucoup plus complexe quand n est composé. Cette condition nécessaire pour que n soit premier constitue un test de primalité de n. Beaucoup moins coûteux est le test de primalité de Miller-Rabin : pour n un grand nombre premier, n-1 est pair et s’écrit n-1=2^r\times d avec d impair. Pour que m^{n-1}\equiv 1[n], il faut nécessairement que soit m^d\equiv 1[n] soit qu’il existe un entier \ell<r tel que m^{d\times 2^\ell}\equiv -1[n], ce qui fait beaucoup moins de cas à tester et des puissances simples à calculer par carrés successifs. Et il suffit en fait de tester peu de nombres m différents pour avoir une probabilité très faible que n ne soit pas premier si tous ces entiers passent le test. Dans le cas contraire, on tient un témoin de Miller-Rabin qui prouve que n n’est pas premier. Le test de Miller-Rabin est un test probabiliste de primalité. On peut vérifier numériquement que pour n < 9 080 191 il suffit de tester m=31 et m=73. Si n < 4 759 123 141, il suffit de tester m=2, m=7 et m=61. Si n < 341 550 071 728 321, il suffit de tester m = 2, 3, 5, 7, 11, 13, et 17. Le test devient alors déterministe pour des nombres n pas trop énormes.

Il est très simple d’implémenter ce test avec xcas :

MR(n):={// Test de primalité de Miller-Rabin
local (d:=n-1), (s:=0), a, r, j;
while((d mod 2)==0){ s:=s+1; d:= d/2; }
// a = 2^s*d, d impair
for( j:=2; j<11; j++) { // 2(log n)^2
a := j; // hasard n;
a := powmod(a, d, n); r:=0;
if(a<>1) {
while((((a+1)mod n)!=0) and (r<s)){ // a = -1 mod n?
a:=powmod(a,2,n); r:=r+1; // a = 2^r*d, r<s
}
}
if (((a mod n)!=0) and (r==s)) return faux; //N'est pas premier
}; // Si a réussi 10 fois
return vrai; // Probablement premier
}
:;

Et on peut constater que c’est très rapide et conforme à un test non probabiliste de primalité :

for j from 10001 to 20000 by 2 do if(MR(j)!=isprime(j)) afficher(i+MR(j)+isprime(j)); end_do

Documents joints

Test de primalité de Miller-Rabin
Test de primalité de Miller-Rabin
Fichier xcas

Commentaires

Navigation

Brèves

12 juillet 2021 - MOOC Entrée dans l’enseignement supérieur

L’école polytechnique propose une série de cours massifs en ligne à prendre comme un "cahier de (...)

18 octobre 2015 - Questionnaires de la CII Université

L’objectif est de collecter de nouvelles réponses pour mieux mesurer l’impact de la réforme du (...)

27 janvier 2010 - Travailler par compétences et avec le socle commun

Conférence le 10 février au CRDP de Lyon de 9 h à 12 h, avec Jean Michel Zarkhartchouk

13 novembre 2008 - Probabilités en 3e

Texte issu d’une formation aux probabilités pour les professeurs de troisième faite par Y. Ducel (...)

Sur le Web