Re: public key crypto

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?

> (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)