Core API

Division, gcds, and resultants¶

The library implements division, gcds, resultants, and canonical rational functions. Every computational entry point accepts the caller's shared Budget. Coefficients support ZZ, QQ, and prime ModInt; rational functions use QQ.

Example¶

gcd.mojo Download

"""Compute and check a gcd and a rational-function cancellation."""
from polynomials import Budget, QQ, NoContext, MonomialOrder, SparsePoly, gcd, check_common_divisor, check_bezout, RationalFunction, check_cancellation

def main() raises:
    var budget = Budget()
    var order = MonomialOrder(MonomialOrder.LEX, [0], budget)
    var x = SparsePoly[QQ].variable(0, order, NoContext(), budget)
    var one = SparsePoly[QQ].constant(QQ.one(NoContext()), order, budget)
    var numerator = x.pow(2, budget).sub(one, budget)
    var denominator = x.sub(one, budget)
    var result = gcd(numerator, denominator, budget, certify_maximal=True)
    if result.gcd != denominator or not check_common_divisor(numerator, denominator, result, budget) or not check_bezout(numerator, denominator, result, budget):
        raise Error("gcd certificate failed")
    var reduced = RationalFunction.normalize(numerator, denominator, budget)
    if reduced[0].numerator != x.add(one, budget) or reduced[0].denominator != one or not check_cancellation(numerator, denominator, reduced[1], budget):
        raise Error("cancellation certificate failed")
    print("gcd and cancellation certificates checked")

Run from the repository root pixi run mojo run -I build docs/examples/gcd.mojo

Output

gcd and cancellation certificates checked

For \(f=x^2+1\) and \(g=x-1\), divmod returns the quotient \(x+1\) and the remainder \(2\). check_division checks the identity and the required degree condition against the original inputs:

tutorial_division.mojo Download

"""Divide two rational polynomials and check the quotient and remainder."""
from std.testing import assert_equal, assert_true
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, divmod, check_division


def main() raises:
    var work = Budget()
    var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
    var numerator = DensePoly[QQ].from_sparse(ring.parse("x^2 + 1", work), work, variable=Int64(0))
    var divisor = DensePoly[QQ].from_sparse(ring.parse("x - 1", work), work, variable=Int64(0))
    var result = divmod(numerator, divisor, work)
    var expected = DensePoly[QQ].from_sparse(ring.parse("x + 1", work), work, variable=Int64(0))
    assert_equal(result.quotient, expected)
    assert_equal(result.remainder.coefficients[0].value, Rational(2))
    assert_true(check_division(numerator, divisor, result, work))
    print("Quotient is x + 1:", result.quotient == expected)
    print("Remainder:", result.remainder.coefficients[0].value)

Run from the repository root pixi run mojo run -I build docs/examples/tutorial_division.mojo

Output

Quotient is x + 1: True
Remainder: 2

Representation and boundary conventions¶

Exact sparse division accepts KERNEL storage order, uses an internal LEX order for termination, and restores the original order. Ordered list division requires LEX, GRLEX, or GREVLEX.
subresultants returns the entire indexed family, including zero entries. Resultants use the Sylvester sign convention in E-1. A zero input gives zero; one nonzero constant gives the usual power. Two nonzero constants in the elimination variable raise DOMAIN: E-1 does not define this case, and the empty determinant 1 need not belong to their ideal over ZZ.
check_resultant_identity proves ideal membership; it does not prove that the supplied polynomial is the determinant. check_common_divisor proves divisibility; maximality additionally needs a Bézout or coprimality proof.
The gcd of two zeros is zero, with zero cofactors. A requested field proof can use the zero Bézout identity; no coprimality proof exists for two zero cofactors over ZZ.
Integer and rational coprimality certificates can carry a degree-preserving modular affine projection and a univariate Bézout identity. Integer witnesses also exclude scalar factors through an exact coefficient identity. The fallback coprimality nodes carry explicit content witnesses. Node references point backwards. A unit identity terminates a proof; other nodes prove the contents through coefficient gcd folds. The checker visits every referenced input pair, so sharing a node cannot substitute a proof of a different pair. It does not run gcd, division, or resultants.
Cancellation certificates establish the original guarded equality, including denominator scalar normalization. They do not assert equality at removed singularities or prove maximal cancellation on their own.

