これは分かりやすい，拡張ユークリッド互除法

Javaで作って学ぶ暗号技術 - RSA,AES,SHAの基礎からSSLまで

書店で目に留まり，購入しました．
RSA, AES, SHAの構成とコードだけでなく，ユークリッド互除法やべき剰余に複数の(後ろにいくほど処理速度のよい)アルゴリズムも取り上げられています．
買う強いきっかけになったのは，拡張ユークリッド互除法(2.4節)で，p.58掲載のアルゴリズムを，Rubyで書いてみました．

#!/usr/bin/env ruby

# extended_euclid.rb

def print_equation(a, x, b, y)
  puts "#{a} * #{x} + #{b} * #{y} = #{a * x + b * y}"
end

def check_equation(a, x, b, y, g)
  print "#{a} * #{x} + #{b} * #{y} = #{g}"
  g2 = a * x + b * y
  if g == g2
    puts " ...ok"
  else
    puts " ...wrong"
  end
end

def extended_euclid(a, b, option_print = false)
  x_2, x_1 = 1, 0
  y_2, y_1 = 0, 1
  r_2, r_1 = a, b
  check_equation(a, x_2, b, y_2, r_2) if option_print
  check_equation(a, x_1, b, y_1, r_1) if option_print
  loop do
    q, r = r_2.divmod(r_1)
    puts "q = #{q}, r = #{r}" if option_print
    x = x_2 - q * x_1
    y = y_2 - q * y_1
    check_equation(a, x, b, y, r) if option_print
    break if r == 0
    x_2, x_1 = x_1, x
    y_2, y_1 = y_1, y
    r_2, r_1 = r_1, r
  end
  [x_1, y_1, r_1]
end

if __FILE__ == $0
  a = (ARGV.shift || 79).to_i
  b = (ARGV.shift || 23).to_i
  x, y = extended_euclid(a, b, true)
  print_equation(a, x, b, y)
end

コードで特別なことはしていませんが，あえて書くと，「x_2, x_1 = 1, 0」は一括代入で「x_2 = 1; x_1 = 0」と同じことだってのと，無限ループはloop do〜endでいいよといったところでしょうか．
aとbのデフォルト値，79, 23というのは，今期の試験問題で出した数値です．
実行してみましょう．1年前のも．

$ ruby extended_euclid.rb
79 * 1 + 23 * 0 = 79 ...ok
79 * 0 + 23 * 1 = 23 ...ok
q = 3, r = 10
79 * 1 + 23 * -3 = 10 ...ok
q = 2, r = 3
79 * -2 + 23 * 7 = 3 ...ok
q = 3, r = 1
79 * 7 + 23 * -24 = 1 ...ok
q = 3, r = 0
79 * -23 + 23 * 79 = 0 ...ok
79 * 7 + 23 * -24 = 1
$ ruby extended_euclid.rb 94 27
94 * 1 + 27 * 0 = 94 ...ok
94 * 0 + 27 * 1 = 27 ...ok
q = 3, r = 13
94 * 1 + 27 * -3 = 13 ...ok
q = 2, r = 1
94 * -2 + 27 * 7 = 1 ...ok
q = 13, r = 0
94 * 27 + 27 * -94 = 0 ...ok
94 * -2 + 27 * 7 = 1

こうして見ると，aとbは固定し，xとyとrを適切に変更していくことで，

• a * x + b * y = rが常に成立
• r = 0となる直前のrが，aとbの最大公約数(1なら，aとbは互いに素)
• r = 0となる直前のxとyが答え

というのが分かります．
拡張ユークリッド互除法について，授業では『現代暗号理論』に基づくアルゴリズムを用いてきました．そこでは，yの計算は上と同じで，「a * x + b * y = gcd(x, y)」の式からxを求めています．
冒頭の本のアルゴリズムのほうが，乗算の数が増えますが，各ターンで式の確認ができるので，よさそうです．来年度から改訂するとともに，この本を授業の参考書に入れるべきですね…．