Re: public key crypto

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 07/05/04 

Date: Mon, 05 Jul 2004 22:14:21 +0100

Michael Amling wrote:

> Peter Fairbrother wrote:
[..]
>> Let r = (ed mod p-1),
[..]
>> Then for all A, 0 < A < p
[..]
>> A^de = A^r mod p.
>>
>> Now RSA requires that A^de = A mod p, and this is only true iff r=1;
>
> The "if" part of this "iff" is obvious. Do you have a proof of the
> "only if"?

Proving that for all primes p a generator for Zp exists would do it (call
the generator a. For case A=a the only possible value for r such that a^r =
a is 1, any other possible value is excluded by a counting argument).

I'm pretty sure I've seen a proof that a generator exists for all Zp, but I
don't know what it's called. Before I go further, does anyone know offhand?
I had no lock with a quick Google.

> (Also, it would be better to explicitly state that 1<=r<=p-1).

Agreed, though r is defined above so (I have rewritten it to make it
clearer). 

-- 
Peter Fairbrother

Relevant Pages

  • Re: public key crypto
    ... > Proving that for all primes p a generator for Zp exists would do it (call ... > I'm pretty sure I've seen a proof that a generator exists for all Zp, ... primitive roots mod p. ...
    (sci.crypt)
  • complex zero-knowledge proof?
    ... I don't know maybe the zk-proof I am searching for, ... Let g be a generator of a group G with prime order p. Let further be h, ... A prover P has 2 secrets s and A, the values h, g and p are publicly known. ... The problem of proving the correctness of c_1 is quite easy: ...
    (sci.crypt)
  • Re: public key crypto
    ... Peter Fairbrother wrote: ... > Proving that for all primes p a generator for Zp exists would do it (call ... > I'm pretty sure I've seen a proof that a generator exists for all Zp, ...
    (sci.crypt)
  • AP-Prime-Generator APPG Re: possible Riemann Hypothesis proof; #137;
    ... rather strange since Euclid's Number in Euclid's Infinitude of Primes ... have devised a Generator of primes, all the primes in that time period. ... So it looks ideal for the Moebius function ... of the Sieve of Eratosthenes. ...
    (sci.math)
  • Re: order of an element
    ... >The question of what order residue 2 has in Z/pZ, p an odd prime, ... >primes, ... >generator of this cyclic group for infinitely many odd primes p. ... >of primes p for which non-square a> 1 is a primitive root). ...
    (sci.math)