Division¶

`divmod`¶

def divmod[C: CoefficientField](f: DensePoly[C], g: DensePoly[C], mut budget: Budget) raises PolyError -> DivisionResult[C]

Divide univariate polynomials over a field.

Parameters.

C: The coefficient field.

Arguments.

f: The dividend.
g: The nonzero divisor in the same variable and ring.
budget: The shared work allowance.

Returns. The unique quotient and remainder of degree less than the divisor.

Raises.

PolyError: DOMAIN for invalid operands, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/division.mojo.

`pseudo_divmod`¶

def pseudo_divmod[C: CoefficientRing](f: DensePoly[C], g: DensePoly[C], mut budget: Budget) raises PolyError -> DivisionResult[C]

Divide after multiplying the dividend by the standard leading-coefficient power.

Parameters.

C: The coefficient integral domain.

Arguments.

f: The dividend.
g: The nonzero divisor in the same variable and ring.
budget: The shared work allowance.

Returns. Quotient and remainder for lc(g)**max(deg(f)-deg(g)+1, 0) times f.

Raises.

PolyError: DOMAIN for invalid operands, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/division.mojo.

`divide_exact`¶

def divide_exact[C: CoefficientRing](f: SparsePoly[C], g: SparsePoly[C], mut budget: Budget) raises PolyError -> Optional[SparsePoly[C]]

Return an exact quotient over the coefficient ring, or no value.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The dividend.
g: The nonzero divisor in the same ring and order.
budget: The shared work allowance.

Returns. The quotient if g divides f, otherwise None.

Raises.

PolyError: DOMAIN for invalid operands, UNSUPPORTED for another ring, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/division.mojo.

`divide_exact_dense`¶

def divide_exact_dense[C: CoefficientRing](f: DensePoly[C], g: DensePoly[C], mut budget: Budget) raises PolyError -> Optional[DensePoly[C]]

Return the exact dense quotient over the coefficient ring, or no value; the dense counterpart of divide_exact.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The dividend.
g: The nonzero divisor in the same variable and ring.
budget: The shared work allowance.

Returns. The quotient if g divides f, otherwise None.

Raises.

PolyError: DOMAIN for invalid operands, UNSUPPORTED for another ring, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/division.mojo.

`divide_by_list`¶

def divide_by_list[C: CoefficientField](f: SparsePoly[C], divisors: List[SparsePoly[C]], mut budget: Budget) raises PolyError -> ListDivision[C]

Reduce by nonzero divisors in the supplied order under a monomial order.

Parameters.

C: The coefficient field.

Arguments.

f: The dividend in LEX, GRLEX, or GREVLEX order.
divisors: Nonzero divisors in the same ring and order.
budget: The shared work allowance.

Returns. Quotients and a remainder with no term divisible by a divisor's leading monomial.

Raises.

PolyError: DOMAIN for zero divisors, mixed rings/orders, or KERNEL order; LIMIT or CAPACITY on work limits.

Defined in src/polynomials/division.mojo.

Primes and CRT¶

`prime`¶

def prime(i: Int, mut budget: Budget) raises PolyError -> UInt64

Return a cached prime from the fixed descending sequence below 2**62.

Every call charges the same fixed work, whatever the cache holds, so a computation is charged the same however often it runs.

Arguments.

i: The zero-based sequence index.
budget: The shared work allowance.

Returns. The i-th prime, independent of cache state and thread scheduling.

Raises.

PolyError: DOMAIN for a negative index, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/primes.mojo.

`crt`¶

def crt(residues: List[UInt64], primes: List[UInt64], mut budget: Budget) raises PolyError -> Integer

