Re: Discrete logarithm and Chinese Remainder Theorem
From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 09/26/05
- Next message: tomstdenis_at_gmail.com: "Re: Google Secure Access"
- Previous message: David Wagner: "Re: Making a weak Hash stronger until a fix comes along -- concatenation of hash functions..."
- In reply to: John McKormick: "Re: Discrete logarithm and Chinese Remainder Theorem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 25 Sep 2005 22:59:09 GMT
John McKormick wrote:
>>Explain why you cannot just apply CRT to x=x1 (mod ?) and
>>x=x2 (mod ?). Then isolate the troublesome part and explain why
>>you will have a unique solution anyway with a suitable restriction.
>
>
> Actually, i dont see how to apply CRT because of exponents. In a common
> use of CRT, it's
> x = a (mod p)
> x = b (mod q)
> but here, there is exponentation.
>
> I saw i have to solve CRT modulos p-1 and q-1, but I dont understand
> why
Because for prime p, and c not a multiple of p,
c ^ (p - 1) = 1 (mod p).
So if:
c ^ u = y (mod p)
then for v such that v = u (mod p-1)
c ^ v = y (mod p).
Thus if you know
c ^ x1 = y (mod p)
c ^ x2 = y (mod q)
then one solution for x in c ^ x = y (mod p*q) is to find x such that
x = x1 (mod p-1)
x = x2 (mod q-1)
-- --Bryan
- Next message: tomstdenis_at_gmail.com: "Re: Google Secure Access"
- Previous message: David Wagner: "Re: Making a weak Hash stronger until a fix comes along -- concatenation of hash functions..."
- In reply to: John McKormick: "Re: Discrete logarithm and Chinese Remainder Theorem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
