a25 mod n

[albert kao]

Rewrite my previous question with latex.
I have a question about the result of [latex]a^{25} mod\ n[/latex].
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"

[latex]a^8 mod\ n = ((a^2 mod\ n)^2 mod\ n)^2 mod\ n[/latex]
[latex]a^{16} mod\ n = (((a^2 mod\ n)^2 mod\ n)^2 mod\ n)^2 mod\ n[/
latex]

[latex]a^{25} mod\ n = (a*a^{24}) mod\ n = (a*a^8*a^{16}) mod\ n [/
latex]
[latex]= (a*((a^2)^2)^2*(((a^2)^2)^2)^2) mod\ n =
((((a^2*a)^2)^2)^2*a) mod\ n [/latex]

With judicious storing of intermediate results, you only need six
multiplications:
[latex](((((((a^2 mod\ n)*a) mod\ n)^2 mod\ n)^2 mod\ n)^2 mod\ n)*a)
mod\ n [/latex]

I don't understand what are the missing intermediate results (steps).
Please explain why
[latex]a^{25} mod\ n = (((((((a^2 mod\ n)*a) mod\ n)^2 mod\ n)^2 mod\
n)^2 mod\ n)*a) mod\ n
[/latex]

[Peter Pearson]

On 23 Apr 2010 14:26:38 GMT, albert kao <alber...@gmail.com> wrote:
[snip]

> Please explain why
> [latex]a^{25} mod\ n = (((((((a^2 mod\ n)*a) mod\ n)^2 mod\ n)^2 mod\
> n)^2 mod\ n)*a) mod\ n
> [/latex]

First, note that a**25 = (((((a**2)*a)**2)**2)**2)*a, so
a**25 mod n = (((((a**2)*a)**2)**2)**2)*a mod n.
Then, note that if any of the intermediate results on the right is
changed by adding or subtracting a multiple of n, the equality
still holds, because the final "mod n" operation will remove
any added (or subtracted) multiples of n. Finally, note that
applying a "mod n" operation to an intermediate result only
adds or subtracts a multiple of n.

--
To email me, substitute nowhere->spamcop, invalid->net.