Combine prime residues into the unique symmetric representative.

Arguments.

residues: Residues, reduced modulo the corresponding primes.
primes: Distinct prime moduli strictly below 2**62.
budget: The shared work allowance.

Returns. The representative in (-M/2, M/2], where M is the product of the primes.

Raises.

PolyError: DOMAIN for empty, mismatched, composite, or repeated moduli; LIMIT or CAPACITY on work limits.

Defined in src/polynomials/primes.mojo.

Gcds and content¶

`content`¶

def content[C: CoefficientRing](p: SparsePoly[C], main_variable: Int64, mut budget: Budget) raises PolyError -> SparsePoly[C]

Compute the normalized gcd of the coefficients in one variable.

Parameters.

C: ZZ or a coefficient field.

Arguments.

p: The polynomial.
main_variable: The variable separated from its coefficient ring.
budget: The shared work allowance.

Returns. The content in the remaining variables, or zero for zero input.

Raises.

PolyError: LIMIT or CAPACITY on work limits, UNSUPPORTED for another ring.

Defined in src/polynomials/gcd.mojo.

`primitive_part`¶

def primitive_part[C: CoefficientRing](p: SparsePoly[C], main_variable: Int64, mut budget: Budget) raises PolyError -> SparsePoly[C]

Divide by the content in the chosen variable.

Parameters.

C: ZZ or a coefficient field.

Arguments.

p: The polynomial.
main_variable: The variable separated from its coefficient ring.
budget: The shared work allowance.

Returns. The primitive part, or zero for zero input.

Raises.

PolyError: LIMIT or CAPACITY on work limits, UNSUPPORTED for another ring.

Defined in src/polynomials/gcd.mojo.

`gcd`¶

def gcd[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], mut budget: Budget, certify_maximal: Bool = False) raises PolyError -> GcdResult[C]

Compute a normalized gcd, its cofactors, and optionally maximality evidence.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
h: The second polynomial in the same ring and order.
budget: The shared work allowance.
certify_maximal: Whether to produce a Bézout or coprimality proof.

Returns. The positive-leading ZZ or monic field gcd and its certificates.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/gcd.mojo.

`gcd_value`¶

def gcd_value[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], mut budget: Budget) raises PolyError -> SparsePoly[C]

Compute the normalized gcd alone, without cofactors or evidence.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
h: The second polynomial in the same ring and order.
budget: The shared work allowance.

Returns. The positive-leading ZZ or monic field gcd, equal to gcd(f, h).gcd.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/gcd.mojo.

`extended_gcd`¶

def extended_gcd[C: CoefficientField](f: DensePoly[C], h: DensePoly[C], mut budget: Budget) raises PolyError -> GcdResult[C]

Compute a monic univariate gcd with Bézout multipliers.

Parameters.

C: The coefficient field.

Arguments.

f: The first polynomial.
h: The second polynomial in the same variable and ring.
budget: The shared work allowance.

Returns. A gcd, its cofactors, and G-C2 evidence in KERNEL storage order.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/gcd.mojo.

`coprimality_certificate`¶

def coprimality_certificate[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], mut budget: Budget) raises PolyError -> Optional[CoprimalityCertificate[C]]

Prove coprimality by unit identities or elimination with content witnesses.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
h: The second polynomial in the same ring and order.
budget: The shared work allowance.

Returns. A modular projection witness or a deterministic G-C3 proof arena, or None when the inputs share a nonunit factor.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/gcd.mojo.

Elimination¶

`resultant`¶

def resultant[C: CoefficientRing](f: SparsePoly[C], g: SparsePoly[C], variable: Int64, mut budget: Budget) raises PolyError -> ResultantResult[C]

Compute the resultant and multipliers proving its ideal membership.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
g: The second polynomial in the same ring and order.
variable: The elimination variable.
budget: The shared work allowance.

Returns. The Sylvester-convention resultant and its cofactor identity.

Raises.

