Recursive Elucidation of Polynomial Congruences Using Root‐Finding Numerical Techniques

In this paper we put forward a family of algorithms for lifting solutions of a polynomial congruence mod p to polynomial congruence mod pk. For this purpose, root‐finding iterative methods are employed for solving polynomial congruences of the form axn ≡ b(mod pk), k ≥ 1, where a, b, and n > 0 are integers which are not divisible by an odd prime p. It is shown that the algorithms suggested in this paper drastically reduce the complexity for such computations to a logarithmic scale. The efficacy of the proposed technique for solving negative exponent equations of the form ax−n ≡ b(mod pk) has also been addressed.