Results 1 to 5 of 5

Math Help - a25 mod n

  1. #1
    Newbie
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by albertkao View Post
    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
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    3
    I am sorry.
    I had never used LaTeX.
    Is there any tutorial about it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by albertkao View Post
    I am sorry.
    I had never used LaTeX.
    Is there any tutorial about it?
    Of course. good luck
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    3
    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 <br />

    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
    Last edited by albertkao; April 18th 2010 at 10:58 AM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum