A NOVEL TECHNIQUE FOR THE ELUCIDATION OF LINEAR AND QUADRATIC CONGRUENCES

Abstract

Explicit iteration formulas were proposed for solving the equation ( ) 0 mod k f x p  , when f was the polynomial n ax b  . Speedy algorithms were formulated for lifting solutions of a polynomial congruence mod p , to polynomial congruence mod . kp 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 1 0 mod k xp and 2 1 mod k xp to ( ) 0 mod k f x p  , haggled a solution 2 x to 12 ( ) 0 mod kk f x p   with, 1 1 0 21 10 ( )( ) =, ( ) ( ) f x x x xx f x f x    where the inverse was computed using the Euclidean algorithm in the ring of integers modulo . kp 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.