Re: Algorithm to generate prime number from fix SERIAL

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 22:52:05 +0200

konrad herrmann wrote:

> I'm searching for an algorithm doing this:
>
> -Generate from a fix-length SERIAL number a prime number.
> -Nearly every SERIAL shold produce an other prime number.
> -Every time one SERIAL must produce the same prime number.
>
> My problem is the efficency of the algorithm:
> It should be very fast and use only a small memory size.

I suppose you could do this: Depending on the range you
are interested in, you could choose a number n and
tabulate the n-th, 2n-th, .... primes. So given k such
that i*n <= k < (i+1)*n you could start from the i*n-th
prime and successively add 2 to it and check for the
primality (employing a small table of primes for trial
division) to determine the primes that follow, thus
arriving at the k-th prime. If your range is sufficiently
small, that table would be fine, otherwise the computing
efficiency would be quite bad, since larger trial
divisors (i.e. those exceeding the content of the table)
would themselves have to be found through trial divisions.

M. K. Shen