Modulo hatványozás

A számítás a következő módon megy végbe:
a^b kiszámítható lenne úgy, hogy a-t megszorozzuk a-val b-szer. Ha azonban b nagy, a számítás ilyen módon millió évekig tartana, még a világ leggyorsabb mikroprocesszorával is.

Ennél gyorsabb némileg, ha kiszámítjuk az a, a², a⁴, ..., a²ⁿ, ... értékeket. Legyen b bináris megjelenítése b₀, b₁, ... , b_n, ... és b_n a b n-edik bitje. a^b értéke a következő egyenlettel számítható ki:

ahol f[x] egy olyan függvény, amely minden egész számra identitás, kivéve a nullát, ahol f[0]=1. Más szavakkal a szorzatba csak azokat a tagokat vesszük be, ahol b_i nem nulla bit. A képlet végén levő három pont végtelen szorzást jelentene, de egy idő után b-nek csupa nulla bitje van, hiszen b véges.

Ezzel az eljárással a számítás időigénye arányos a b bitjeinek a számával és nem b nagyságával.

Mivel minket nem érdekel a^b értéke, csak a^b mod c ezért minden egyes szorzás után az eredményt helyettesíthetjük a c-vel adott osztási maradékával. Ezzel annyi memóriahelyet és időt tudunk spórolni, hogy a számítás elvégezhető.

Number Power(Number a, Number b, Number c){
 register Number ActPower,Ac,result,re;
 register int bLength,bit,i;
 register u8 ActB;

 if( (bLength = Length(b)) == 0 )
 return CreateNumber(1L);
 ActPower = DupNumber(a);

 if( !Length(ActPower) )return ActPower;
 result = CreateNumber(1L);
/* b miden egyes digitjén */
 for( i = 0 ; i digit[i];
/* a digit minden bitjére */
 for( bit = 0 ; bit <8 ; bit++ ){ if( actb&1 ){/* ha az aktuális bit egy */ re="<A" href="mult.htm">Multiply(result,ActPower);
 DisposeNumber(result);
 if( !re ){
 return (Number)0;
 }
 result = Remainder(re,c);
 DisposeNumber(re);
 if( !result ){
 return (Number)0;
 }
 }
 ActB >>= 1;
 Ac = Square(ActPower);
 if( Ac->n == -1 ){
 Ac->n = Ac->n;
 }
 DisposeNumber(ActPower);
 if( !Ac ){
 return (Number)0;
 }
 ActPower = Remainder(Ac,c);
 DisposeNumber(Ac);
 if( !ActPower ){
 return (Number)0;
 }
 }
 }
 DisposeNumber(ActPower);
 return result;
 }

Square

#define Square(x) Multiply(x,x)