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

136 Chapitre 7 – Programmes d’arithm´etique
resultat PUI
ffonction
On peut remarquer que si P est impair, P-1 est pair.
On peut donc ´ecrire :
fonction puismod (A, P, N)
local PUI
1->PUI
tant que
P>0 faire
si P mod 2 =1 alors
A*PUI mod N ->PUI
P-1->P
fsi
P/2->P
A*A mod N->A
ftantque
resultat PUI
ffonction
7.4.2 Traduction HP40G
Le calcul de A p mod N est utilis´e dans le programme de la m´ethode
probabiliste de Mr Rabin. On se reportera donc ` a ce sous-programme
pour la traduction (cf 7.6).
7.5 La fonction “estpremier”
7.5.1 Traduction Algorithmique
- Premier algorithme
On va ´ecrire un fonction bool´ eenne de param`etre N, qui sera ´egale
` a VRAI quand N est premier et ` a FAUX sinon.
Pour cela, on cherche si N poss´ede un diviseur = 1 et ` a E(
√
N )
(partie enti`ere de racine de N).
On traite le cas N=1 ` a part!
On utilise une variable bool´ eenne PREM, qui est au d´epart ` a
VRAI, et qui passe ` a FAUX d`es que l’on rencontre un diviseur de N.
Fonction estpremier(N)
local PREM, I, J
E(
√
N)
− > J