computing ae mod n

expo(a,e,n: integer):integer

{ae = (a2)e/2 or a•(a2)(e-1)/2}

 

IF e=0 THEN RETURN 1

IF e is even

THEN RETURN expo(a2 mod n,e/2,n)

ELSE

RETURN a•expo(a2 mod n,(e-1)/2,n) mod n

 

running time: O(|n|2|e|)