2012Re: Random prime numbers generator
- Jul 30, 2001--- In primenumbers@e..., axel_kalbarczyk@y... wrote:
> Hi every body,It depends on what size you're looking at. If we're talking crypto,
> I am a french student and I'm looking for a random prime number
> generator. Do you you wher I could fing a C/C++ implenmentation for
> such a function? It would help me very much!
> Thanks in advance
then the following will work:
Firstly find a bignumber library which provides a probable primality
test (or a 'Miller Rabin' test). I know that GMP has such a test.
Other bignum libraries that are held in high regard are LIP and
Miracl, but I can't say off the top of my head whether they provide
such a test.
Then generate a random bitstring which in the range that you are
If the bignum library's primality test includes trial division, then
simply test every increasing number until you find a probable prime.
If it doesn't then you will want to deal with testing for small
When you've found a probable prime and you need to be absolutely
certain the value is prime, then use Marcel's excellent Titanix for a
Note: the distribution is horribly non-flat. Upper twins will be
particularly rare. (You could search down as well as up, but that
won't rescue the middle of triplets.)
Note too that GMP provides a 'next prime' function (which is
effectively what the above steps achieve), so in GMP it should be
really simple code indeed. (GMP is sloppy with the name, it means
If you need a flat distribution I can't think of anything better than
just repeatedly testing random bitstrings until you find one that is
- << Previous post in topic Next post in topic >>