Maurer's algorithm

[Niels Möller]

Pedro Gimeno <gmpdevel at personal.formauri.es> writes:

> Please keep in mind that GMP does not generate cryptographically secure
> random numbers and currently doesn't support pluggable generators
> either.

I'm aware of that; I'm using my own generator based on Yarrow. The
immediate objective is support for the revised FIPS186-3 specification
of DSA in the Nettle library.

So this discussion might be slightly off-topic on this list and belong
on gmp-discuss. I don't have any immediate plans to get the main
random_prime function integrated into GMP, but underlying primitives,
like trial division (current interface is for internal use only, iirc),
and powm for small bases are relevant for GMP.

Anyway, I have a somewhat better understanding of the mathematics now. I
think Maurer's algorithm should apply Pocklington's theorem with n = 1 +
2 r q and completely factorized part 2 q (not just q). If one also
performs a Miller-Rabin test to the same base, in a parallel fashion
sharing computed and implied values, I think it boils down to checking

  a^{(n-1)/2} = -1 (mod n)
  gcd(a^{(n-1)/q} - 1, n) = 1

The first condition is interesting; for a full Miller-Rabin one sets n-1
= 2^s m, m odd, s >= 1, and one then computes a^{2^k r} for k = 0, ...
s-1. If n passes this test, this implies that a^{(n-1)} = 1 (mod n) and
that a^{(n-1)/2} = ± 1 (mod n).

The condition to test for Pocklington's theorem corresponding to the
known factor 2 of n-1 is

  gcd(a^{(n-1)/2} - 1, n) = 1

This excludes the case a^{(n-1)/2} = 1 (mod n), so to check that both
the Miller-Rabin conditions and this Pocklington condition holds, one
should check that a^{(n-1)/2} = -1 (mod n), which is simpler than
Miller-Rabin. I wonder if I'm missing something.

Regards,
/Niels

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