Random prime number

问题:

How do I quickly generate a random prime number, that is for sure 1024 bit long?

回答1:

1. Generate 1024 random bits. Use a random source that is strong enough for your intended purpose.

2. Set the highest and lowest bits to 1. This makes sure there are no leading zeros (the prime candidate is big enough) and it is not an even number (definitely not prime).

3. Test for primality. If it's not a prime, go back to 1.

Alternatively, use a library function that generates primes for you.

回答2:

Use a library function, such as OpenSSL. There's no need to write this yourself.

Example: http://ardoino.com/7-maths-openssl-primes-random/

回答3:

1024 is a lot. Are you sure a probabilistic prime won't do? Probabilistic prime generator is part of JDK

回答4:

You do not specify a context/language/platform.. if you'd like to use unix/linux-like system and shell, you might consider a solution involving OpenSSL version >= 1.0.0:

$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677

If you got the same result, something is very wrong with the universe.

Add -hex option if you like hexadecimal system.

回答5:

To trade memory for speed you could just generate them and store them in a list and then randomly pick one.

Edit: Naturally you can't generate them all so the best you could achieve is pseudo randomness at a high memory cost. Also this isn't good if you want it for security.

回答6:

In PARI/GP:

randomprime([2^1023,2^1024])

If you'd like to do this in 'library mode'

#include <pari/pari.h>
// ...
randomprime(mkvec2(int2u(1023), int2u(1024)))