The safegcd implementation in libsecp256k1 explained

And 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-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.