Re: Fast generation of primes

From: Francois Grieu (fgrieu_at_francenet.fr)
Date: 04/05/04 

Date: Mon, 05 Apr 2004 12:38:04 +0200

In article <LRBbc.20442$jVF.5363@news04.bloor.is.net.cable.rogers.com>,
 Tom St Denis <tom@securescience.net> wrote:

> Generate a table that correspond to each prime in the base called T.
>
> 1. pick random number N, make sure it's odd and the msb is set
> 2. for i = 1 to #T do
> 2.1 T[i] = N mod P[i]
> 3. while (not pass Miller-Rabin) do
> 3.1 do
> 3.1.1 N = N + 2, flag = false
> 3.1.2 for i = 1 to #T do
> 3.1.2.1 T[i] = T[i] + 2 (mod P[i]), if T[i] = 0 set flag = true
> 3.2 while flag = true
> 4. return N as probably prime
(...)
> there will be skew towards several primes
> [e.g. ones with the most distance between primes].

The problem is not to be feared if one first picks a random
even step >> log(N), rather than 2; this is necessary anyway
if the primes are to be conformant to ANSI X9.31,
which requires assurance that p-1 and p+1 both have
a randomly seeded prime factor >2^100.

   Francois Grieu

Relevant Pages

  • Re: Montgomery Reduction for GF(2)[x] ?
    ... Tom St Denis wrote: ... if the lsb of pis one then ... if the msb of pis one then ...
    (sci.crypt)
  • Re: Schneiers "Helix" cipher is remarkably similar to the "generic feistel cipher&qu
    ... Tom St. Denis wrote: ... a cipher to the design of simpler components, ... the cipher answered to by Wagner ...
    (sci.crypt)
  • Re: XORShift PRNG as a diffusion structure
    ... >>like him and Tom St Denis. ... > This isn't the first time you've done this before [or the first time ... number of general readers would certainly have been angry ...
    (sci.crypt)
  • Re: AES trickery ;-)
    ... Too bad you missed the day in school where they taught you to ... Someone who reads the above diatribe about how Tom St Denis demands ... you're too american to sit down and work out the details ...
    (sci.crypt)
  • Re: Working on ARC4-16 bit
    ... Well, i'm sorry about what happened with Tom St Denis, i have esteem ... of him and personally i had found interesting many of his posts here. ... deeply tested by highly qualified matematicians and cryptoanalists it ...
    (sci.crypt)