Find b from a=b^x mod x^2 given a,x,p,q

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

 

[GPPaille]

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

 

[vanvincent]

in modular arithmetic please!

 

[Dragonfall]

Use Euler's theorem.

 

[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!

 

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

 

[Dragonfall]

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

 

[bpet]

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