Newton's iteration and the sparse Hensel algorithm (Extended Abstract)

ABSTRACT

This paper presents an organization of the p-adic lifting (or Hensel) algorithm that differs from the organization previously presented by Zassenhaus [Zas69] and currently used in algebraic manipulation circles [Mos73, Yun74, Wan75, Mus75]. Our organization is somewhat more general than the earlier one and admits the improvements that yielded the “sparse modular” algorithm [Zip79] more easily than the Zassenhaus algorithm. From a pedagogical point of view, the relationship between Newton's iteration and the p-adic algorithms is clearer in our formulation than with the Zassenhaus algorithm.

REFERENCES

• 1: E. R. Berlekamp, "Factoring Polynomials over Large Finite Fields," Math. of Comp.24, 111 (1970), 713-735.
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
• 4: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 5: B. M. Trager and P. S.-H. Wang, "On Square-free Decomposition," SIAM Rev. of Comp.8, 3 (1979), 300-305.
• 6: P. S.-H. Wang and L. P. Rothschild, "Factoring Multivariate Polynomials over the Integers," Math. Comp.29, (1975), 935-950.
• 7: P. S.-H. Wang, "An Improved Multivariate Polynomial Factoring Algorithm," Math. Comp.32, (1978), 1215-1231.
• 8: D. Y. Y. Yun, The Hensel Lemma in Algebraic Manipulation, Ph. D. thesis, Dept. of Mathematics, Massachusetts Institute of Technology, (1974).
• 9: H.J. Zassenhaus, "On Hensel Factorization I," J. Number Theory1, (1969), 291-311.
• 10: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory