Results 1 to 5 of 5

- Apr 17th 2010, 12:47 PM #1

- Joined
- Apr 2010
- Posts
- 3

## 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).

Please explain why

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

- Apr 17th 2010, 01:12 PM #2

- Apr 17th 2010, 01:18 PM #3

- Joined
- Apr 2010
- Posts
- 3

- Apr 17th 2010, 01:20 PM #4

- Apr 17th 2010, 01:46 PM #5

- Joined
- Apr 2010
- Posts
- 3

I have a question about the result of .

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"

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

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

Please explain why the book said:

I get the following result instead of that of the book: