scientific article; zbMATH DE number 3984564

From MaRDI portal
Publication:3747717





[For the entire collection see Zbl 0591.00036.] In Lect. Notes Comput. Sci. 174, 285-296 (1984; Zbl 0584.68057) \textit{B. W. Char}, \textit{K. O. Geddes} and \textit{G. H. Gonnet} presented a heuristic algorithm for computing polynomial GCD's. The idea is to evaluate the two polynomials at a heuristic evaluation point, then to compute the integer GCD of the two integers and to reconstruct the GCD of the two polynomials from this integer GCD. In RAIRO, Inf. Théor. 12, 305-318 (1978; Zbl 0424.68025), \textit{G. Viry} already proposed a method of the same kind for factoring multivariate polynomials. This paper describes how to use this method in the lifting step of the multivariate factorization and proposes to use the Chinese Remainder Theorem to strengthen this method. The case of two variables is studied, but some proposals for extending to the general case are done. The problems arising in this method, i.e. the leading coefficient problem, the extraneous content problem, the choice of good evaluation points are solved. A comparison with the classical method is done showing that this new heuristic method is worthy of use. Moreover chips performing long integer arithmetic, available soon, increases its interest even more.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3747717)