Enum GcdAlgorithm 

pub enum GcdAlgorithm {
    HuangGao,
    HuangMonagan,
    HuMonagan,
    HuMonaganBivariate,
    Zippel,
}

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

To run a single recovery backend without fallback, use its named function: zippel(), huang_gao(), huang_monagan(), hu_monagan() or hu_monagan_bivariate().

Variants

HuangGao

Huang–Gao separated Hensel lifting (asymptotic SOTA, 2026), then Huang–Monagan, then Zippel. See huang_gao() for the paper and scope.

HuangMonagan

Integer prime substitution and valuation decoding, then Zippel.

Follows Algorithms 1 and 6 of Huang–Monagan, https://arxiv.org/abs/2609.10626v1, using the practical modular univariate GCD and small-prime sampling of Section 6. Trial division by the chosen primes recovers exponents; exact division and degree certificates reject unlucky substitutions.

Tries two substitutions per term-bound guess from 2 through 64. Images are limited to degree 65,536, estimated coefficient size 65,536 bits and 64 million coefficient bits in total. Degree certificates use at most four million coefficient slots; each univariate CRT uses at most 256 primes. Exhausting a budget invokes the Zippel fallback.

HuMonagan

Hu–Monagan geometric interpolation of a GCD and cofactor together. Uses univariate images, smooth-subgroup discrete logarithms and Ben-Or/Tiwari recovery, then exact certification and a Zippel fallback.

Both Hu–Monagan variants allow three orbits of at most 256 samples per prime, 256 CRT primes, a 48-bit exponent box, retained degrees up to 4,096 and two million coefficient slots per interpolant. Exact modular division permits 100,000 term reductions. Exceeding a budget falls back.

HuMonaganBivariate

Hu–Monagan simultaneous GCD/cofactor recovery using bivariate images. Keeps two variables symbolic; otherwise uses the same recovery and budgets as Self::HuMonagan. In one variable, uses univariate images.

Zippel

Recursive modular interpolation with LINZIP support reuse.

Trait Implementations

impl Clone for GcdAlgorithm

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Copy for GcdAlgorithm

impl Debug for GcdAlgorithm

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for GcdAlgorithm

fn default() -> Self

Returns the “default value” for a type.

impl Eq for GcdAlgorithm

impl PartialEq for GcdAlgorithm

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for GcdAlgorithm