Find in Library

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.