Re: Stein's (binary) GCD algorithm (iterative version)

[jzakiya]

Here's a gist of the code.

[https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39](https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39)

Re: Stein's (binary) GCD algorithm (iterative version)

[jzakiya]

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)

Re: Stein's (binary) GCD algorithm (iterative version)

[mratsim]

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.

Stein's (binary) GCD algorithm (iterative version)

[jzakiya]

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.

[https://en.wikipedia.org/wiki/Binary_GCD_algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)

Here's a Nim implementation of the iterative version.


proc gcd(a, b: int): int =
  var (a, b) = (a, b)
  if a == 0: return b
  if b == 0: return a
  
  var k = 0
  while ((a or b) and 1) == 0:
a = a shr 1
b = b shr 1
k += 1
  
  while (a and 1) == 0: a = a shr 1
  
  while b != 0:
while (b and 1) == 0: b = b shr 1
if a > b: swap a,b
b -= a
  
  result = a shl k


Here's a Ruby implementation of it.


def gcd(a, b)
  return b if a.zero?
  return a if b.zero?
  
  k = 0
  while (a | b).even?
 a >>= 1; b >>= 1; k += 1
  end
  
  a >>= 1 while a.even?
  
  until b.zero?
b >>= 1 while b.even?
a, b = b, a if a > b
b -= a
  end
  
  a << k
end