Chu
Nov15-04, 02:08 PM
Hello all, here is a problem I am working on that is giving me some problems.
p,q, and N are defined as in RSA i.e.
{p,q} in (Z_p,*), N = pq
a in (Z_n,*)
g in (Z_{N^2}) s.t. g=aN+1 mod N^2
The problem is to show that the discrete log problem base g is easy in Z_{N^2}, i.e. :
given {g,c} s.t. c=g^x mod N^2, solve for x.
I've been messing around with this problem for quite a bit, and I assume that the solution has something to do with the form of g since along the way I proved (very informally) that this is NOT true for a general g*. Any further nudge in the right direction would be GREATLY appreciated.
-Chu
*assuming the discrete log problem is hard in Z_p of course
p,q, and N are defined as in RSA i.e.
{p,q} in (Z_p,*), N = pq
a in (Z_n,*)
g in (Z_{N^2}) s.t. g=aN+1 mod N^2
The problem is to show that the discrete log problem base g is easy in Z_{N^2}, i.e. :
given {g,c} s.t. c=g^x mod N^2, solve for x.
I've been messing around with this problem for quite a bit, and I assume that the solution has something to do with the form of g since along the way I proved (very informally) that this is NOT true for a general g*. Any further nudge in the right direction would be GREATLY appreciated.
-Chu
*assuming the discrete log problem is hard in Z_p of course