PolyError: DOMAIN for incompatible inputs or two nonzero constants in the variable, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/resultant.mojo.

`resultant_value`¶

def resultant_value[C: CoefficientRing](f: SparsePoly[C], g: SparsePoly[C], variable: Int64, mut budget: Budget) raises PolyError -> SparsePoly[C]

Compute the resultant alone, without the multipliers of its identity.

Univariate integer inputs use multi-modular reconstruction up to the Hadamard bound, univariate inputs over odd prime fields a word-size Euclidean recurrence, multivariate integer and odd prime field inputs dense evaluation and interpolation when the specialization grid is small enough, and all others the subresultant PRS of resultant without cofactor propagation.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
g: The second polynomial in the same ring and order.
variable: The elimination variable.
budget: The shared work allowance.

Returns. The Sylvester-convention resultant, equal to resultant(f, g, variable).resultant.

Raises.

PolyError: DOMAIN for incompatible inputs or two nonzero constants in the variable, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/resultant.mojo.

`subresultants`¶

def subresultants[C: CoefficientRing](f: SparsePoly[C], g: SparsePoly[C], variable: Int64, mut budget: Budget) raises PolyError -> List[SparsePoly[C]]

Compute S_j for every index below the smaller degree, including zeros.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first polynomial.
g: The second polynomial in the same ring and order.
variable: The elimination variable.
budget: The shared work allowance.

Returns. The indexed subresultants S_0 through S_(min(deg(f),deg(g))-1).

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/resultant.mojo.

Rational functions¶

`RationalFunction`¶

@fieldwise_init
struct RationalFunction(Copyable, Movable, Equatable, Writable)

A reduced polynomial fraction with a monic nonzero denominator.

Defined in src/polynomials/fractions.mojo.

Field	Type
`numerator`	`SparsePoly[QQ]`	The canonical numerator; zero has denominator one.
`denominator`	`SparsePoly[QQ]`	The monic denominator, coprime to the numerator.

`RationalFunction.normalize`¶

@staticmethod
def normalize(p: SparsePoly[QQ], q: SparsePoly[QQ], mut budget: Budget) raises PolyError -> Tuple[Self, CancellationCertificate]

Reduce a polynomial fraction and produce its cancellation identity.

Arguments.

p: The numerator.
q: The nonzero denominator in the same ring and order.
budget: The shared work allowance.

Returns. The unique normalized fraction and its cancellation certificate.

Raises.

PolyError: DOMAIN for a zero denominator or incompatible inputs, LIMIT or CAPACITY on work limits.

`RationalFunction.add`¶

def add(self, other: Self, mut budget: Budget) raises PolyError -> Self

Compute a normalized sum.

Arguments.

other: The second fraction in the same ring and order.
budget: The shared work allowance.

Returns. The canonical sum.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

`RationalFunction.sub`¶

def sub(self, other: Self, mut budget: Budget) raises PolyError -> Self

Compute a normalized difference.

Arguments.

other: The subtracted fraction in the same ring and order.
budget: The shared work allowance.

Returns. The canonical difference.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

`RationalFunction.mul`¶

def mul(self, other: Self, mut budget: Budget) raises PolyError -> Self

Compute a normalized product.

Arguments.

other: The second fraction in the same ring and order.
budget: The shared work allowance.

Returns. The canonical product.

Raises.

PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.

`RationalFunction.div`¶

def div(self, other: Self, mut budget: Budget) raises PolyError -> Self

Compute a normalized quotient by a nonzero fraction.

Arguments.

other: The divisor in the same ring and order.
budget: The shared work allowance.

Returns. The canonical quotient.

Raises.

PolyError: DOMAIN for a zero divisor or incompatible inputs, LIMIT or CAPACITY on work limits.

`RationalFunction.neg`¶

def neg(self, mut budget: Budget) raises PolyError -> Self

Negate the fraction while retaining its canonical denominator.

Arguments.

budget: The shared work allowance.

