A correct proof of the heuristic GCD algorithm

2002/06/21 by Bernard Parisse, Parisse, Bernard
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #FOS: Computer and information sciences #G.4 #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC

paper · pdf · doi:10.48550/arxiv.cs/0206032

arxiv created 2002/06/21 · openalex publication_date 2002/06/21 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note, we fill a gap in the proof of the heuristic GCD in the multivariate case made by Char, Geddes and Gonnet (JSC 1989) and give some additionnal information on this method.

Related

• Simple algorithm for GCD of polynomials
• Around the gcd of the values of two polynomials
• The Accelerated Euclidean Algorithm
• The GPGCD Algorithm with the Bézout Matrix for Multiple Univariate Polynomials
• Approximate GCD in a Bernstein basis