HP Calculatrice graphique HP 39g - Manuel (Page 139)

M´ethode probabiliste de Mr Rabin 139
I+6 ->I:
END:
END:
CLEAR:
DISP 5;P:
FREEZE:
7.6 M´ ethode probabiliste de Mr Rabin
Si N est premier alors tous les nombres K strictement inf´erieurs
` a N sont premiers avec N , donc d’apr` es le petit th´eor`eme de Fermat
on a :
K N −1
= 1 (mod N )
Si N n’est pas premier, les entiers K v´erifiant :
K
N −1
= 1 (mod N )
sont tr`es peu nombreux.
Plus pr´ecisement on peut montrer que si N > 4, la probabilit´ e
d’obtenir un tel nombre K est inf´erieure ` a 0.25.
Un nombre N v´erifiant K N −1
= 1 (mod N ) pour 20 tirages de K
est un nombre pseudo-premier. La m´ethode probabiliste de Rabin
consiste `
a tirer au hasard un nombre K (1 < K < N ) et ` a calculer :
K N −1
(mod N )
Si K N −1
= 1 (mod N ) on refait un autre tirage et si K N −1
=
1 (mod N ) on est sˆ ur que N n’est pas premier.
Si on obtient K N −1
= 1 (mod N ) pour 20 tirages de K on peut
conclure que N est premier avec une probabilit´e d’erreur tr`es faible
inf´erieure `
a 0.25 20 soit de l’ordre de 10
−12
.
Bien sˆ ur cette m´ethode est employ´ee pour savoir si de grands
nombres sont pseudo-premiers.
7.6.1 Traduction Algorithmique
On suppose que :
Hasard(N) donne un nombre entier au hasard entre 0 et N
− 1.
Le calcul de :
K
N −1
mod N
se fait grˆ ace ` a l’algorithme de la puissance rapide (cf page 134).
On notera :
puismod(K, P, N) la fonction qui calcule K
P mod N
Fonction estprem(N)
local K, I, P
1->I