Proven Primes

[David Wagner]

Bill Frantz  wrote:
>I guess I'm dumb, but how to you verify a proof of Sophie Germain primeness
>with less effort than to run the tests yourself?

There are ways to prove that p is prime so that the receiver
can verify the proof more easily than it would be to construct
a proof.  The verification process is deterministic (there is
no chance of error), unlike probabilistic primality tests.

Here's a simple method, due to Pratt.  It turns out that p is
prime if and only if the multiplicative group (Z/pZ)^* of integers
modulo p is cyclic.  To show that the group is cyclic, we can
give a generator g.  To show that g is a generator, we can factor
p-1 and show that g^{(p-1)/q} != 1 (mod p) for all prime q that
divide p-1.  Thus, the proof of primality for p will be
   proof(p) = (g, q_1, proof(q_1), q_2, proof(q_2), ...)
where q_1, q_2, ... is the list of prime factors of p and where
proof(q_i) is a recursive proof of primality for q_i.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com