Loading ...
Sorry, an error occurred while loading the content.

2012Re: Random prime numbers generator

Expand Messages
  • Phil Carmody
    Jul 30, 2001
    • 0 Attachment
      --- In primenumbers@e..., axel_kalbarczyk@y... wrote:
      > Hi every body,
      >
      > 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

      It depends on what size you're looking at. If we're talking crypto,
      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
      looking for.
      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
      factors yourself.
      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
      deterministic test.

      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
      _probable_ prime.)

      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
      prime.

      Phil
    • Show all 4 messages in this topic