Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 15, 2004 #1


    User Avatar

    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.


    *assuming the discrete log problem is hard in Z_p of course
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted