Home |
Logithèque |
TI82
Test probabiliste de primalité de Rabin-Miller
Code
ClrHome:Disp "TEST DE RABIN-","MILLER"
Prompt N
N-1->Q:0->R
While 0=fPart(Q/2):R+1->R:Q/2->Q
End
Disp " R"," N-1=2 .Q"
Disp R,Q:Output(6,1,"R="):Output(7,1,"Q=")
{2,3,5,7,11,13,17,19,23,29,31,37,41,47,53,59,61,67,71}->L1
Lbl B
Disp "ENTREZ UN NOMBRE","PREMIER (1=RAND":Input "0=Fin) A=",A
If 0=A:Then
Disp N:Output(7,1,"n=")
Stop:End
If 1=A:Then
L1(RandInt(1,19))->A
Disp A:Output (7,1,"A="):End
Q->P:R->S
Disp "CALCUL DE"," Q"," A (MOD N)"
1->M:Repeat 0=P
P/2->P
If 0/=fPart(P)
round(N*fPart(A*M/N),0)->N
round(N*fPart(A^2/N),0)->A
iPart(P)->P
End
Disp M:Output(7,1,"=")
If 1=M:Goto N
While 0<S
If 1=M:Goto N
If M+1=N:Goto P
round(N*fPart(M^2/N),0)->M
S-1->S
If 1/=M:Goto N
Lbl P
Disp "PREMIER?"
Goto B
Lbl N
Disp "COMPOSE"
Les signes "/=" à la 21ème et 33ème lignes représentent l'opérateur "différent de", les signes "^2" en lignes 23 et 31 représentent l'élévation au carré.
Mode d'emploi
Exécuter le programme. Le nombre à tester est demandé. Le programme affiche la décomposition sous la forme (2^R)*Q, puis demande un nombre premier A pour l'épreuve du test. Taper 0 pour arrêter le programme, 1 pour qu'il choisisse un nombre premier au hasard entre 2 et 71 (affiché), ou tapez le nombre directement.
Le programme affiche A^Q modulo N et déclare s'il est composé (le programme s'arrête), ou s'il peut être premier.
Dans ce second cas on revient au choix de la base pour le test. Il est alors possible de taper 0 pour terminer.
Exemple :
Saisie | Réponse |
prgmTESTPRIM |
TEST DE RABIN- MILLER N= |
25461 |
R N-1=2 .Q R= 2 Q= 6365 ENTREZ UN NOMBRE PREMIER (1=RAND, 0=FIN) A= |
1 |
A= 71 CALCUL DE Q A (MOD N) = 21932 COMPOSE Done |
Mathématiques à l'oeuvre
Il s'agit en fait du petit théorème de Fermat un peu dopé : si A^(P-1) n'est pas congru à 1 modulo P, alors P n'est pas premier.
Mais si (P-1) est divisible par 2, alors A^( (P-1)/2) doit aussi être une racine carrée de 1 modulo P, soit +1 ou -1. Si ce n'est pas le cas, P est composé.
En itérant le raisonnement, on obtient le test de Rabin-Miller...
Il existe quelques subtilités d'implémentation qui sont très bien décrites dans le superbe livre "Merveilleux Nombres Premiers" de ???
Fonctionnement du programme
Voici l'utilisation des variables :
A | Nombre premier base du test |
M | A^Q mod N |
N | Nombre à tester |
P | Temporaire pour Q |
Q | Tel que N-1=(2^R)*Q |
R | Idem |
|
|
|
|
Le programme est linéaire sauf le branchement permettant de revenir tester le même nombre avec une autre base. Les labels P et N sont pour "premier" et "non-premier".
On peut énormément simplifier et alléger le programme en supprimant la bibliothèque de bases et les messages informatifs détaillant les calculs.