# Find b from a = b^x

1. Aug 17, 2009

### vanvincent

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. Aug 17, 2009

### GPPaille

$$(a)^{\frac{1}{x}}=(b^x)^{\frac{1}{x}}$$
$$a^{\frac{1}{x}}=b$$

3. Aug 18, 2009

### vanvincent

4. Aug 18, 2009

### Dragonfall

Use Euler's theorem.

5. Aug 18, 2009

### vanvincent

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!

6. Aug 18, 2009

### Dragonfall

I'm sorry, I think I'm mistaken with Euler's theorem.

If $$a\equiv b^n (\mod n^2)$$ then $$|a-kn^2|=b^n$$ 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.

7. Aug 25, 2009

### Dragonfall

What I said above is an exponential algorithm, so please ignore it.

8. Sep 25, 2009

### bpet

Is there necessarily a unique solution, e.g. 0^6 = 6^6 mod 36