Results 1 to 6 of 6

Math Help - Square and Multiply

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    7

    Square and Multiply

    I was wondering if somebody could help me with a problem I am having. I am trying to compute:

    9983^2052765 mod 36581 and 13461^2052765 mod 36581

    I am pretty sure it can be accomplished with the square and multiply method but I'm not to sure as to how to accomplish this. Could anyone point me in the right direction or get me started off?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     \varphi(36581) = 36192 and  2052765 = 56\cdot36192+26013 .

    Thus  \displaystyle 9983^{2052765} \equiv 9983^{26013} \bmod{36581} . Now express  26013 in binary..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    7
    Thanks for your response. To be honest I have no idea what you did. What do you mean by express in binary, as in 2 to a power?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
     \varphi(36581) = 36192 and  2052765 = 56\cdot36192+26013 .

    Thus  \displaystyle 9983^{2052765} \equiv 9983^{26013} \bmod{36581} . Now express  26013 in binary..
     26013 = 110010110011101_2 i.e.  26013 = 2^{14}+2^{13}+2^{10}+2^8+2^7+2^4+2^3+2^2+2^0

    Let  a = 9983 , now  \displaystyle a^{26013} = a^{2^{14}}\cdot a^{2^{13}}\cdot a^{2^{10}}\cdot a^{2^8}\cdot a^{2^7}\cdot a^{2^4}\cdot a^{2^3}\cdot a^{2^2}\cdot a^{2^0} .

    If we compute  \displaystyle a^{2^n} starting from  0 to  14 , it will be less messy to compute the solution.

     9983^1 \equiv 9983 \bmod{36581}

     9983^2 \equiv 13645 \bmod{36581}

     9983^4 \equiv 13645^2 \equiv 25316 \bmod{36581}

     9983^8 \equiv 25316^2 \equiv 736 \bmod{36581}

     9983^{16} \equiv 736^2 \equiv 33454 \bmod{36581}

     \vdots

    This seems rather tedious. If you are familiar with the notion of multiplicative order, this can be a bit easier. Are you?

    If so, use the fact that  9983^{1508} \equiv 1 \bmod{36581} and  2052765 = 1361 \cdot 1508+377 . Then you'll only have to do the above for  377 instead of  26013!
    Last edited by chiph588@; December 12th 2010 at 11:14 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    7
    Okay, so this is what I did.

    377 = 101111001

    377^256 % 36581 = 25398
    377^64 % 36581 = 13118
    377^32 % 36581 = 20272
    377^16 % 36581 = 24932
    377^8 % 36581 = 26097
    377^1 % 36581 = 377

    multiplied those all together and got 1656734045363396234936064.
    Now do i mod that number by 36581 for the answer?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tr6699 View Post
    Okay, so this is what I did.

    377 = 101111001

    377^256 % 36581 = 25398
    377^64 % 36581 = 13118
    377^32 % 36581 = 20272
    377^16 % 36581 = 24932
    377^8 % 36581 = 26097
    377^1 % 36581 = 377

    multiplied those all together and got 1656734045363396234936064.
    Now do i mod that number by 36581 for the answer?
    You need to consider  \displaystyle 9983^{2^n} , not  \displaystyle 377^{2^n}

    Otherwise, yes you've done everything correctly.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Do we just multiply everything?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 12th 2010, 11:30 AM
  2. Multiply
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 26th 2009, 04:20 AM
  3. How would I multiply this out?
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: September 23rd 2009, 08:50 PM
  4. Multiply
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 27th 2009, 07:01 PM
  5. Multiply
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 15th 2007, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum