快速指数运算法一平方再乘法 Algorithm fastexp a, z, n) begin "return x=az mod n a1:=a;z1:=z;X Whez1≠0d0“X(a121modn)=a2modn” egl While z, mod 2=o do begin square a, while z, is even z,'=z div 2 ar: =(a*aj)mod n end x:=(X*a)mod n" multiply' end astexp: =X end 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 24/81mfy@ustc.edu.cn 现代密码学理论与实践 24/81 Algorithm fastexp(a, z, n) begin “return x=a z mod n” a1 := a; z1 :=z; x:=1 while z1≠0 do “x(a1 z1 mod n)= a z mod n” begin while z1 mod 2 = 0 do begin “square a1 while z1 is even” z1 :=z1 div 2 a1 :=(a1*a1 ) mod n end; z1 :=z1-1 x:= (x*a1 ) mod n “multiply” end; fastexp:=x end