27 views

Skip to first unread message

Apr 23, 2010, 10:26:38 AM4/23/10

to

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]

Apr 24, 2010, 2:43:05 AM4/24/10

to

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu