Crate zippel_gcd 

Sparse multivariate polynomial GCD, cofactors and LCM over the rationals.

gcd() automatically tries Huang–Gao, Huang–Monagan, then Zippel. gcd_with_algorithm chooses the first algorithm in a documented fallback chain. cofactors and lcm provide the same choice through their _with_algorithm variants.

Call an algorithm directly to control recovery:

Function	Algorithm	Result
zippel()	Zippel modular GCD with LINZIP	Poly
huang_gao()	Huang–Gao separated Hensel lifting; asymptotic SOTA (2026)	Option<Poly>
huang_monagan()	Huang–Monagan prime substitution	Option<Poly>
hu_monagan()	Hu–Monagan GCD/cofactor interpolation	Option<Poly>
hu_monagan_bivariate()	Hu–Monagan with bivariate images	Option<Poly>

Named sparse methods return None when bounded recovery fails; they never switch to another recovery backend. They share integer normalization, CRT, exact certification and, for Hu–Monagan, Zippel content extraction. Every successful result has the normalization and zero conventions of gcd().

Huang–Gao’s 2026 paper is the state of the art in asymptotic sparse integer GCD complexity. This bounded, exactly certified implementation does not claim the paper’s full complexity bound or the fastest practical runtime for every input.

use polycore::{Order, Ring};
use zippel_gcd::{gcd, huang_gao, huang_monagan, hu_monagan,
                 hu_monagan_bivariate, zippel};

let ring = Ring::new(["x", "y"], Order::Lex);
let a = ring.parse("(x + y)*(x + 1)").unwrap();
let b = ring.parse("(x + y)*(y + 2)").unwrap();
let expected = ring.parse("x + y").unwrap();
assert_eq!(gcd(&a, &b), expected);       // Automatic recovery and fallback.
assert_eq!(zippel(&a, &b), expected);    // Explicit Zippel.
for algorithm in [huang_gao, huang_monagan, hu_monagan, hu_monagan_bivariate] {
    assert_eq!(algorithm(&a, &b).unwrap(), expected);
}

Structs

Frac

num / den with no common factor and den monic in its order. The constants Zero and One build have no variables and widen to whatever they meet, like Fp’s unbound modulus.

GcdReport

The top-level recovery chain actually tried, in order.

Enums

GcdAlgorithm

Preferred algorithm for gcd_with_algorithm, cofactors_with_algorithm and lcm_with_algorithm, including each variant’s documented fallback.

Functions

cofactors

GCD and cofactors (h, f / h, g / h) using the automatic Huang–Gao-first chain.

cofactors_with_algorithm

GCD and cofactors using a chosen first algorithm and its documented fallback chain.

gcd

Automatic GCD: Huang–Gao, then Huang–Monagan, then Zippel.

gcd_with_algorithm

GCD using a chosen first algorithm and its documented fallback chain.

gcd_with_report

Compute a GCD with the same fallback chain as gcd_with_algorithm, recording which attempts ran. This does not add a work limit to the Zippel fallback.

hu_monagan

Hu–Monagan GCD/cofactor interpolation using univariate images.

hu_monagan_bivariate

Hu–Monagan GCD/cofactor interpolation using bivariate images.

huang_gao

Huang–Gao GCD by derivative-aided separated Hensel lifting (asymptotic SOTA, 2026).

huang_monagan

Huang–Monagan GCD by integer prime substitution and valuation decoding.

lcm

LCM using the automatic Huang–Gao-first GCD chain.

lcm_with_algorithm

LCM using a chosen first algorithm and its documented fallback chain.

zippel

Zippel GCD by recursive modular interpolation with LINZIP support reuse.