Add optimized binary extended gcd algorithm

rust-num / num-integer

Integer trait and functions for Rust

Apache License 2.0

180 stars 48 forks source link

Open unseddd opened 3 years ago

unseddd commented 3 years ago

Optimized to use cheap shifts and adds rather than multiplications and divisions for finding the greated common divisor and Bezout coefficients.

unseddd commented 3 years ago

Much appreciation to @cuviper for their help/discussion about the impl on Zulip.