GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (Q1124635): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0747-7171(89)80004-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2077853647 / rank | |||
Normal rank |
Latest revision as of 11:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation |
scientific article |
Statements
GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (English)
0 references
1989
0 references
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.
0 references
heuristic methods
0 references
height of a polynomial
0 references
G.C.D. of multivariate polynomials
0 references