A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor

Abstract

An algorithm is presented to compute the residue of a polynomial over a finite field of degree n modulo a polynomial of degree O (log n ) in O ( n ) algebraic operations. This algorithm can be implemented on a Turing machine. The implementation is based on Turing machine procedure that divides a polynomial of degree n by a sparse polynomial with k nonzero coefficients in O ( kn ) steps. This algorithm can be adapted to compute the residue of a number of length n modulo a number of length O (log n ) in O ( n ) bit operations.