Brett vor dem Kopf

16/08/2013 - 17:26 von mock | Report spam
Ich habe mir in PARI-gp einen kleinen Siebenzeiler für die modulare Potenzierung geschrieben. Das erscheint hier, weil ich hier am meisten gp-Benutzer erwarte.

Mein Problem ist, dass er nur für ungerade Exponenten richtige Ergebnisse liefert. Wo ist der Fehler?

-

modexp(zhl,xpnt,mdl)= /* zhl: Grundzahl, xpnt: Exponent, mdl: Modul */
{
res=1;
x=binary(xpnt); /* Binàrdarstellung des Exponenten als Vektor */
forstep(i=matsize(x)[2],1,-1,res=res*res%mdl;if(x[i],res=res*zhl%mdl));
return(res)
}
 

Lesen sie die antworten

#1 Marc Olschok
17/08/2013 - 01:46 | Warnen spam
mock wrote:
Ich habe mir in PARI-gp einen kleinen Siebenzeiler für die modulare
Potenzierung geschrieben. Das erscheint hier, weil ich hier am
meisten gp-Benutzer erwarte.

Mein Problem ist, dass er nur für ungerade Exponenten richtige
Ergebnisse liefert. Wo ist der Fehler?

-

modexp(zhl,xpnt,mdl)= /* zhl: Grundzahl, xpnt: Exponent, mdl: Modul */
{
res=1;


___^^^^^___(*)
x=binary(xpnt); /* Binàrdarstellung des Exponenten als Vektor */
forstep(i=matsize(x)[2],1,-1,res=res*res%mdl;if(x[i],res=res*zhl%mdl));


________________________________^^^^^^^^^^^^^^^__(**)
return(res)
}



In der Schleife bleibt res=1 solange bestehen, bis in der Binàrdarstellung
von zhl die erste 1 (von rechts) auftaucht. Bis es soweit ist, bleibt das
quadrieren in (**) wirkungslos.

Marc

Ähnliche fragen