A big number modulo a prime


by GatorPower
Tags: modulo, number, prime
GatorPower
GatorPower is offline
#1
Dec12-12, 09:06 AM
P: 26
Im looking through old exams for a course in Cryptography and have beaten my head against the wall for a long time on one of the questions:

p = 683 is a prime, p-1 = 2*11*31. What is x = 4^11112 mod p?

When i did chinese remainder theorem on primes 2,11,31 i got that x = 16 mod 682, but so far i have not found a way to use this in determining x mod 683..

Also, when computing discrete logs I have found that one goes from mod p to mod (p-1) alot, why is that?
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
mfb
mfb is offline
#2
Dec12-12, 10:01 AM
Mentor
P: 10,809
Can you use a computer to calculate it?
The common general approach to calculate a^b mod c will give you the answer in milliseconds.
GatorPower
GatorPower is offline
#3
Dec12-12, 10:14 AM
P: 26
It is supposedly solvable by hand, but I'm wondering if it was meant to calculate mod p-1 instead of p. Atleast thats what I'll conclude if no one finds another answer.

Also, it seems that the answer is 16 mod 683 as well. Perhaps there is some once-in-a-lifetime connection between 682 and 683 for this task?

mfb
mfb is offline
#4
Dec12-12, 10:19 AM
Mentor
P: 10,809

A big number modulo a prime


4^11 = 2^22 = 1 mod 683

I would expect that there is some way to get this from p-1=2*11*31.
The rest is easy, as 11112 = 11*1010 + 2.

4^6 = -2 mod 683 is quite interesting, too.
It is possible to calculate that by hand, but then you don't need the hint.
GatorPower
GatorPower is offline
#5
Dec12-12, 11:15 AM
P: 26
4 is quadratic residue, so 4^(p-1)/2 = 1 mod p, but then i get 4^11*31 = 1 mod p, and i need to get rid of 31.. Otherwise i get stuck with 4^200 mod p. I'll try to figure something out, thanks for the help!
ramsey2879
ramsey2879 is offline
#6
Dec12-12, 11:22 AM
P: 891
Quote Quote by GatorPower View Post
Im looking through old exams for a course in Cryptography and have beaten my head against the wall for a long time on one of the questions:

p = 683 is a prime, p-1 = 2*11*31. What is x = 4^11112 mod p?

When i did chinese remainder theorem on primes 2,11,31 i got that x = 16 mod 682, but so far i have not found a way to use this in determining x mod 683..

Also, when computing discrete logs I have found that one goes from mod p to mod (p-1) alot, why is that?
The solution is to use Fermat's little theorm. To use that you need 11112 mod 682 not x mod 682.
GatorPower
GatorPower is offline
#7
Dec12-12, 11:52 AM
P: 26
Fermat gives 4^11112 = 1*4^200 mod p, so that gets me a little further, but not quite there.
ramsey2879
ramsey2879 is offline
#8
Dec12-12, 12:19 PM
P: 891
Quote Quote by GatorPower View Post
Fermat gives 4^11112 = 1*4^200 mod p, so that gets me a little further, but not quite there.
Knowing that 4^200 =(((4^5)^2)^2)^5 should help
GatorPower
GatorPower is offline
#9
Dec12-12, 12:29 PM
P: 26
That does help, its just that i want to find a better way of doing it! Usually these things turn out to be some number squared or something, so I feel like im doing something wrong if i compute too much :p
dodo
dodo is offline
#10
Dec12-12, 12:32 PM
P: 688
p-1=2*11*31 is also phi(p), and the order of any number (for example, 2) mod p is going to be a divisor of phi(p). So there are not many combinations to try in order to find a divisor d of phi(p) such that 2^d =1 mod p.
mfb
mfb is offline
#11
Dec12-12, 02:08 PM
Mentor
P: 10,809
Quote Quote by Dodo View Post
p-1=2*11*31 is also phi(p), and the order of any number (for example, 2) mod p is going to be a divisor of phi(p). So there are not many combinations to try in order to find a divisor d of phi(p) such that 2^d =1 mod p.
I think this is the trick. You still have to calculate 4^2 mod p (trivial) and 4^6 mod p (you can stop calculating 4^11 here if you see 4^6 = -2 mod p and therefore 4^11 = 1 mod p), but you know that you don't have to calculate anything beyond 4^11.
GatorPower
GatorPower is offline
#12
Dec13-12, 05:19 AM
P: 26
Indeed, that does help. Thank you everyone for helping out!
johnqwertyful
johnqwertyful is offline
#13
Dec15-12, 02:55 PM
P: 308
The way I did it was
4^682=1 mod 683
(4^219)(4^463)=1mod 683
Then 4^11=1 mod 683
You can surely simplify 4^219 by using that

The rest should be clear.


Register to reply

Related Discussions
Modulo and prime numbers Linear & Abstract Algebra 6
Calculation of Large Exponents Modulo a Prime Calculus & Beyond Homework 2
Order of 3 modulo a Mersenne prime Linear & Abstract Algebra 4
modulo a prime Calculus & Beyond Homework 1
binomial coefficient modulo a prime Linear & Abstract Algebra 1