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

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?

Rich
For cryptographic purposes the standard definition of "random prime"
is "a prime number in the given range".

The usual method is to generate a series of random number in the range
and test each one for primality. After a number of tries you have
either found one or you need to use a bigger range.

Pseudocode:
function PrimeInRange(lo, hi) : integer
if not(2 < lo <= hi) then throw exception
limit <- 100 * (floor(log2(u)) + 1)
repeat
limit <- limit - 1
if limit = 0 then throw exception
n <- random(lo, hi)
until IsPrime(n)
return n
end function

rossum

.

Relevant Pages
Loading