computing ae mod n

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

 

x := 1

WHILE e>0 DO

. . . IF e is odd THEN x := ax mod n

. . . a := a2 mod n

. . . e := e div 2

RETURN x

 

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