Re: How to test a pseudo random prime number generator?

On Sun, 19 Aug 2007 16:41:06 -0400, quasi <quasi@xxxxxxxx> wrote:

On Sun, 19 Aug 2007 12:15:08 -0700, rich burge <r3769@xxxxxxx> wrote:

On Aug 19, 11:36?am, quasi <qu...@xxxxxxxx> wrote:
On Sun, 19 Aug 2007 11:29:04 -0700, rich burge <r3...@xxxxxxx> wrote:
There a a variety of techniques for testing the quality of random
number generators (DIEHARD, NIST, Knuth, ect.). How can I test the
quality of a "random prime number generator"?

First, you have to define what you mean by a random prime.

This part of my problem, I am not sure what I mean by a "random
prime".

But suppose we define

random_prime(x):=nextprime(random(x))

[Here random(x) is a random number between 0 and x-1 and nextprime(x)
is the first prime larger than x.] If the underlying x's are all
small, no problem. But what if the x's are large?

Perhaps better to specify a range, so as to avoid small primes (unless
you don't want to avoid them).

Thus, suppose you want a random 10-digit prime number.

Here's one approach ...

Let pi(x) be the number of primes <= x and let p_n denote the n'th
prime.

Suppose you have an efficient way to calculate pi(x).

Let a=pi(10^9) and let b=pi(10^10). Choose a random integer n between
a+1 and b inclusive. Then take p_n as the random prime.

Note, assuming pi(x) can be efficiently calculated for 10^9 <= x <=
10^10, then, by binary search, p_n can also be efficiently calculated.

The method above produces a uniformly random 10-digit prime, however
unless pi(x) can be efficiently calculated for 10^9 <= x <= 10^10, the
method is impractical.

As an alternative, let's try a method similar to the one you outlined,
but restricted to producing 10-digit primes.

Thus, take a random number x between 10^9 and 10^10-1 inclusive. If x
is prime, take x, otherwise take the next prime after x, rejecting it
exceeds 10^10-1.

This method is efficient but does not produce a uniform distribution
of 10-digit primes. The lack of uniformity is due to the fact that the
probability that a prime is chosen is proportional to the distance to
the previous prime, or to 10^9, whichever distance is less. Thus, if p
and p+2 are successive 10-digit primes, and if q and q+4 are also
successive 10-digit primes, then q+4 has twice as much chance of being
selected as p+2.

Ignore the proposed method for correcting the non-unformity -- it's
not correct.

10-digit primes and their next or previous primes, to get an
approximate distribution of gaps. Once you have a distribution of
gaps, you can then begin choosing "random" primes as previously
described, but selectively reject to maintain the fair distribution.
In essence, you restore the correct balance ("affirmative action" for
primes).

The distribution of gaps is irrelevant. What is relevant is the actual
gaps for the candidate random primes.

Here's a corrected version, step by step ...

(1) Choose a random number x between 10^9 and 10^10-1 inclusive.

(2) If x is prime, let p=x, otherwise let p = nextprime(x), but in the
latter case, if p > 10^10-1, go back to step (1).

(3) Let d = p - max(prevprime(p),10^9-1)

(4) If d=1, then accept p, otherwise accept p with probability 1/d. If
p is rejected, go back to step (1).

The distribution is now exactly uniform on the set of all 10-digit
primes.

The main disadvantage is that by this method, for 10-digit primes,
only 1 in approximately 22 prime candidates is accepted, on average.

Thus, when compared with the method which accepts all candidates, this
method is about 22 times slower, but at least it's truly uniform
(assuming the underlying RNG is regarded as uniform).

quasi
.

Relevant Pages

  • Re: How to test a pseudo random prime number generator?
    ... number generators. ... This method is efficient but does not produce a uniform distribution ... approximate distribution of gaps. ...
    (sci.math)
  • Re: Primes algorithm
    ... distribution. ... The gaps between primes are not uniform, ... suppose you have the following for three consecutive primes: ...
    (sci.crypt)
  • Re: How to test a distribution for uniformity?
    ... > observations occured is roughly uniform. ... > distribution of observation times differs significantly from ... I am using bins (those are my 45 minute ... I wonder is there such a thing as a chi-square test which is adjusted to ...
    (sci.stat.math)
  • Re: Randomly generated convex polygon
    ... gaps actually do happen, at least with small number of sides. ... leaving the fifth side to extend over 2/3 of the angular range. ... If you look at the histograms, you can see that the distribution ... or small N) see standard deviations more than half of the mean; ...
    (comp.soft-sys.matlab)
  • Re: random number problem
    ... It's a simple linear transformation. ... your distribution will be ... which is what theory says it should be for a uniform ... If you want a *serious* random number generator, ...
    (comp.programming)