Function ring_algorithm::extended_euclidian_algorithm [−][src]
pub fn extended_euclidian_algorithm<T>(x: T, y: T) -> (T, T, T) where
T: Sized + Zero + One,
for<'x> &'x T: EuclideanRingOperation<T>,
Expand description
extended euclidian algorithm
calcurate g (gcd(a, b)
) and x, y ( $g = ax + by
$ )
use ring_algorithm::{gcd, extended_euclidian_algorithm};
let a = 314;
let b = 271;
let (d, x, y) = extended_euclidian_algorithm::<i32>(a, b);
assert_eq!(d, gcd::<i32>(a, b));
assert_eq!(d, x * a + y * b);