Abstract:
Explicit iteration formulas were proposed for solving the equation f (x) mod pk , when f was the polynomial axn - b . Speedy algorithms were formulated for lifting solutions of a k polynomial congruence mod p , to polynomial congruence mod p . This was done reasonably fast, using proposed algorithm. Polynomial time was , which was about the best possible since the number of bits in the answer was in general proportional to The algorithm developed was instigated with an adaptation of secant method. For a polynomial , with initial solutions x0 mod pk1 and x1 mod pk2 to f (x)≡ 0 mod pk , haggled a solution x2 to f (x)≡0 mod pk1+k2 with, x2 = x1 = f (x1x11))\(-x1f-(xx00)) , where the inverse was computed using the Euclidean algorithm in the ring of integers modulo pk . The proposed technique endeavored to keep the elucidation consistently a little low to give advantage in finding the solution of congruences by means of explicit iteration techniques which proved quite fast in finding these solutions.
Page(s):
264-268
DOI:
DOI not available
Published:
Journal: Pakistan Journal of Science, Volume: 67, Issue: 3, Year: 2015
Keywords:
Polynomial modulo
,
Euclidean algorithm
,
Secant method
,
congruences