a25 mod n
in [Math]
|
Prev: spectral radius and Frobenius norm
Next: I am Isaac Newton, do I need to always wear a chastity belt all my life?
From: albert kao on 17 Apr 2010 15:22 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). Please explain why a25 mod n = (((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
From: albert kao on 17 Apr 2010 17:10 On Apr 17, 3:22 pm, albert kao <albertk...(a)gmail.com> wrote: > 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). > Please explain why > 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). 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]
From: Chip Eastham on 17 Apr 2010 18:14
On Apr 17, 5:10 pm, albert kao <albertk...(a)gmail.com> wrote: > On Apr 17, 3:22 pm, albert kao <albertk...(a)gmail.com> wrote: > > > > > 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). > > Please explain why > > 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). > 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] See my reply to your duplicate post in alt.math.recreational. --c |