Maurer's algorithm

[Niels Möller]

I'm considering implementing some variant of Maurer's algorithm to
generate prime numbers for cryptographic purposes. It's not obvious
that's a useful thing to do, instead of using mpz_next_prime (which is
sieving + probabilistic primaliy testing). Some possibly valid reasons:

1. If one is paranoid enough to use a high repeat count (say, 25 as was
   suggested by Knuth) for the Miller-Rabin test, Maurer's algorithm may
   be faster.

2. One need not worry about the probability of the theoretical
   miller-rabin giving an incorrect result. Instead, one should of course
   worry about implementation and hardware errors.

3. One always gets primes with a fairly large factor in p-1, which is
   sometimes beneficial.

3. It's mandated in FIPS186-3 for the generation of DSA parameters for
   certain key sizes.

The algorithm is simpler than I expected. Given a desired bit size k,
first recursively generate a prime q of bit size 1 + ceil(k/2). (The
description in Handbook of Applied Cryptography, Alg. 4.62, uses 1 +
floor(k/2) instead, I suspect that's incorrect for odd k).

Next, select a random r, and set n = 2 q r + 1 as a candidate prime,
with r chosen from the interval which corresponds to n being precisely k
bits.

To check if n is prime, first subject it to some trial division and
maybe a single Miller-Rabin test. If it passes that, we invoke
Pocklington's theorem, which says that if q and a are such that

  q is a prime factor of n-1, and q > sqrt(n)-1
  a^{n-1} = 1 (mod n)
  gcd(a^{(n-1)/q} - 1, n) = 1

then n is prime. Certainly. Furthermore, if n is prime, almost any a, a
!= ±1 (mod n), will do, so we need only try one a (not sure if one
really needs to select a randomly, or if it's good enough to always use
a = 2 or 3 or so. If one uses the same base as for the Miller-Rabin test
(which computes a^{(n-1)/2^j} for some j:s, one can share a big
exponentiation cost).

And if n doesn't pass this primality testing, we repeat with a
different r.

As a base case, when k is small (HoAC suggests when k <= 20), chose a
random number of the right size and do trial division using a list of
primes < 2^10. (And when k < 10, one could consider random selection
from the prime list, I guess).

Implementing this on top of GMP, I think it makes some sense to use
mpz_probab_prime_p with REPS=1 for the combination of some sieving and
one miller-rabin test.

But I'm not aware of any public gmp function that can be used for the
basecase, since the threshold used by mpz_probab_prime_p (currently
1000000) is not public, so I'll do my own sieving there.

I also have two related questions.

1: HoAC suggests that a single Miller-Rabin test to the base 2 is
particularly efficient. I wonder if that's true in GMP, or if it should
be. The crucial operation is the computation

  2^r mod n

One obvious thing to do (which can be done for any small base) is to
chose k so that 2^k is of roughly the same size of n, and then compute

  (2^k)^{floor(r/k)} * 2^{r mod k} (mod n)

Code to do something like that seems to be in mpz_powm, but currently
#if:ed out. Is there anything else that applies particularly to the base
2 (or slightly more generally, a base that is a power of two?) I imagine
the redcification could exploit this. Anything else?

2: Maybe one could speed up Maurer's algorithm a little by sieving for
r. I.e., when one r fails, don't go for a random one but try r+1, r+2,
and so on (or r + delta, where delta is a *small* random quantity). One
useful function might be

  /* Similar to mpz_nextprime, finds the first (odd) prime of the form n
     + k * step, with k >= 1. If n and step has a common factor, it never
     terminates... */
  static void
  mpz_nextprime_step (mpz_ptr p, mpz_srcptr n, mpz_srcptr step_in);

There's an implementation in tests/mpz/t-jac.c, but it was slower than I
expected and I'm not sure it's right.

Regards,
/Niels
-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.