4 ms·
The safegcd implementation in libsecp256k1 explained
- nullc 5y agoAnd this covers the hull-bound technique used to prove the worst case runtimes of this (and related) algorithm(s): https://github.com/sipa/safegcd-bounds#bounds-on-divsteps-iterations-in-safegcd https://github.com/sipa/safegcd-bounds#bounds-on-divsteps-it... The hull-bound technique is different from the technique used in the safegcd paper-- it's more accessible to a less mathematical audience, it is easily adapted to algorithm variations (which let us find a variation with a much better worst case), and also usually results in tighter bounds.