Module multivariate_gcd 

Multivariate polynomial GCD computation using evaluation-interpolation

Implements the heuristic GCD algorithm (heugcd) from SymPy’s euclidtools.py. This approach avoids the infinite recursion issues of content-primitive factorization by using integer evaluation and polynomial interpolation.

Algorithm Overview (from [Liao95])

For multivariate polynomials f, g in Z[x₁, …, xₙ]:

1. Extract ground GCD (numeric content only - NON-RECURSIVE)
2. Evaluate both polynomials at integer point x₀ for main variable
3. Recursively compute GCD of resulting (n-1)-variate polynomials
4. Interpolate back to n-variate polynomial
5. Verify result by polynomial division
6. If verification fails, try new evaluation point (up to 6 attempts)

Mathematical Background

The key insight is that GCD computation can be reduced dimension by dimension:

• gcd(f(x,y), g(x,y)) at y=y₀ gives gcd(f(x,y₀), g(x,y₀))
• The GCD is then reconstructed via polynomial interpolation
• Verification ensures correctness (heuristic may fail, triggering retry)

References

• [Liao95] Liao, Q. “Factoring multivariate polynomials over algebraic number fields”
• SymPy polys/euclidtools.py: dmp_zz_heu_gcd, dup_zz_heu_gcd

Structs

HeuristicGCDFailed

Error type for heuristic GCD failures

Functions

multivariate_gcd

Compute GCD of multivariate polynomials using evaluation-interpolation

polynomial_evaluate_at

Evaluate polynomial at integer value for main variable

polynomial_interpolate

Interpolate polynomial from integer using symmetric representation