I'm playing around and trying to write an implementation of RSA. The problem is that I'm stuck on generating the massive prime numbers that are involved in generating a key pair. Could someone point me to a fast way to generate huge primes/probable primes?
+4
A:
Take a look at how TrueCrypt does it. Also, take a look at Rabin-Miller for testing large pseudoprimes.
JP Alioto
2009-07-18 00:31:12
+1
A:
You didn't mention what language you are using. Some have a method of doing this built in. For example, in java this is as easy as calling nextProbablePrime() on a BigInteger.
Peter Recore
2009-07-18 00:32:19
I'm using Objective-C
computergeek6
2009-07-18 00:47:27
+1
A:
The previous answer is incorrect: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
I think the poster is misremembering the (real) proof that there are are an uncountable number of prime numbers.
Actually, there's only a countable (but infinite) number of primes. Also, the other poster (whose post seems to be deleted now) is not misremembering the construction from the proof (that's really how it goes) but is rather misusing it.
oggy
2009-07-18 10:43:42
Indeed. Remember that integers are countable, it goes "1, 2, ...". So are primes and rationals; it's real numbers that are not countable.
jrockway
2009-07-20 07:37:42
A:
Mono has a BigInteger class that's open source as does java. You could take a look at those. They're probably portable :) g'luck
the_ajp
2009-07-20 07:34:16
+8
A:
You don't generate prime numbers exactly. You generate a large odd number randomly, then test if that number is prime, if not generate another one randomly. There are some laws of prime numbers that basically state that your odds of "hitting" a prime via random tries is (2/ln n)
For example, if you want a 512-bit random number, you will find one in 2/(512*ln(2)) So roughly 1 out of every 177 of the numbers you try will be prime.
There are multiple ways to test if a number is prime, one good one is the "Miller-Rabin test" as stated above.
Also, OpenSSL has a nice utility to test for primes:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
James
2009-07-20 23:57:27