Menu
How do I quickly generate a random prime number, that is for sure 1024 bit long?
426
The number 11 is divisible only by 1 and the number itself. For a number to be classified as a prime number, it should have exactly two factors.
Prime numbers, of course, are not really random at all — they are completely determined. Yet in many respects, they seem to behave like a list of random numbers, governed by just one overarching rule: The approximate density of primes near any number is inversely proportional to how many digits the number has.
Seven is a prime number because it doesn't have proper factors. In other words, the only factors of 7 are 1 and itself. To be sure of this, let's verify that none of the numbers greater than 1 and less than 7 divides 7. The numbers greater than 1 and less than 7 are 2, 3, 4, 5, and 6.
Generate 1024 random bits. Use a random source that is strong enough for your intended purpose.
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).
Test for primality. If it's not a prime, go back to 1.
Alternatively, use a library function that generates primes for you.
154
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.
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
