Struct IntExtEuclidResult 

pub struct IntExtEuclidResult {
    pub gcd: i64,
    pub x: i64,
    pub y: i64,
}

Extended Euclidean algorithm result: gcd and Bezout coefficients.

Given integers a and b, stores gcd, x, y such that ax + by = gcd.

Fields

gcd: i64

The greatest common divisor (always non-negative).

x: i64

Bezout coefficient for a.

y: i64

Bezout coefficient for b.

Implementations

impl IntExtEuclidResult

pub fn compute(a: i64, b: i64) -> Self

Run the extended Euclidean algorithm on (a, b).

pub fn verify(&self, a: i64, b: i64) -> bool

Verify the Bezout identity: ax + by = gcd.

pub fn is_coprime(&self) -> bool

Returns true if a and b are coprime (gcd = 1).

pub fn modular_inverse(&self, _a: i64, b: i64) -> Option<i64>

Returns a modular inverse of a modulo b, if it exists.

Trait Implementations

impl Clone for IntExtEuclidResult

fn clone(&self) -> IntExtEuclidResult

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for IntExtEuclidResult

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

Formats the value using the given formatter.

impl PartialEq for IntExtEuclidResult

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for IntExtEuclidResult

impl StructuralPartialEq for IntExtEuclidResult