How do I use Chinese remainder theorem to solve for x mod 683 in Cryptography?

  • Thread starter GatorPower
  • Start date
  • Tags
    Prime
In summary, the conversation discusses a question on determining the value of x = 4^11112 mod p, where p = 683 is a prime and p-1 = 2*11*31. The participants explore various methods, including the Chinese remainder theorem and Fermat's little theorem, to find a solution. They also discuss the use of discrete logs and how it relates to mod p and mod (p-1). Ultimately, they come to the conclusion that the solution is 16 mod 683 and that there are various ways to calculate it, such as using the fact that p-1 is also phi(p).
  • #1
GatorPower
26
0
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?
 
Physics news on Phys.org
  • #2
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.
 
  • #3
It is supposedly solvable by hand, but I'm wondering if it was meant to calculate mod p-1 instead of p. Atleast that's 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?
 
  • #4
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.
 
  • #5
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!
 
  • #6
GatorPower said:
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.
 
  • #7
Fermat gives 4^11112 = 1*4^200 mod p, so that gets me a little further, but not quite there.
 
  • #8
GatorPower said:
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
 
  • #9
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 I am doing something wrong if i compute too much :p
 
  • #10
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.
 
  • #11
Dodo said:
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.
 
  • #12
Indeed, that does help. Thank you everyone for helping out!
 
  • #13
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.
 

1. What is a big number modulo a prime?

A big number modulo a prime is a mathematical operation that involves dividing a large number by a prime number and finding the remainder. It is commonly denoted as "a mod p" or "a % p", where a is the big number and p is the prime number.

2. Why do we use modulo with a prime number?

Using a prime number as the divisor in a big number modulo operation ensures that the resulting remainder is unique. This is because prime numbers have no divisors other than 1 and itself, making it less likely for the remainder to be repeated.

3. What is the significance of using a prime number as the divisor?

Using a prime number as the divisor in a big number modulo operation has several important properties. First, it ensures that the remainder is always smaller than the divisor, making it easier to work with. Additionally, the resulting remainder is also useful in cryptography and number theory applications.

4. How is a big number modulo a prime calculated?

To calculate a big number modulo a prime, we use the modulus operator (%) in programming languages or the "mod" function in mathematical notation. First, we divide the big number by the prime number and find the remainder. The resulting remainder is the result of the big number modulo the prime.

5. Can a big number be divided by any prime number?

Yes, a big number can be divided by any prime number. However, the resulting remainder may not be unique if the prime number is not large enough. It is recommended to use a prime number that is at least half the size of the big number for a unique remainder.

Similar threads

  • Linear and Abstract Algebra
Replies
4
Views
3K
  • General Math
Replies
1
Views
1K
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
2
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top