# Math Help - a25 mod n

1. ## a25 mod n

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).
a25 mod n = (((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n

2. 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).
a25 mod n = (((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
I for one cannot understand what you're asking. I'm sorry, but sometimes when you don't use LaTeX it's too busy and my eyes can't process it.

3. I am sorry.
I had never used LaTeX.
Is there any tutorial about it?

4. Originally Posted by albertkao
I am sorry.
I had never used LaTeX.
Is there any tutorial about it?
Of course. good luck

5. I have a question about the result of $a^{25} 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"

$a^8 mod\ n = ((a^2 mod\ n)^2 mod\ n)^2 mod\ n$
$a^{16} mod\ n = (((a^2 mod\ n)^2 mod\ n)^2 mod\ n)^2 mod\ n$

$a^{25} mod\ n = (a*a^{24}) mod\ n = (a*a^8*a^{16}) mod\ n$
$= (a*((a^2)^2)^2*(((a^2)^2)^2)^2) mod\ n = ((((a^2*a)^2)^2)^2*a) mod\ n$

With judicious storing of intermediate results, you only need six multiplications:
$(((((((a^2 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 the book said:
$a^{25} mod\ n = (((((((a^2 mod\ n)*a) mod\ n)^2 mod\ n)^2 mod\ n)^2 mod\ n)*a) mod\ n
$

I get the following result instead of that of the book:
$(a*b) mod\ n = ((a\ mod\ n)*(b\ mod\ n)) mod\ n$
$(x^2) mod\ n = ((x\ mod\ n)^2) mod\ n$
$a^{25} mod\ n = ((((((a^2)*a)^2)^2)^2)*a) mod\ n$
$= ((((((a^2)*a)^2)^2)^2 mod\ n) * (a\ mod\ n)) mod\ n$
$= (((((((a^2)*a)^2)^2) mod\ n)^2 mod\ n) * (a\ mod\ n)) mod\ n$
$= (((((((a^2)*a)^2)mod\ n)^2 mod\ n)^2 mod\ n) * (a\ mod\ n)) mod\ n$
$= ((((((((a^2)*a)mod\ n)^2)mod\ n)^2 mod\ n)^2 mod\ n)) * (a\ mod\ n)) mod\ n$
$= ((((((((((a^2)mod\ n)*(a\ mod\ n))mod\ n)^2)mod\ n)^2 mod\ n)^2 mod\ n))$
$\ * (a\ mod\ n)) mod\ n$
$= (((((((((((a\ mod\ n)^2)mod\ n)*(a\ mod\ n))mod\ n)^2)mod\ n)^2 mod\ n)^2 mod\ n))$
$\ * (a\ mod\ n)) mod\ n$