HP 39g-Grafenberechner - Handbuch (Seite 162)

Exakte Berechnungen und Mathematik mit HP40G
162 Arithmetische Programme
Man benutzt nur eine lokale Variable PUI, aber man ändert P so, daß man in
jedem Zyklus der Iteration folgendes hat:
Ergebnis = PUI * A
P
(mod N)
lokal PUI
1 -
> PUI
solange P
>0 durchführen
A*PUI mod N -
> PUI
P-1 -
>P
/solange/
Ergebnis PUI
/Funktion/
Dritter Algorithmus
Dieses Programm kann einfach modifizieren, wenn man beachtet daß:
A²
*P
= (A*A)
p
.
Wenn P gerade ist, entsteht das Verhältnis:
PUI * A
P
= PUI * A *A
P-1
(mod N).
Man bekommt also einen schnellen Algorithmus von A
P
(mod N).
Funktion puismod (A, P, N)
lokal (lokal) PUI
1-
>PUI
solange P
>0 durchführen
wenn P mod 2=0 dann
P/2-
>P
A*A mod N-
>A
sonst
A*PUI mod N -
>PUI
P-1-
>P
/wenn/