Re: Algorithm to generate prime number from fix SERIAL

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

Date: Fri, 30 Apr 2004 00:11:17 +0200

konrad.herrmann@stud.tu-ilmenau.de 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 sent a reply but didn't notice that one of the groups
was moderated. So here is a quick repetition of that.]

If your serial numbers are sufficiently small, they could
be mapped to consecutive prime numbers (above a certain
base, if desired) in a range that is also not big. One
could choose a number n and tabulate the n-th, 2n-th,
.... prime numbers. One can thus find the k-th prime number
(i*n <= k < (i+1)*n) fairly quickly by starting from the
i*n-th prime number via repeatedly adding 2 and testing for
primality, which can be done through trial division with
the help of a small table of prime numbers. If the trial
divisors needed exceed the largest entry in the table,
the computing efficiency would be bad, since the divisors
would themselves have to be found through primality testing
in the same manner. But hopefully this will rarely be the
case, since your serial numbers, according to you, are
presumably not big.

M. K. Shen