Originally Posted by

**albertkao** I have a question about the result of a25 mod n.

According to the book

Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C

Bruce Schneier, John Wiley & Sons

Chapter 11.3 Number Theory

Section "Modular Arithmetic"

a8 mod n = ((a2 mod n)2 mod n)2 mod n

a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n

a25 mod n = (a*a24) mod n = (a*a8*a16) mod n

= (a*((a2)2)2*(((a2)2)2)2) mod n = ((((a2*a)2)2)2*a) mod n

With judicious storing of intermediate results, you only need six multiplications:

(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n

I don't understand what are the missing intermediate results (steps).

Please explain why

a25 mod n = (((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n