Number Theory - Elementary Cryptology

In summary, the conversation is about a problem involving public key cryptography and evaluating the congruence of 16^31 and 081 (mod 247). The participants discuss different methods for finding the remainder, including breaking the numbers into blocks and using the Euclidean algorithm. They also discuss the use of RSA cryptography in enciphering a message and finding the inverse using the Euclidean algorithm or the Euler totient function.
  • #1
Bellarosa
48
0
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.
 
Physics news on Phys.org
  • #2
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
ok thank you.
 
  • #4
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
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
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
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
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
ok I think I am missing it ... how did you get 139 I got 6561
 
  • #10
aren't you suppse to square 81?
 
  • #11
6561 mod 247=139. I told you. Keep reducing it.
 
  • #12
ok ... I got it...I forgot to divide 6561 by 247...
 
  • #13
one more thing... finding the inverse is something I never get...for example 31x is congruent to 1 mod 6912
 
  • #15
ok...
 
  • #16
ok I was just on this page the answer is 223...is there another way besides using the Euclidean Algorithm? just curious
 
  • #17
They describe one on the Wiki page don't they, using the Euler totient function?
 

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It explores patterns in numbers and their behavior, and has applications in fields such as cryptography, computer science, and physics.

2. How is number theory used in elementary cryptology?

Number theory plays a crucial role in elementary cryptology, as it provides the foundation for many encryption techniques. For example, prime numbers are used in generating keys for symmetric and asymmetric encryption, and modular arithmetic is used in creating one-time pads for secure communication.

3. What is the difference between symmetric and asymmetric encryption?

Symmetric encryption uses a single key to both encrypt and decrypt a message, while asymmetric encryption uses a public key and a private key. The public key is used to encrypt the message, and the private key is used to decrypt it. This allows for secure communication without the need for both parties to have the same key.

4. How does modular arithmetic work in cryptology?

Modular arithmetic is used in cryptology to perform mathematical operations on large numbers in a way that is computationally efficient and secure. In modular arithmetic, numbers "wrap around" a fixed value, known as the modulus. This allows for the creation of one-time pads, which are used to encrypt messages by combining them with a random string of numbers.

5. What is the significance of prime numbers in cryptography?

Prime numbers are crucial in cryptography, as they are used in generating keys for secure communication. This is because prime numbers have only two factors (1 and itself) and are therefore difficult to factorize, making it difficult for hackers to decrypt messages without the correct key.

Similar threads

How can I find 544 mod 3 using congruence
    • Calculus and Beyond Homework Help
Replies
27
Views
2K
Finding the orders of 1, 2, .... , 16 (mod 17)
    • Calculus and Beyond Homework Help
Replies
1
Views
5K
I Modulo and Modulus in math and computer programming
    • General Math
Replies
5
Views
2K
Set theory, intersection of two sets
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Discussion on Astronomical Prime Numbers and Re-evaluating the Primali
    • General Discussion
Replies
5
Views
422
I What should I say about elementary number theory?
    • General Math
Replies
2
Views
964
MHB What should I say about elementary number theory?
    • General Math
Replies
3
Views
1K
Using Fermat's Little Theorem to Find Prime Factors of 10^12 -1
    • Calculus and Beyond Homework Help
Replies
10
Views
2K
Euler's Totient Function, Proof
    • Calculus and Beyond Homework Help
Replies
9
Views
2K
I How to introduce quadratic residues?
    • General Math
Replies
2
Views
858

Hot Threads

Recent Insights

Back
Top