1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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