# Generating Large Prime Numbers

• Jul 25th 2009, 06:24 PM
calccrypto
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
• Jul 25th 2009, 07:20 PM
Gamma
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.
• Jul 25th 2009, 08:10 PM
calccrypto
so how do those RSA programs do it?

anyone undestand java?
http://ohdave.com/rsa/
• Jul 25th 2009, 08:42 PM
Gamma
That is the thing, there are lists of large primes that are out there, for instance:

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.
• Jul 26th 2009, 12:05 AM
CaptainBlack
Quote:

Originally Posted by Gamma
That is the thing, there are lists of large primes that are out there, for instance:

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
• Jul 26th 2009, 12:08 AM
CaptainBlack
Quote:

Originally Posted by calccrypto
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
• Jul 26th 2009, 01:48 PM
calccrypto
thats what dr math told me to do
• Jul 26th 2009, 03:08 PM
CaptainBlack
Quote:

Originally Posted by calccrypto
thats what dr math told me to do

Smart guy that Dr Math.

CB