HP 39g Graphing Calculator Manual do Utilizador descarregar pdf (Página 139)

M´ethode probabiliste de Mr Rabin 139

I+6 ->I:

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

ona:

N−1

=1(modN)

Si N n’est pas premier, les entiers K v´eriﬁant :

N−1

=1(modN)

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´eriﬁant K

N−1

=1(modN) 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 :

N−1

(mod N)

Si K

N−1

=1(modN ) 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(modN) pour 20 tirages de K on peut

conclure que N est premier avec une probabilit´e d’erreur tr`es faible

inf´erieure `a0.25

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 :

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

mod N

Fonction estprem(N)

local K, I, P

1->I

1 2 ... 134 135 136 137 138 139 140 141 142 143 144 ... 154 155

Comentários a estes Manuais

Sem comentários

HP 39g Graphing Calculator Manual do Utilizador Página 139

Comentários a estes Manuais

Manuais e produtos relacionados com não HP 39g Graphing Calculator