Jump to content
  • Advertisement
Sign in to follow this  
JinJo

modulo of large numbers (e.g. 13^183 mod 11)

This topic is 4492 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This isn't a homwork question btw, just going through an old maths course to catch up a bit. Anyway, I know the anser is 8 and done it using simple mod arithmetic. Here's my working: 13^183 mod 11 = 13^(2^7) mod 11 * 13^55 mod 11 = 3 * 10 mod 11 = 8 however even though it was broken down a bit those are still huge numbers and i done them in a calculator. I thought of using Fermat's little theorem but the 183 isn't a prime number and from what i understand it needs to be to use that rule? Any pointers?

Share this post


Link to post
Share on other sites
Advertisement
I know less than you do, but isn't Fermat's little theorem (what a strange name!) used to determine that 1355 mod 11 = 10?
    1355 mod 11
( 1311 mod 11 )5 mod 11 <-- ap mod p = a mod p
( 13 mod 11 )5 mod 11
25 mod 11
10
13128 mod 11 is found using quadratic reciprocity, since 13128 = (1364)2, and (1364)2 is congruent to 3 modulo 11, because (1364)2 is not congruent to 11 modulo 3, because x2 is not congruent to 2 modulo 3, because 3 is congruent to 3 modulo 8.

I think I've learned enough for today.

[Edited by - JohnBolton on June 5, 2006 6:35:42 PM]

Share this post


Link to post
Share on other sites
lets take a smaller example, it follows that your larger numbers work in the same exact way.

5^3 mod 4 = 125 mod 4 = 1
but we can also say 5^3 = 5*5*5, and mod is distributive in a way
so
((((5 mod 4) * 5) mod 4)*5) mod 4) =>
(1 * 5 mod 4) * 5 mod 4 =>
(1) * 5 mod 4 =>
1

You can shorten the process with a square and multiply algorithm to remove some of the multiplications.

int sqpow ( int base, int exp, int n )
{
vector<bool> bits;
for ( int cnt1 = 0; cnt1 < sizeof(int)*8; cnt1++ )
{
bool bit = exp & 1;
exp = exp >> 1;
bits.push_back(bit);
}

int rVal = 1;
while ( bits.back() == 0 ) bits.pop_back();
int sz = bits.size();

for ( int cnt1 = 0; cnt1 < sz; cnt1++ )
{
bool bit = bits.back();
bits.pop_back();
if ( bit )
{
rVal *= base;
}
else
{
rVal *= 1;
}
rVal %= n;
if ( cnt1 != sz -1 )
{
rVal *= rVal;
}
rVal %= n;
}


return rVal;
}



[Edited by - KulSeran on June 5, 2006 7:43:11 PM]

Share this post


Link to post
Share on other sites
so what about doing 13^(2^7) using KulSeran method then? as its a power to a power?

sorry if this is all daft, it's late as anythin lol and ive been drinkin.

Share this post


Link to post
Share on other sites
read all that while sober and it makes perfect sense lol.

cheers guys, i'll be less stupid in future!

Share this post


Link to post
Share on other sites
I used the Chinese Remainder Theorem for my RSA implementation. Works very well.

Share this post


Link to post
Share on other sites
You can't use fermat's little theorem directly, but you can use a result of it, namely that, if gcd(a, c) = 1, then a^b = a^(b mod phi(c)) (mod c). When working with modular equations, you can always replace the base, and any other numbers not rooted within (like exponents, logs, etc) with any number that is congruent mod c. phi() is the Euler function. For instance

13^183 (mod 11)
= 2^183
phi(11) = 10
183 = 3 (mod 10)
2^183 = 2^3 (mod 11)
= 8

In the second example,
5*5*5 (mod 4)
5 = 1 (mod 4)
You can replace all the 5s with 1 since they are congruent with the modulus.
5*5*5 = 1*1*1 = 1 (mod 4)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!