Results 1 to 2 of 2

Math Help - modular exponentiation example

  1. #1
    Member
    Joined
    Sep 2011
    Posts
    106
    Thanks
    1

    modular exponentiation example/explaination

    I'm trying to follow along this example of modular expression. I have a few questions.

    1. Where does the 71 come from
    2. What does this mean exactly? x = 16243 ≡ 71 mod 622

    ************************************************** ************

    16243^{77} mod 622.
    We first compute the binary expansion of 77 using repeated division by 2:

    2 | 77
    2 | 38 r 1
    2 | 19 r 0
    2 | 9 r 1
    2 | 4 r 1
    2 | 2 r 0
    2 | 1 r 0
    0 r 1

    so that the decimal number 77 is written in binary as 1001101 (notice that we reverse the
    list of remainders). So

    77 = 1◊2^6 + 0◊2^5 + 0◊2^4 + 1◊2^3 +1◊2^2 + 0◊2^1 + 1◊2^0

    or simply
    77 = 64+8 + 4 + 1.

    Now start with x = 16243 ≡ 71 mod 622 and square six times modulo n (six being one
    less than seven, the bit-length of 1001101):

    x ≡ 71 mod 622
    x^2 ≡ 65
    x^{4}≡ 493
    x^{8} ≡ 469
    x^{16} ≡ 395
    x^{32} ≡ 525
    x^{64} ≡ 79

    Now refer to the 1ís in the binary expansion of 77, and multiply together the corresponding powers of x modulo n, thus:
    x^{64+8} ≡ 79◊469 ≡ 353
    x^{64+8+4} ≡ 353◊493 ≡ 491
    x^{77} = x^{64+8+4+1} ≡ 491◊71 ≡ 29 mod 622
    Last edited by delgeezee; March 2nd 2012 at 09:45 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Re: modular exponentiation example

    Hello,

    Your two questions are one and the same. The expression a \equiv b \pmod{n} (read: "a is congruent to b mod n") by definition means that a-b is a multiple of n or equivalently n divides a-b, written respectively as \exists c: a-b=cn and n \mid a-b. This may be hard to remember; it's probably easier to think of it this way: a and b have the same (non-negative) remainder when divided by n. When we specify non-negative remainder, we want the integer in [0,n), also called the common residue. Using the common residue can keep the numbers smaller, making our calculations easier.

    You can verify that 71 is the remainder when 16243 is divided by 622.

    Formally, we can write

    a \equiv b \implies a^c \equiv b^c \pmod{n}

    No matter whether we start with 16243, or 71, or 71+622, or 71+2*622, we will get the same result after applying the steps for modular exponentiation, so we might as well choose the smallest.

    Also, you can use \cdot in LaTeX for multiplication, it looks like 1 \cdot 2^6.

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Exponentiation Calculator
    Posted in the Math Software Forum
    Replies: 6
    Last Post: April 2nd 2011, 08:25 AM
  2. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 13th 2010, 02:54 PM
  3. Modular Exponentiation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2010, 06:31 PM
  4. Modular exponentiation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 9th 2009, 12:08 AM
  5. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 27th 2008, 05:31 PM

Search Tags


/mathhelpforum @mathhelpforum