Re: public key crypto
From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 07/07/04
 Next message: Kristian Gjøsteen: "Re: public key crypto"
 Previous message: Andrew Swallow: "Re: A law case of crypto"
 In reply to: Peter Fairbrother: "Re: public key crypto"
 Next in thread: Kristian Gjøsteen: "Re: public key crypto"
 Reply: Kristian Gjøsteen: "Re: public key crypto"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Wed, 07 Jul 2004 15:51:03 +0100
Peter Fairbrother wrote:
> Michael Amling wrote:
>
>> Peter Fairbrother wrote:
> [..]
>>> Let r = (ed mod p1),
> [..]
>>> 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
 Next message: Kristian Gjøsteen: "Re: public key crypto"
 Previous message: Andrew Swallow: "Re: A law case of crypto"
 In reply to: Peter Fairbrother: "Re: public key crypto"
 Next in thread: Kristian Gjøsteen: "Re: public key crypto"
 Reply: Kristian Gjøsteen: "Re: public key crypto"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
