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
    [tex](a)^{\frac{1}{x}}=(b^x)^{\frac{1}{x}}[/tex]
    [tex]a^{\frac{1}{x}}=b[/tex]
     
  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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook