Is There a Solution to the Equation A=x^b mod p?

[Chu]

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.

-Chu

 

[Muzza]

Try solving x^2 = 2 (mod 3).

 

[Chu]

Try solving x^2 = 2 (mod 3).

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).

 

[matt grime]

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 \varphi(x), 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).