法Nでの逆数を求めるその２

2013年11月21日(木)

一つ前のエントリ

法Nでの逆数を求める

の手法は途中の計算結果を保存しておかないといけないという問題がありました。そこでそれを改良したアルゴリズムを紹介します。このアルゴリズムもユークリッドの互除法を使うという点では同じです。違うのは

$a x + b y = 1$

ではなく

$a x + b y = N$

を考えている点がです。この式は $a = N, b = n$ とすると $x = 1, y = 0$ という自明な解を持っています。

そこで $a_{1} = N, b_{1} = n, x_{1} = 1, y_{1} = 0$ として前回と同じように

$a_{n + 1} = b_{n} b_{n + 1} = m_{n} x_{n + 1} = d_{n} x_{n} + y_{n} y_{n + 1} = x_{n}$ と変形していきます。 $a_{n} x_{n} + b_{n} y_{n} = N$ が常に成り立っているので、

$a_{n} x_{n} = N - b_{n} y_{n}$ が成立します。 $a_{n} = b_{n - 1}, y_{n} = x_{n - 1}$ ですから $b_{n - 1} x_{n} = N - b_{n} x_{n - 1}$ と書き直すことができます。nを2からnまで変化させた等式

$b_{1} x_{2} = N - b_{2} x_{1} b_{2} x_{3} = N - b_{3} x_{2} \dots b_{n - 1} x_{n} = N - b_{n} x_{n - 1}$

について左辺どうし、右辺どうしを掛け合わせると

$左辺 = b_{1} b_{2} \dots b_{n - 1} x_{2} x_{3} \dots x_{n}$ $右辺 = N (なんちゃら) \pm b_{2} b_{3} \dots b_{n} x_{1} x_{2} \dots x_{n - 1}$

となります。 $(\mod N)$ で考えれば $N (なんちゃら)$ は0とみなせるので結局

$b_{1} x_{n} = \pm b_{n} x_{1} (\mod N)$

が常に成立していることになります。符号はnの偶奇で決まります。なお $b_{1}, b_{2}, . . .$ および $x_{1}, x_{2}, . . .$ がゼロでないという証明が別途必要ですがそれは最後に記します。

ところで、 $b_{n}$ はいずれ1になります。 $x_{1} = 1, b_{1} = n$ でしたから、その時点で

$n x_{n} = \pm 1$

となり $x_{n}$ が求める解になります。このアルゴリズムは途中の計算結果を保存しておかなくてよいという利点があり一つ前のエントリより優れていると言えましょう。

サンプルコード


#!/usr/bin/env ruby
    
n = a = 916132831
b0 = b = 9973
x = 1
y = 0
sign = 1

while b != 1
  d = a / b
  m = a % b
  
  a = b
  b = m
  
  tmp = d * x + y
  y = x
  x = tmp
  
  sign = -sign
end

puts("#{sign * x} * #{b0} = #{b0 * x * sign % n} (mod #{n})")

さて、このアルゴリズムでも十分実用になるのですが、Nが奇数の場合はさらに効率よく求めることができます。そのアルゴリズムを次のエントリで紹介しようと思います。

補足

$b_{1}, b_{2}, . . .$ および $x_{1}, x_{2}, . . .$ がゼロでないという証明

$b_{n}$ については単調に減少し1になったところでアルゴリズムは止まるので0でないことは明らか。 $x_{n}$ については次の補題を利用します。

補題

$gcd (a_{n + 1}, b_{n + 1}) = gcd (a_{n}, b_{n}) gcd (x_{n + 1}, y_{n + 1}) = gcd (x_{n}, y_{n}) が成立する$

この補題より $gcd (x_{n}, y_{n}) = gcd (x_{1}, y_{1}) = 1$ であり、したがって $x_{n} = 0$ ならば $y_{n} = 1$ でならねばならずそれは $b_{n} = 0$ でなければならないので矛盾

元祖ワシ的日記