fast_poly_eea

feanor_math::algorithms::poly_gcd::finite

Function fast_poly_eea 

Source 
pub fn fast_poly_eea<P, Controller>(
    poly_ring: P,
    lhs: El<P>,
    rhs: El<P>,
    controller: Controller,
) -> (El<P>, El<P>, El<P>)
where
    P: RingStore + Copy,
    P::Type: PolyRing + EuclideanRing,
    <<P::Type as RingExtension>::BaseRing as RingStore>::Type: Field,
    Controller: ComputationController,
Available on crate feature unstable-enable only.
Expand description

Computes a Bezout identity for polynomials, using a fast divide-and-conquer polynomial gcd algorithm. Unless you are implementing crate::pid::PrincipalIdealRing for a custom type, you should use crate::pid::PrincipalIdealRing::extended_ideal_gen() to get a Bezout identity instead.

A Bezout identity is exactly as specified by crate::pid::PrincipalIdealRing::extended_ideal_gen(), i.e. s, t, d such that d is the gcd of lhs and rhs, and d = lhs * s + rhs * t. Note that this algorithm does not try to avoid coefficient growth, and thus is only fast over finite fields. Furthermore, it will fall back to a slightly less efficient variant of the standard Euclidean algorithm on small inputs.

ยงAvailability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.