# Homework Help: Number Theory Question - Discrete Log mod (pq)^2.

1. Nov 15, 2004

### Chu

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