# A=x^b mod p, solvable?

1. Nov 14, 2004

### 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

2. Nov 15, 2004

### Muzza

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

3. Nov 15, 2004

### Chu

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

4. Nov 15, 2004

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook