Abstract
In this paper we have tried to demonstrate how sparse techniques can be used to increase the effectiveness of the modular algorithms of Brown and Collins. These techniques can be used for an extremely wide class of problems and can applied to a number of different algorithms including Hensel's lemma. We believe this work has finally laid to rest the bad zero problem.
Much of the work here is the direct result of discussion with Barry Trager and Joel Moses whose help we wish to acknowledge.
This work was supported, in part, by the United States Department of Energy under Contract Number E(11-1)-3070 and by the National Aeronautics and Space Administration under Grant NSG 1323.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Brown, “On Euclid's Algorithm and the Computation of Polynomial Greatest Divisors,” J. ACM 18, 4 (1971), 478–504.
MATHLAB Group, MACSYMA Reference Manual—version 9, Laboratory for Computer Science, Massachusetts Institute of Technology, (1978).
J. Moses and D. Y. Y. Yun, “The EZGCD algorithm,” Proceedings of ACM Nat. Conf. (1973), 159–166.
D. R. Musser, “Multivariate Polynomial Factoring,” J. ACM 22, 2 (1975), 291–308.
M. O. Rabin, “Probabilistic Algorithms,” Algorithms and Complexity—New Directions and Recent Results (J. F. Traub Ed.), Acad. Press, New York, (1976), 21–39.
R. Solovay and V. Strassen, “A Fast Monte-Carlo Test for Primality,” SIAM J. of Comp. 6, 1 (1977).
P. S.-H. Wang and L. P. Rothschild, “Factoring Multivariate Polynomials over the Integers,” Math. Comp. 29, (1975), 935–950.
P. S.-H. Wang, “An Improved Multivariate Polynomial Factoring Algorithm,” Math. Comp. 32, (1978), 1215–1231.
D. Y. Y. Yun, The Hensel Lemma in Algebraic Manipulation, Ph. D. thesis, Massachusetts Institute of Technology, (1974).
H. Zassenhaus, “On Hensel Factorization I,” J. Number Theory 1, (1969), 291–311.
R. E. Zippel, Probabilistic Algorithms for Sparse Polynomials, Ph. D. thesis, Massachusetts Institute of Technology, (1979).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1979 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zippel, R. (1979). Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (eds) Symbolic and Algebraic Computation. EUROSAM 1979. Lecture Notes in Computer Science, vol 72. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09519-5_73
Download citation
DOI: https://doi.org/10.1007/3-540-09519-5_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-09519-4
Online ISBN: 978-3-540-35128-3
eBook Packages: Springer Book Archive