Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theroy and Cryptography?

  1. Sep 30, 2004 #1
    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
  2. jcsd
  3. Sep 30, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Sep 30, 2004 #3
    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
  5. Sep 30, 2004 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook