1. Not finding help here? Sign up for a free 30min 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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Number Theory Question - Discrete Log mod (pq)^2.
  1. Kinetic theory HW help (Replies: 0)