Discussion:
a25 mod n
albert kao
2010-04-17 19:22:27 UTC
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"

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
Brian M. Scott
2010-04-17 20:32:55 UTC
On Sat, 17 Apr 2010 12:22:27 -0700 (PDT), albert kao
Post by albert kao
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"
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
First let's rewrite that using the usual ASCII notation for
exponentiation:

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
Post by albert kao
With judicious storing of intermediate results, you only need six
(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
(((((((a^2 mod n) * a) mod n)^2 mod n)^2 mod n)^2 mod n)
* a) mod n
Post by albert kao
I don't understand what are the missing intermediate results (steps).
((((a^2 * a)^2)^2)^2 * a) mod n =

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

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

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

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

(((((((a^2 mod n) * a) mod n)^2 mod n)^2 mod n)^2 mod n)
* a) mod n

What's being used repeatedly is the fact that

(bc) mod n = [(b mod n) * c] mod n = (b mod n)(c mod n).

[...]

Brian
albert kao
2010-04-17 21:10:13 UTC
Post by albert kao
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"
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
(((((((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
Rewrite using 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).
[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]
Chip Eastham
2010-04-17 22:14:49 UTC
Post by albert kao
Post by albert kao
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"
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
(((((((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 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
[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).