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

Find b from a = b^x

  1. Aug 17, 2009 #1
    How to find b from a = b^x mod x^2, where a and x are known? prime factors p and q of x are also known.
    Last edited: Aug 18, 2009
  2. jcsd
  3. Aug 17, 2009 #2
  4. Aug 18, 2009 #3
    in modular arithmetic please!
  5. Aug 18, 2009 #4
    Use Euler's theorem.
  6. Aug 18, 2009 #5
    thanks dragonfall, i looked up the euler's theorem but i don't see how to apply it to my problem. could you please elaborate how? thanks!
  7. Aug 18, 2009 #6
    I'm sorry, I think I'm mistaken with Euler's theorem.

    If [tex]a\equiv b^n (\mod n^2)[/tex] then [tex]|a-kn^2|=b^n[/tex] for some k which can be computed easily. Then you can use an n-th root extraction algorithm, without modular arithmetic.

    But then I'm not using the fact that the factors of n are known, so maybe this isn't a good solution. Maybe I missed something.
  8. Aug 25, 2009 #7
    What I said above is an exponential algorithm, so please ignore it.
  9. Sep 25, 2009 #8
    Is there necessarily a unique solution, e.g. 0^6 = 6^6 mod 36
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook