RustCrypto/crypto-bigint

Implement `safegcd-bounds`

tarcieri opened this issue · 0 comments

This is a corresponding tracking issue for this TODO: https://github.com/RustCrypto/crypto-bigint/blob/ae30093/src/modular/safegcd.rs#L341

The bounds we currently implement for Bernstein-Yang are the ones described in the paper, which proves that the algorithm will always converge within the prescribed bounds. However, the bounds are overly conservative and not optimal:

https://github.com/sipa/safegcd-bounds

There is both an improved bounds calculation we can use, as well as an improved divsteps algorithm (hddivsteps) which itself has improved bounds over the original divsteps algorithm.