[CST-2] advanced algorithms 1996/9/6 (fwd)

[Alan Lawrence]

Of course you can do that - 12^64 mod 65 = (X) mod 65, where 
X=12^64=12^(4*16)=(12^4)^16... etc. - you can do the mod 65 at any point 
or points you like, so the usual identities a^(b*c) = (a^b)^c apply etc.

The other way is

a^b mod m = a^(b mod phi(m)) mod m

phi(65)=phi(5)*phi(13)=4*12 = 48 => a^64 mod 65 = a^16 mod 65. Doesn't 
help significantly in this case, but might possibly be useful under, I 
don't know, some strange set of circumstances :-)

--Alan