# Number theroy and Cryptography?

1. Sep 30, 2004

### poolwin2001

Number theroy and Cryptography??

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

2. Sep 30, 2004

### matt grime

the simplest version is public encode/decode, and is not secure because both you and the person you're communicating to can encode and decode, amongst other reasons, and relies on some properties of rings, this isn't what you're asking about but it's a good starting place before you go onto RSA in full since it introduces several things you'll need.

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. Sep 30, 2004

### poolwin2001

Thanks
looked it up and found this good site
http://world.std.com/~franl/crypto/rsa-guts.html [Broken]

Last edited by a moderator: May 1, 2017
4. Sep 30, 2004

### Gokul43201

Staff Emeritus
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.

Last edited: Sep 30, 2004