法Nでの逆数を求める

2013年11月20日(水)

と書くと何やら難しそうですが、簡単にいうならば $n$ という整数が与えられたとき

$n x = 1 (\mod N)$

となる数 $x$ を見つけようということです。このような逆数はnとNが互いに素なら必ずあります。法Nにおける逆数は整数の剰余の計算においてとても重要であり暗号の分野で頻繁に使われています。

(多くの）プログラム言語的に言い換えると

(n * x) % N = 1

となる数ということになるでしょう。ここで細かいことをいうと $n$ が負数のときどうなるん？という問題があります。例えばperlやrubyだと $n$ が負の場合は（例えば -1 % 7)は 6を返しますが、CやNode.jsは-1を帰すようです。ちなみに、数学的にはどちらでも問題なしです。何故どちらでもいいかを語り始めると長いので細かいことは有限体の本でも読んでもらうとして、結論から言うと

$- 1 = 6 (\mod 7)$

と思っておけば問題ないです。7を法とした世界では-1も6も同じものを指します。表現の仕方が違うだけです。

さてこのアプローチには大きく2種類あるようです。一つはユークリッドの互除法を使うもの。もう一つはopensslの内部て使われているものです。後者のアルゴリズムに名前があるのかどうかはしりません。

最初にユークリッドの互除法を使う手法を紹介します。

ユークリッドの互除法とは数 $a$ , $b$ が与えられたときにその最大公約数を求める手法ですが、その解を求める課程を利用して

$a x + b y = 1$

を解くことができるのです。実際ここで $a = N, b = n$ として両辺をNで割ったあまりをみれば

$b y = 1 (\mod N)$

ですからyが求めるものであることがわかります。ちなみに上の式は $a, b$ が互いに素なら（つまりGCD(a,b)=1ならば必ず解を持つことが知られています。

さてそのアルゴリズムですが、このアルゴリズムをを一般式で書くと煩雑になるので具体的に $a = (N =) 916132831, b = (n =) 9973$ として説明します。まず $a$ を $b$ で割った余りと商を利用して以下のように変形します。

$916132831 x + 9973 y = (91861 \times 9973 + 3078) x + 9973 y = 3078 x + 9973 (91861 x + y)$

ここで $x^{'} = 91861 x + y y^{'} = x$ とすれば $9973 x^{'} + 3078 y^{'}$ という式が得られます。商と余りを利用してより小さい係数の式を得ることができました。

定理

$a_{1}, b_{1}$ を正の整数で $a_{1} > b_{1}$ とし $a_{n}, b_{n}, x_{n}, y_{n}$ を以下のように定義する $a_{n + 1} = b_{n} b_{n + 1} = m_{n} x_{n + 1} = d_{n} x_{n} + y_{n} y_{n + 1} = x_{n}$ ただし $d_{n}$ は $m_{n}$ は $a_{n} = d_{n} b_{n} + m_{n} (0 \leq m_{n} < b_{n})$ を満たす整数とすると $a_{n} > b_{n}$ であり $a_{1} x_{1} + b_{1} y_{1} = a_{n} x_{n} + b_{n} y_{n}$ が成立する。

このように書くと何やら複雑ですがプログラム的には

a[n+1] = b[n]
b[n+1] = a[n] % b[n]

ということです。このように $a_{n}, b_{n}$ だけを計算していくといつかは $a_{n}$ は $1$ に、 $b_{n}$ は0になります。そのとき

$x_{n} = 1 y_{n} = 0$ とすると、 $a_{n} x_{n} + b_{n} y_{n} = 1$ を満たしますから、これから逆に、 $x_{n - 1}, y_{n - 1}$ が求まってゆき、最終的に $y_{1}$ が求まります。これが求める答えになります。例として、 $a_{1} = 916132831$ と $b_{1} = 9973$ で計算していくと以下のようになります。

         #         a         b         d         m
         1 916132831      9973     91861      3078
         2      9973      3078         3       739
         3      3078       739         4       122
         4       739       122         6         7
         5       122         7        17         3
         6         7         3         2         1
         7         3         1         3         0
         8         1         0

これから $x_{8} = 1, y_{8} = 0$ が求まります。これから $x_{7}, y_{7}, x_{6}, y_{6}, . . .$ と計算していくと

         #         x         y
         7         0         1
         6         1        -2
         5        -2        35
         4        35      -212
         3      -212       883
         2       883     -2861
         1     -2861 262815204

となり、 $y_{1} = 262815204$ が求まります。

実際 $9973 \times 262815204 = 1 (\mod N)$ です。

サンプルコード


#!/usr/bin/env ruby

a = []
b = []
d = []
m = []
x = []
y = []
n = a[1] = 916132831
b[1] = 9973

i = 1
while b[i] != 0
  d[i] = a[i] / b[i]
  m[i] = a[i] % b[i]

  a[i + 1] = b[i]
  b[i + 1] = m[i]
  
  i = i + 1
end

x[i] = 1
y[i] = 0
j = i
while j > 1
  j = j - 1
  x[j] = y[j + 1]
  y[j] = x[j + 1] - d[j] * x[j]
end

puts("#{y[1]} * #{b[1]} = #{b[1] * y[1] % n} (mod #{n})")

ユークリッドの互除法はとても早く1まで係数が降下するので効率もよいのですが $a_{n}, b_{n}$ の途中の計算結果を保存しておかないといけないという問題があります。また、 $d, m$ を求めるのに商計算をしなくてはなりません。一般的に商の計算はとても遅く、特にNが数1000bitともなるとその計算がオーバヘッドとなるので、出来ることなら使いたくないというのが本音です。そこでより効率のよいアルゴリズムがopensslでは使われています。それを次回に紹介したいと思います。

元祖ワシ的日記