Function g2poly::extended_gcd
source · Expand description
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));