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

Prime numbers use

  1. Nov 19, 2008 #1
    What is yhe usage of big primes in Cryptography?
  2. jcsd
  3. Nov 19, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    One major use is for RSA. Encrypting with RSA requires finding large random primes and doing modular arithmetic with them, which are easy. Decrypting RSA can be performed by factoring the product of the primes, which is believed to be hard.

    As an example: the 663-bit semiprime RSA-200 was factored by a cluster of computers; the lattice sieving alone was the equivalent of 55 years of work on a single processor. I multiplied the factors together on my computer; according to Pari, this took 0 ms.
  4. Nov 19, 2008 #3
    are there any uses outside cryptography?
  5. Nov 22, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    Numerical algorithms (e.g. factorial computation), pseudorandom number generation (e.g. Mersenne twister), private information retrieval schemes (see Yekhanin's Ph.D thesis), etc.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Prime numbers use
  1. Prime Numbers (Replies: 44)

  2. Prime Numbers (Replies: 24)

  3. Prime Numbers (Replies: 28)

  4. Prime number. (Replies: 7)

  5. Prime Numbers (Replies: 1)