- #1

- 174

- 0

**Number theroy and Cryptography??**

I heard that Number theroy has apllication in Cryptography especially the bit about factorisation.How?Can anyone Explain?

Thanks in advance

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter poolwin2001
- Start date

- #1

- 174

- 0

I heard that Number theroy has apllication in Cryptography especially the bit about factorisation.How?Can anyone Explain?

Thanks in advance

- #2

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

i don't have time right now to answer in full, but if someone wants to post a reply before i get back do so.

or google for details on RSA encryption

you'll need to know about euclid's algorithm, and some basics in ring and group theory would be beneficial, particularly modulo arithemetic and the orders of elements.

- #3

- 174

- 0

Thanks

looked it up and found this good site

http://world.std.com/~franl/crypto/rsa-guts.html [Broken]

looked it up and found this good site

http://world.std.com/~franl/crypto/rsa-guts.html [Broken]

Last edited by a moderator:

- #4

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,051

- 18

The role that number theory played is that it was used to solve the key distribution problem by providing a usable "one-way" function for the encryption algorithm.

Other forms of cryptography (than RSA or PGP) do not rely on a number theoretic approach, but suffer from the difficulty (and security needed) in transporting keys.

A key is something that allows the recipient to decipher a coded message. If the key is compromised, a whole series of communications may be intercepted. Furthermore, when sending a communication to several locations, the distribution of keys becomes cumbersome. And lastly, to ensure security, it may often be safe to keep changing the key periodically, and that just adds to the complexity of the problem.

Public key encryption avoids these difficulties. And that's what RSA is.

PS : This was just meant to supplement what you got from the link you posted...which seems quite limited in explanation. The "how" of RSA (and of Euclid's algorithm) has not been talked about...I'll pass the baton on to someone else (maybe matt will take it) for that. Or I'll come back to it later.

Other forms of cryptography (than RSA or PGP) do not rely on a number theoretic approach, but suffer from the difficulty (and security needed) in transporting keys.

A key is something that allows the recipient to decipher a coded message. If the key is compromised, a whole series of communications may be intercepted. Furthermore, when sending a communication to several locations, the distribution of keys becomes cumbersome. And lastly, to ensure security, it may often be safe to keep changing the key periodically, and that just adds to the complexity of the problem.

Public key encryption avoids these difficulties. And that's what RSA is.

PS : This was just meant to supplement what you got from the link you posted...which seems quite limited in explanation. The "how" of RSA (and of Euclid's algorithm) has not been talked about...I'll pass the baton on to someone else (maybe matt will take it) for that. Or I'll come back to it later.

Last edited:

Share: