元祖ワシ的日記

一つ前のエントリ

法Nでの逆数を求める

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

\[ax + by = 1\]

ではなく

\[ax + by = 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} \]

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

\[b_1 x_n = \pm b_n x_1 \pmod 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$については次の補題を利用します。

この補題より$\hbox{gcd}(x_n, y_n) = \hbox{gcd}(x_1, y_1) = 1$であり、したがって $x_n=0$ならば$y_n=1$でならねばならず それは$b_n=0$でなければならないので矛盾