Here's a gist of the code.
[https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39](https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39)
Back in the day I had that book, when I wore a younger man's clothes, and also
**Applied Cryptography**. I wonder what happened to them
[https://www.goodreads.com/book/show/351301.Applied_Cryptography](https://www.goodreads.com/book/show/351301.Applied_Cryptography)
Relevant [Handbook of Applied
Cryptography](http://cacr.uwaterloo.ca/hac/about/chap14.pdf) on page 17 of the
this chapter 14 PDF (page 606 - chapter 14.4 of the whole book)
It has the binary GCD, extended binary GCD and Lehmer's GCD algorithm.
On the Ruby issue tracker replacing Euclid's gcd algorithm with Steins (binary)
algorithm came up.
[https://bugs.ruby-lang.org/issues/13503](https://bugs.ruby-lang.org/issues/13503)
Here's the wikipedia article on it.