Results 1 to 8 of 8

Math Help - Generating Large Prime Numbers

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    4

    Generating Large Prime Numbers

    How are randomly large prime numbers chosen and proven to be prime?

    in RSA, two random prime numbers are multiplied, but how is the first number chosen? i would guess just putting together 0s and 1s in binary and then testing the result, but how do you test it? if im wrong, then whats the answer to the first question?

    How do programs/scripts that output prime numbers work (in pseudo-code please)?

    whats the general idea to generating prime numbers? i know the 2^x-1 thing, but its useless if you cant test the number. and the square root trick is too time consuming for the computer
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    It is very very difficult to construct large prime numbers for exactly the reasons you have pointed out. That is precisely the reason we use the RSA code to encrypt things. If you did have a very good way to generate large prime numbers I would guess the NSA would like to talk to you very badly.

    I was a member of one of those distributive computing projects that helped search for large primes of the form k\cdot 2^n-1 called Riesel Sieve Project. I am not sure if it still exists or not, I got a new computer and never got around to reinstalling it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2009
    Posts
    4
    so how do those RSA programs do it?

    anyone undestand java?
    http://ohdave.com/rsa/
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    That is the thing, there are lists of large primes that are out there, for instance:
    The Prime Database: The Top 5000: Downloading the List

    So the idea is everyone has a public key and a private key, large prime numbers from a list like that. You multiply two really big prime numbers together and it is next to impossible to factor them if you don't already know one of them. So you use this to encrypt any messages. Like you pointed out, to determine the factorization you would need to check every prime number less than the square root of the product. This would take so long that a brute force attempt would never work if you didn't know one of the prime numbers. But because the person you send the message to knows one of the primes in the factorization they can decrypt it. This is a very simplified overview of how it works, but if you are interested in it, the following gives a pretty decent explanation of how the math behind it actually works.
    marasingha :: the RSA code and congruences


    The key trick comes down to using the Fermat-Euler theorem, but you need to know the number of elements relatively prime to whatever the modulo is (the two large primes multiplied together), this is the Euler totient function. Which is really easy if you know what the two primes are, you simply subtract 1 from each and multiply those two together and that is the order of the multiplicative group, and you can take advantage of Lagrange's theorem.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Gamma View Post
    That is the thing, there are lists of large primes that are out there, for instance:
    The Prime Database: The Top 5000: Downloading the List
    You can't use large primes off of a published list, since hackers then need only try factors on the published lists.

    As the density of primes near n is approximately 1/\ln(n) more than 1% of 100 bit integers are prime, so testing random odd 100 bit integers until you find a prime is entirely feasible (as would be 500 or more bit integers as \ln increases so slowly).

    CB
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by calccrypto View Post
    How are randomly large prime numbers chosen and proven to be prime?

    in RSA, two random prime numbers are multiplied, but how is the first number chosen? i would guess just putting together 0s and 1s in binary and then testing the result, but how do you test it? if im wrong, then whats the answer to the first question?
    Google for primality testing (or go straight to the Wikipedia article)

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2009
    Posts
    4
    thats what dr math told me to do
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by calccrypto View Post
    thats what dr math told me to do
    Smart guy that Dr Math.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Prime factoring a large number.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 10th 2011, 04:10 AM
  3. Prove a large number is prime
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 1st 2011, 10:17 PM
  4. Replies: 13
    Last Post: December 19th 2010, 03:09 PM
  5. Comparing large prime powers.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 9th 2010, 07:08 AM

Search Tags


/mathhelpforum @mathhelpforum