Multiples, puissance dans Z/nZ et test de primalité de Miller-Rabin
par
Nous visualisons les tables de multiplication et d’exponentiation dans à l’aide de Géogébra.
On choisit un entier n (par un curseur entier), et on visualise 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 quand 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, 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 (), 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 est premier et qui est beaucoup plus complexe quand est composé. Cette condition nécessaire pour que soit premier constitue un test de primalité de . Beaucoup moins coûteux est le test de primalité de Miller-Rabin : pour un grand nombre premier, est pair et s’écrit avec impair. Pour que , il faut nécessairement que soit soit qu’il existe un entier tel que , 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 différents pour avoir une probabilité très faible que 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’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
Commentaires