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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Michael Kaminski, Note on probabilistic algorithms in integer and polynomial arithmetic, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.117-121, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806380]
• 3: MOENCK, R., AND BORODIN, A. Fast modular transforms via divisions. In Proceedings of the 13th Symposium on Switching and Automata Theory. IEEE, New York, 1972, pp. 90-96.
• 4: PATERSON, M. S., FISHER, M. J., AND MEYER, A.R. An improved overlap argument for on-fine multiplication. Complexity of Computation, vol. 7. SIAM-ACM PrOngs 1974, 97- l 13.
• 5: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• 6: SCH6NHAGE, A. Schnelle Multiplikation yon Polynomen fiber K6rpern der Charakteristik 2. Acta Inf. 7 (1977), 395-398.
• 7: Andrew C Yao, A lower bound to palindrome recognition by probabilistic Turing machines, Stanford University, Stanford, CA, 1977

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Design, Performance, Theory, Verification