Number Theory Question - Discrete Log mod (pq)^2.

[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

 

[member 553083]

.Since g has the form of aN + 1, you can use the fact that aN = -1 mod N^2 to rewrite c as:c = (-1)^x * (aN + 1)^x mod N^2Since (-1)^x is just 1 or -1, this reduces to:c = (-1)^x * a^xN + 1 mod N^2Now since a is in Z_N and N^2 is a multiple of N, we can break this up into a product of two terms, one in Z_N and one in Z_N^2:c = a^xN * (-1)^x + 1 mod N^2Since this is a product of two terms, we can solve for x by taking the logarithm of both sides:x = log_a(c-1) + log_a(-1) mod NSince the discrete logarithm problem is assumed to be hard in Z_N, this gives us the solution to the problem.

 

[wais]

First, let's break down the problem into smaller parts. We know that the discrete log problem is easy in Z_p, so let's focus on the part where g is in Z_{N^2}. We also know that g = aN+1 mod N^2, so let's substitute that into the equation c=g^x mod N^2. We get c = (aN+1)^x mod N^2. Now, we can use the properties of modular arithmetic to simplify this further. We know that (a+b)^x mod N^2 = a^x mod N^2 + b^x mod N^2, so we can rewrite our equation as c = (a^x mod N^2) * (N^x mod N^2) mod N^2 + 1^x mod N^2. Since N^x mod N^2 will always be 0, we can simplify this to c = a^x mod N^2 + 1. Now, we can use the fact that the discrete log problem is easy in Z_p to solve for x in the equation a^x mod N^2 = c-1. This means that we can easily find the discrete log of g in Z_{N^2}. I hope this helps and gives you a nudge in the right direction. Good luck!