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

S

Temporaire pour R

L1

Bibliothèque de nombre premiers

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.