[12693] in cryptography@c2.net mail archive
Re: Proven Primes
daemon@ATHENA.MIT.EDU (David Wagner)
Fri Mar 7 15:41:18 2003
X-Original-To: cryptography@wasabisystems.com
X-Original-To: cryptography@wasabisystems.com
X-Envelope-To: cryptography@wasabisystems.com
To: cryptography@wasabisystems.com
From: daw@mozart.cs.berkeley.edu (David Wagner)
Date: 7 Mar 2003 18:30:37 GMT
X-Complaints-To: news@abraham.cs.berkeley.edu
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@wasabisystems.com
