GCD Algorithms

Multiple GCD (Greatest Common Divisor) algorithms for polynomials, optimized for different use cases including univariate, multivariate, and modular GCD using Zippel's algorithm.

📐

Mathematical Definition

For polynomials $f, g \in R[x]$ over a ring $R$ , the greatest common divisor $\gcd(f, g)$ is the monic polynomial $d$ of maximum degree such that:

d \mid f \quad \text{and} \quad d \mid g

and for any other polynomial $h$ where $h \mid f$ and $h \mid g$ , we have $h \mid d$ .

Euclidean Algorithm: For univariate polynomials over a field:

\gcd(f, g) = \begin{cases} f & \text{if } g = 0 \ \gcd(g, f \bmod g) & \text{otherwise} \end{cases}

Zippel's Modular Algorithm: 1. Extract content: $f = c_f \cdot f_p$ , $g = c_g \cdot g_p$ 2. Compute $\gcd(f_p, g_p)$ in $\mathbb{Z}_p[x]$ for prime $p$ 3. Use CRT to reconstruct $\gcd$ in $\mathbb{Z}[x]$

Code Examples

General-Purpose GCD

Use PolynomialGcdOps trait for automatic algorithm selection

use mathhook_core::core::polynomial::PolynomialGcdOps;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

// f = x^2 - 1 = (x-1)(x+1)
let f = expr!((x ^ 2) - 1);
// g = x^2 - 2x + 1 = (x-1)^2
let g = expr!((x ^ 2) - (2 * x) + 1);

// Compute GCD
let gcd = f.polynomial_gcd(&g).unwrap();
// gcd = x - 1

// Compute LCM
let lcm = f.polynomial_lcm(&g).unwrap();
// lcm = (x-1)^2(x+1)

Univariate Modular GCD with Cofactors

Returns GCD and cofactors for Bezout identity verification

use mathhook_core::core::polynomial::algorithms::zippel_gcd::modular_gcd_univariate;
use mathhook_core::{expr, symbol};

let x = symbol!(x);
let f = expr!((x ^ 2) - 1);
let g = expr!(x - 1);

// Returns (gcd, cofactor_f, cofactor_g)
let (gcd, cof_f, cof_g) = modular_gcd_univariate(&f, &g, &x).unwrap();

// Verify: f = gcd * cof_f, g = gcd * cof_g

Multivariate GCD with Zippel Algorithm

Compute GCD for polynomials in multiple variables

use mathhook_core::core::polynomial::algorithms::zippel_gcd::{
    multivariate_gcd_zippel,
    MultivariateGcdConfig
};
use mathhook_core::{expr, symbol};

let x = symbol!(x);
let y = symbol!(y);

// f = x*y, g = x*y + x
let f = expr!(x * y);
let g = expr!((x * y) + x);

let config = MultivariateGcdConfig::default();
let (gcd, _, _) = multivariate_gcd_zippel(&f, &g, &[x, y], config).unwrap();
// gcd = x

Content and Primitive Part Decomposition

Fundamental operation for GCD computation

use mathhook_core::core::polynomial::algorithms::zippel_gcd::{
    extract_content,
    primitive_part
};

let coeffs = vec![6, 12, 18];  // 6 + 12x + 18x^2

// Extract content (GCD of coefficients)
let content = extract_content(&coeffs);  // 6

// Get primitive part
let (cont, pp) = primitive_part(&coeffs);  // (6, [1, 2, 3])

🔗 Related Topics

Browse All Topics

Explore the full documentation library