16

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

oldhomemovie
  • 14,621
  • 13
  • 64
  • 99
  • 2
    Do you mean absolutely definitely prime, or most likely prime for all practical purposes? Are these primes going to be used for security purposes, or something else? – Mark Byers Nov 20 '09 at 10:55
  • 1
    @Mark_Byers i'm using Ruby. Yes, this is for security purpose. I'm trying to make an RSA encryption. – oldhomemovie Nov 21 '09 at 11:32
  • 3
    Are you just trying to teach yourself how to do it or use it for a real security sensitive application? If you want to be secure it would be much better to using the OpenSSL libraries for Ruby (see example here http://nunojob.wordpress.com/2008/12/08/rsa-encrypt-decrypt-in-ruby/) rather than trying to reimplement it yourself. – Mark Byers Nov 21 '09 at 16:29

6 Answers6

25

  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.

laalto
  • 150,114
  • 66
  • 286
  • 303
  • 5
    Optionally - read up on primes distribution to assure yourself that this algorithm is feasible (i.e. won't need trillions of attempts). – Rafał Dowgird Nov 20 '09 at 12:28
  • 3
    It won't need trillions of attempts: the density of primes is very approximately 1 in ln(x). In this case 1 in 710, but because he avoids even numbers 1 in 305. It will need trillions of trial divisions to prove it prime, unless you use a non-trivial primality test. And if you're going to need a non-trivial primality test, it's not clear to me why you wouldn't also use a non-trivial means of generating better candidates. – Steve Jessop Nov 20 '09 at 16:55
  • Thanks, this was an initial idea. Though I wanted to know if there's a quicker solution. – oldhomemovie Nov 21 '09 at 11:36
  • "Set the highest [and lowest] bit[s] to 1. This makes sure [there are no leading zeros] the prime candidate is big enough" - But that makes it not random, right? Doesn't this narrow down the interval of admissible values? Or is the question implicitly (I'm not expert in securty/encryption) "how to generate a 1024 bit random prime greater than 2^1023 + 1 (or greater than X)"? – d.. Jan 21 '10 at 15:37
  • True, you lose two bits-worth of randomness. So, you could start with the 1024 bits and prepend a '1' and append a '1' to make a 1026 bit number with 1024 bits of randomness. Of course that'll be a bit awkard on most machines made on this planet. In practice, no one is going to worry about losing two bits of randomness. – DarenW Feb 11 '10 at 15:12
  • I see the point in setting the lowest bit to 1, but I don't see the point in setting the highest bit. I think by 1024-bit number the OP is just saying the prime should be between 0 and 2^1024 - 1, not that the number strictly needs that number of bits to be represented. I'm not aware of any common practical applications of the latter. – Joseph Garvin Jan 07 '13 at 19:16
22

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

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

The above link doesn't work so you can use this archive link.

kiner_shah
  • 3,939
  • 7
  • 23
  • 37
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
3

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

glebm
  • 20,282
  • 8
  • 51
  • 67
  • 3
    -1, I think you are suggesting a probabilistic prime generator when you say pseudo prime. A pseudo prime is NOT a prime (i.e. it has divisors other than 1 and itself) although it has certain properties in common with primes, and a pseudo prime is no substitute for a prime, especially for cryptography. The fact that pseudo primes that pass probabilistic tests are rare, makes such tests good for randomly generated large numbers. But saying that the OPs needs maybe satisfied by a pseudo prime is obviously wrong. Java has a probabilistic prime check/generator, which is likely what you meant. – MAK Nov 20 '09 at 11:19
  • 1
    @Glex: Then please edit your answer so that its not misleading. – MAK Nov 20 '09 at 17:51
2

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.

mykhal
  • 19,175
  • 11
  • 72
  • 80
0

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.

Jonas
  • 1,532
  • 3
  • 16
  • 20
  • 1
    "generate them"? all of them!?! – Robin Day Nov 20 '09 at 10:52
  • 2
    This would not be a good idea if the prime numbers are needed for security reasons, as is often the case. – Mark Byers Nov 20 '09 at 10:53
  • Mark: Apart from the obvious problem of actually storing all 1024-digit primes, where is the problem with that? You'd be choosing a random prime anyway. – Joey Nov 20 '09 at 11:00
  • Johannes: Store them *all*? I hadn't assumed that was what Jonas meant. I assumed he meant store some small subset of them and then pick one at random. This would open a huge security hole if these primes are to be used in crypto. – Mark Byers Nov 20 '09 at 11:08
0

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)))
Charles
  • 11,269
  • 13
  • 67
  • 105