# Number Theory - Elementary Cryptology

1. Dec 15, 2008

### Bellarosa

1. This is a problem involving public key cryptography
2. 16^31 is congruent to 081 (mod 247)

3. I would first evaluate 16^31 and the divided by 247 to find the remainder. I know how to work with congruences, but 16^31 is a very huge number I don't know how to evaluate it into congruence.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Dec 15, 2008

### Dick

Don't wait till the end to find the remainder, do it as you go. What's 16^2 mod 247? Now if you square that you get 16^4 mod 247, square again and you'll get the 8th power. It's not all that much work to get up to 31.

3. Dec 15, 2008

### Bellarosa

ok thank you.

4. Dec 15, 2008

### Bellarosa

ok I did what you said and I did not get 81,...I tryied the same for 8^31, and I got 8^31 is congreuent to18 (mod 247), the answer however is 8^31 is congruent to 122(mod 247)

5. Dec 15, 2008

### Bellarosa

Let me explain what I'm actually doing....the example given is to encipher the plaintext message PHONE = M using the RSA public-key system. In numerical form M is equal to 1608151405 (i.e., p is the 16th letter in the alphabet h the eight and so on).The numbers p= 13 and q = 19 are both primes and their product n=247, the enciphering formula is M^e is congruent to C (mod n), e = 31 is the exponent (the enciphering key) now because M > n, M is broken up into blocks so that C1 = 16^31, C2= 8^31 and so on, for C1 they got 16^31 is congruent to 081(mod 247), C2= 8^31 is congruent to 122 (od 247) , C3 = 15^31 is congruent to 219 (mod 247), I did what you said and I did not get 16^31 is congruent to 081 mod 247 or 8^31 is congruent to 122 mod 247....

6. Dec 15, 2008

### Dick

I do get 16^31 is 81 and 8^31 is 122 mod 247. What did you do? I really don't know RSA cryptography in any detail, but I am pretty good at mods.

7. Dec 15, 2008

### Bellarosa

ok...I have no idea what I am doing wrong...this is what I did: 16^2 is congruent to 9 mod 247 and then I squred 9 and I said 16^4 is congruent to 81 mod 247

8. Dec 15, 2008

### Dick

That's good so far. 16^8=139 and 16^16=55. Right? How do you put them all together to get 16^31?

9. Dec 15, 2008

### Bellarosa

ok I think I am missing it ... how did you get 139 I got 6561

10. Dec 15, 2008

### Bellarosa

aren't you suppse to square 81?

11. Dec 15, 2008

### Dick

6561 mod 247=139. I told you. Keep reducing it.

12. Dec 15, 2008

### Bellarosa

ok ... I got it...I forgot to divide 6561 by 247...

13. Dec 15, 2008

### Bellarosa

one more thing... finding the inverse is something I never get...for example 31x is congruent to 1 mod 6912

14. Dec 15, 2008

### Dick

15. Dec 15, 2008

### Bellarosa

ok...

16. Dec 15, 2008

### Bellarosa

ok I was just on this page the answer is 223...is there another way besides using the Euclidean Algorithm? just curious

17. Dec 16, 2008

### Dick

They describe one on the Wiki page don't they, using the Euler totient function?