GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (Q1124635): Difference between revisions

Let a and b be two primitive univariate polynomials, and let g be their greatest common divisor. The height of a polynomial is the maximum of the absolute values of its coefficients: let n be greater than twice the heights of a,b, or any of their factors, and let \(h=(a(n),b(n))\). Expand h n-adically as \(h_ 0+h_ 1n+...+h_ kn^ k\) where \(-n/2<h_ i\leq n/2\); then if \(h(x)=h_ 0+h_ 1x+...+h_ kx^ k\) divides a and b it is in fact g. It is possible for h(x) to be Lg(x) where L is some integer greater than 1; if an increasing sequence of values of n is used then the probability of h(x) being g(x) increases to unity. The method can be extended to find the G.C.D. of multivariate polynomials.