Skip to content

root · BezoutIdentity

8 accepted declarations. Python and Rust forms, contracts, evidence, failure boundaries, and checked usages are kept together below.

Worked example

The complete checked program Compute and verify a Bézout certificate over the integers uses this API directly.

# SPDX-License-Identifier: MIT
# Copyright (c) 2026 Benjamin Antieau and Deven Manam
"""Compute and verify a Bézout certificate over the integers."""

from noether import Z


def main() -> None:
    identity = Z.extended_gcd(987_654_321, 123_456_789)
    identity.verify(Z, 987_654_321, 123_456_789)
    assert (
        identity.coefficient_a * 987_654_321 + identity.coefficient_b * 123_456_789 == identity.gcd
    )
    print(identity)


if __name__ == "__main__":
    main()

Run it with .venv/bin/python examples/01_bezout_certificates.py.

BezoutIdentity

A typed extended-gcd result with a directly checkable identity.

class BezoutIdentity

noether::BezoutIdentity · Direct Rust declaration

pub struct BezoutIdentity<R: Ring> { pub gcd: R::Element, pub coefficient_a: R::Element, pub coefficient_b: R::Element, }
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: validation/unit/test_bezout_facade.py:10 · validation/unit/test_bezout_facade.py:24 · validation/unit/test_bezout_facade.py:25 · validation/unit/test_bezout_facade.py:32 · validation/unit/test_bezout_facade.py:47 · validation/unit/test_bezout_facade.py:55

BezoutIdentity.coefficient_a

Coefficient multiplying the first input.

(self) -> _Element

noether::root::BezoutIdentity · Python projection

Python projection convenience over this Rust mathematical type
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: examples/01_bezout_certificates.py:12 · validation/unit/test_bezout_facade.py:28 · validation/unit/test_bezout_facade.py:45

BezoutIdentity.coefficient_b

Coefficient multiplying the second input.

(self) -> _Element

noether::root::BezoutIdentity · Python projection

Python projection convenience over this Rust mathematical type
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: examples/01_bezout_certificates.py:12 · validation/unit/test_bezout_facade.py:28 · validation/unit/test_bezout_facade.py:45

BezoutIdentity.from_json

Restore a witness with a checked semantic and coefficient-context ID.

Detailed contract

Restore a witness whose element type has a canonical text parser. Deserialization validates the type and coefficient-context identities. The relation to particular inputs is checked separately by Self::verify.

(cls, value: str) -> BezoutIdentity[int] | BezoutIdentity[_Fraction]

noether::root::BezoutIdentity::from_json · Direct Rust declaration

pub fn from_json(value: &str) -> Result<Self, NoetherError>
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: validation/unit/category/test_category.py:14 · validation/unit/combin/test_acceptance_workload.py:65 · validation/unit/combin/test_acceptance_workload.py:86 · validation/unit/combin/test_graph_facade.py:106 · validation/unit/combin/test_graph_facade.py:25 · validation/unit/combinatorics/test_kashiwara_crystal.py:32

BezoutIdentity.gcd

Canonically normalized greatest common divisor.

(self) -> _Element

noether::root::BezoutIdentity · Python projection

Python projection convenience over this Rust mathematical type
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: examples/01_bezout_certificates.py:12 · validation/unit/commalg/test_polynomial_facade.py:385 · validation/unit/commalg/test_polynomial_facade.py:452 · validation/unit/commalg/test_polynomial_facade.py:469 · validation/unit/commalg/test_polynomial_facade.py:474 · validation/unit/commalg/test_polynomial_facade.py:498

BezoutIdentity.ring

Coefficient context in which the identity is stated.

(self) -> IntegerRing | RationalField

noether::root::BezoutIdentity · Python projection

Python projection convenience over this Rust mathematical type
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: examples/11_qadic_witt_vectors.py:3 · examples/13_chinese_remainder_theorem.py:10 · examples/13_chinese_remainder_theorem.py:12 · examples/13_chinese_remainder_theorem.py:9 · examples/14_weighted_polynomials.py:10 · examples/14_weighted_polynomials.py:11

BezoutIdentity.to_json

Canonical JSON representation shared with the Rust facade.

Detailed contract

Serialize this witness using its semantic and coefficient-context IDs.

(self) -> str

noether::root::BezoutIdentity::to_json · Direct Rust declaration

pub fn to_json(&self) -> Result<String, NoetherError>
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: validation/unit/category/test_category.py:14 · validation/unit/category/test_category.py:15 · validation/unit/combin/test_acceptance_workload.py:30 · validation/unit/combin/test_acceptance_workload.py:65 · validation/unit/combin/test_acceptance_workload.py:86 · validation/unit/combin/test_graph_facade.py:106

BezoutIdentity.verify

Verify the normalized gcd and Bézout relation against the two inputs.

Detailed contract

Verify the normalized gcd and Bézout relation for inputs a and b.

(self, ring: Ring[_Element], left: _Element, right: _Element) -> None

noether::root::BezoutIdentity::verify · Direct Rust declaration

pub fn verify( &self, ring: &R, a: &R::Element, b: &R::Element, ) -> Result<(), VerificationError>
Contract Value
Guarantee checked deterministic result
Determinism deterministic
Availability default CPU build
Domain implementation crates noether, flint-core
GIL attached / bounded
Semantic ID noether/root/BezoutIdentity@1

Executable usage: examples/01_bezout_certificates.py:10 · examples/01_bezout_certificates.py:3 · examples/03_exact_linear_systems.py:13 · examples/03_exact_linear_systems.py:3 · examples/04_smith_normal_form.py:12 · examples/06_shortest_lattice_vectors.py:12