Recursive Elucidation of Polynomial Congruences Using Root-Finding Numerical Techniques

Abstract EN

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.