Returns. The canonical additive inverse.

Raises.

PolyError: LIMIT or CAPACITY on work limits.

Certificates¶

`DivisionResult`¶

@fieldwise_init
struct DivisionResult[C: CoefficientRing](Copyable, Movable, Writable)

A dense quotient and remainder.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`quotient`	`DensePoly[Self.C]`	The quotient polynomial.
`remainder`	`DensePoly[Self.C]`	The remainder polynomial.

`ListDivision`¶

@fieldwise_init
struct ListDivision[C: CoefficientRing](Copyable, Movable, Writable)

Quotients in divisor order and the unreduced remainder.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`quotients`	`List[SparsePoly[Self.C]]`	One quotient for each supplied divisor.
`remainder`	`SparsePoly[Self.C]`	The remainder after the ordered reductions.

`ContentGcdStep`¶

@fieldwise_init
struct ContentGcdStep[C: CoefficientRing](Copyable, Movable, Writable)

A gcd fold step proved by divisibility and cofactor coprimality.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`gcd`	`SparsePoly[Self.C]`	The gcd of the preceding accumulator and the next coefficient.
`cofactors`	`Tuple[SparsePoly[Self.C], SparsePoly[Self.C]]`	The two quotient witnesses.
`coprimality_node`	`Optional[Int]`	An earlier node proving the quotient pair coprime, absent only for two zeros.

`CoprimalityNode`¶

@fieldwise_init
struct CoprimalityNode[C: CoefficientRing](Copyable, Movable, Writable)

A unit identity or a content-and-resultant proof node.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`variable`	`Int64`	The eliminated variable for a nonterminal node.
`u`	`SparsePoly[Self.C]`	The multiplier of the left input.
`v`	`SparsePoly[Self.C]`	The multiplier of the right input.
`s`	`SparsePoly[Self.C]`	The nonzero combination uf+vh, free of the eliminated variable.
`left_content_steps`	`List[ContentGcdStep[Self.C]]`	The coefficient gcd fold for the left input, in increasing degree.
`right_content_steps`	`List[ContentGcdStep[Self.C]]`	The coefficient gcd fold for the right input, in increasing degree.
`contents_node`	`Optional[Int]`	An earlier node proving the two final contents coprime.

`CoprimalityCertificate`¶

struct CoprimalityCertificate[C: CoefficientRing](Copyable, Movable, Writable)

A modular projection witness or a finite arena of coprimality nodes.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`nodes`	`List[CoprimalityNode[Self.C]]`	Nodes whose references must point strictly backwards.
`root`	`Int`	The root node, or -1 for a modular witness with an empty arena.
`modular`	`Optional[ModularCoprimalityCertificate]`	The optional degree-preserving modular coprimality witness.

`CoprimalityCertificate.init`¶

def __init__(out self, var nodes: List[CoprimalityNode[Self.C]], root: Int, var modular: Optional[ModularCoprimalityCertificate] = None)

Retain one proof variant; independent checking enforces its shape.

Arguments.

nodes: The dependency-ordered legacy arena, empty for modular evidence.
root: The arena root or -1 for modular evidence.
modular: An optional modular witness; absent for a legacy arena.

`ModularCoprimalityCertificate`¶

@fieldwise_init
struct ModularCoprimalityCertificate(Copyable, Movable, Writable)

A degree-preserving affine projection and two exact coprimality identities.

The modular identity excludes nonconstant factors. For integer inputs the coefficient identity excludes shared integer factors; rational inputs have empty integer witness lists. Coefficients use ordinary reduced residues.

Defined in src/polynomials/_modular_coprimality.mojo.

Field	Type
`prime`	`UInt64`	One of the fixed admitted primes below 2**30.
`variables`	`List[Int64]`	All occurring variables, in increasing identifier order.
`slopes`	`List[UInt64]`	The coefficient of t in each variable's affine substitution.
`offsets`	`List[UInt64]`	The constant term in each variable's affine substitution.
`u`	`List[UInt64]`	The left univariate Bezout multiplier, in increasing degree.
`v`	`List[UInt64]`	The right univariate Bezout multiplier, in increasing degree.
`integer_indices`	`List[Int]`	Increasing indices into the concatenated input coefficient lists.
`integer_weights`	`List[ZZ]`	Nonzero integer weights whose selected coefficient sum is exactly one.

`GcdResult`¶

@fieldwise_init
struct GcdResult[C: CoefficientRing](Copyable, Movable, Writable)

A normalized gcd and optional evidence of maximality.

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`gcd`	`SparsePoly[Self.C]`	The normalized greatest common divisor.
`cofactors`	`Tuple[SparsePoly[Self.C], SparsePoly[Self.C]]`	The quotients of the inputs by the gcd (G-C1).
`bezout`	`Optional[Tuple[SparsePoly[Self.C], SparsePoly[Self.C]]]`	Bézout multipliers when available (G-C2).
`coprimality`	`Optional[CoprimalityCertificate[Self.C]]`	A proof that the cofactors are coprime (G-C3), when requested.

`ResultantResult`¶

@fieldwise_init
struct ResultantResult[C: CoefficientRing](Copyable, Movable, Writable)

An elimination polynomial with its ideal-membership identity (E-C1).

Parameters.

C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field	Type
`resultant`	`SparsePoly[Self.C]`	The resultant in the remaining variables.
`cofactors`	`Tuple[SparsePoly[Self.C], SparsePoly[Self.C]]`	Multipliers u and v satisfying uf+vg=resultant.

`CancellationCertificate`¶

@fieldwise_init
struct CancellationCertificate(Copyable, Movable, Writable)

The common factor and normalized quotient witnesses for cancellation.

Defined in src/polynomials/certificates.mojo.

Field	Type
`common`	`SparsePoly[QQ]`	The cancelled polynomial, including denominator scalar normalization.
`cofactors`	`Tuple[SparsePoly[QQ], SparsePoly[QQ]]`	The resulting numerator and denominator.

`check_division`¶

def check_division[C: CoefficientRing](f: DensePoly[C], g: DensePoly[C], result: DivisionResult[C], mut budget: Budget) raises PolyError -> Bool

Check the ordinary division identity and strict remainder degree bound.

Parameters.

C: The coefficient ring.

Arguments.

f: The dividend.
g: The divisor.
result: The proposed quotient and remainder.
budget: The shared work allowance.

Returns. Whether the data prove V-C1; pseudo-division requires a scaled dividend.

Raises.

PolyError: DOMAIN for incompatible representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_list_division`¶

def check_list_division[C: CoefficientRing](f: SparsePoly[C], divisors: List[SparsePoly[C]], result: ListDivision[C], mut budget: Budget) raises PolyError -> Bool

Check the ideal-membership identity of division by a list.

Parameters.

C: The coefficient ring.

Arguments.

f: The dividend.
divisors: The ordered divisor list.
result: The proposed quotients and remainder.
budget: The shared work allowance.

Returns. Whether the data prove V-C2, without claiming a unique remainder.

Raises.

PolyError: DOMAIN for incompatible representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_common_divisor`¶

def check_common_divisor[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], result: GcdResult[C], mut budget: Budget) raises PolyError -> Bool

Check both common-divisor identities without claiming maximality.

Parameters.

C: The coefficient ring.

Arguments.

f: The first input.
h: The second input.
result: The proposed gcd and cofactors.
budget: The shared work allowance.

Returns. Whether f=gcda and h=gcdb (G-C1).

Raises.

PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_bezout`¶

def check_bezout[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], result: GcdResult[C], mut budget: Budget) raises PolyError -> Bool

Check common divisibility and the Bézout identity (G-C2).

Parameters.

C: The coefficient ring.

Arguments.

f: The first input.
h: The second input.
result: The proposed gcd and Bézout multipliers.
budget: The shared work allowance.

Returns. Whether the available evidence proves both identities.

Raises.

PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_coprimality`¶

def check_coprimality[C: CoefficientRing](f: SparsePoly[C], h: SparsePoly[C], certificate: CoprimalityCertificate[C], mut budget: Budget) raises PolyError -> Bool

Check modular witnesses or content/elimination identities without rerunning gcd.

Parameters.

C: ZZ or a coefficient field.

Arguments.

f: The first input.
h: The second input.
certificate: The proposed topologically ordered proof arena.
budget: The shared work allowance.

Returns. Whether the reachable proof establishes coprimality of these inputs.

Raises.

PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_resultant_identity`¶

def check_resultant_identity[C: CoefficientRing](f: SparsePoly[C], g: SparsePoly[C], result: ResultantResult[C], mut budget: Budget) raises PolyError -> Bool

Check the ideal-membership identity supplied with a resultant (E-C1).

Parameters.

C: The coefficient ring.

Arguments.

f: The first input.
g: The second input.
result: The proposed elimination polynomial and multipliers.
budget: The shared work allowance.

Returns. Whether uf+vg equals the proposed elimination polynomial.

Raises.

PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

`check_cancellation`¶

def check_cancellation(p: SparsePoly[QQ], q: SparsePoly[QQ], certificate: CancellationCertificate, mut budget: Budget) raises PolyError -> Bool

Check that cancellation preserves the rational function where q is nonzero.

Arguments.

p: The original numerator.
q: The original nonzero denominator.
certificate: The proposed common factor and quotients.
budget: The shared work allowance.

Returns. Whether p=commona and q=commonb with q nonzero (F-C1).

Raises.

PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

Division, gcds, and resultants¶

Example¶

Representation and boundary conventions¶

Division¶

divmod¶

pseudo_divmod¶

divide_exact¶

divide_exact_dense¶

divide_by_list¶

Primes and CRT¶

prime¶

crt¶

Gcds and content¶

content¶

primitive_part¶

gcd¶

gcd_value¶

extended_gcd¶

coprimality_certificate¶

Elimination¶

resultant¶

resultant_value¶

subresultants¶

Rational functions¶

RationalFunction¶

RationalFunction.normalize¶

RationalFunction.add¶

RationalFunction.sub¶

RationalFunction.mul¶

RationalFunction.div¶

RationalFunction.neg¶

Certificates¶

DivisionResult¶

ListDivision¶

ContentGcdStep¶

CoprimalityNode¶

CoprimalityCertificate¶

CoprimalityCertificate.__init__¶

ModularCoprimalityCertificate¶

GcdResult¶

ResultantResult¶

CancellationCertificate¶

check_division¶

check_list_division¶

check_common_divisor¶

check_bezout¶

check_coprimality¶

check_resultant_identity¶

check_cancellation¶

`divmod`¶

`pseudo_divmod`¶

`divide_exact`¶

`divide_exact_dense`¶

`divide_by_list`¶

`prime`¶

`crt`¶

`content`¶

`primitive_part`¶

`gcd`¶

`gcd_value`¶

`extended_gcd`¶

`coprimality_certificate`¶

`resultant`¶

`resultant_value`¶

`subresultants`¶

`RationalFunction`¶

`RationalFunction.normalize`¶

`RationalFunction.add`¶

`RationalFunction.sub`¶

`RationalFunction.mul`¶

`RationalFunction.div`¶

`RationalFunction.neg`¶

`DivisionResult`¶

`ListDivision`¶

`ContentGcdStep`¶

`CoprimalityNode`¶

`CoprimalityCertificate`¶

`CoprimalityCertificate.init`¶

`ModularCoprimalityCertificate`¶

`GcdResult`¶

`ResultantResult`¶

`CancellationCertificate`¶

`check_division`¶

`check_list_division`¶

`check_common_divisor`¶

`check_bezout`¶

`check_coprimality`¶

`check_resultant_identity`¶

`check_cancellation`¶