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

A=x^b mod p, solvable?

  1. Nov 14, 2004 #1


    User Avatar

    Say you are given a=x^b mod p, where p, a, and b are known. Is there a way to solve this? I am pretty sure there is . . . but it is driving me nuts.

  2. jcsd
  3. Nov 15, 2004 #2
    Try solving x^2 = 2 (mod 3).
  4. Nov 15, 2004 #3


    User Avatar

    Sorry, I'll rephrase. I know a solution must exist from the choices of p,b,and a (this is part of a crypto algorithm where they know x, I do not, and I am wondering if I have sufficent info to solve for it).
  5. Nov 15, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You can of course solve it - all one needs is to raise every remainder to the b'th power. However, I don't think there is a better solution except in certain circumstances.

    obviously b must divide [tex]\varphi(x)[/tex], but that doesn't give a sufficient condition for a solution, or even tell you what it is.

    The reason for my scepticism is that it is a well known and difficult problem to find generators of the group of units mod a prime (which is a cyclic group).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook