Re: public key crypto

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

Date: Wed, 07 Jul 2004 15:51:03 +0100

Peter Fairbrother wrote:

> 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.

"Burton, D. M. "Primitive Roots for Primes," §8.2 in Elementary Number
Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, 1989." is said to
contain a proof, but I haven't got a copy handy. 

-- 
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)
  • Re: public key crypto
    ... Michael Amling wrote: ... Proving that for all primes p a generator for Zp exists would do it (call ...
    (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)
  • 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: 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)
Quantcast