Recursive elucidation of polynomial congruences using root-finding numerical techniques (Q1724425)

Summary: In this paper we put forward a family of algorithms for lifting solutions of a polynomial congruence \(\mathrm{mod} p\) to polynomial congruence \(\mod p^k\). For this purpose, root-finding iterative methods are employed for solving polynomial congruences of the form \(a x^n \equiv b\pmod{p^k}\), \(k \geq 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 \(a x^{- n} \equiv b\pmod{p^k}\) has also been addressed.