[][src]Function g2poly::extended_gcd

pub fn extended_gcd(a: G2Poly, b: G2Poly) -> (G2Poly, G2Poly, G2Poly)

Calculate the greatest common divisor with Bézout coefficients

Uses the extended euclidean algorithm to calculate the greatest common divisor of two polynomials. Also returns the Bézout coefficients x and y such that

gcd(a, b) == a * x + b * x

Example

let a = G2Poly(0b11011);
let b = G2Poly(0b100001);
let (gcd, x, y) = extended_gcd(a, b);
assert_eq!(gcd, G2Poly(0b11));
assert_eq!((a * x).to_poly() + (b * y).to_poly(), G2Poly(0b11));