はじめに
RSA暗号を学ぶとき、必ずと言っていいほど登場する式があります。
\(d = e^{-1} \pmod{(p-1)(q-1)}\)
初めて見ると「えっ？逆数？」「modってなに？」と疑問がわいてきますよね。
今回は、このモジュラ逆数（modular inverse）の意味や使い方について解説します。
RSA暗号で出てくる逆数の式
式をシンプルに考える
まずは、式をシンプルに書き直します。
\(d = e^{-1} \pmod{(p-1)(q-1)}\)
ここで、\(m = (p-1)(q-1)\)とおくと、次のように表せます。
\(y = x^{-1} \pmod{m}\)
この「mod m」というのは「mで割った余り」を意味します。
普通に読むと「xの逆数 \(1/x\) を計算して、その値をmで割った余りがyになる」と考えてしまいがちですが、実際にはx, y, mはすべて整数なので、\(1/x\) は小数になってしまい、「小数をmで割る」ということ自体が成り立ちません。
モジュラ逆数（modular inverse）とは？
実は、ここで言う「逆数」は普通の逆数ではなく、「モジュラ逆数（modular inverse）」と呼ばれるものです。これは、「xとyを掛けて、mで割った余りが1になるようなyを探す」という意味です。
モジュラ逆数の表現を消すと、次のようになります。
\(1 = xy \pmod{m}\)
上記の計算結果を満たすような y を求める式なのです。
具体例で考えてみる
たとえば \(x = 3\), \(m = 10\) のとき、yはいくつでしょうか？
代入すると次のようになります。
- \(y = 3^{-1} \pmod{10}\)
- \(1 = (3 \times y) \bmod{10}\)
0から順にyに代入して試してみると
- \(3 \times 0 = 0\) （10を割った余り0）
- \(3 \times 1 = 3\) （10を割った余り3）
- \(3 \times 2 = 6\) （10を割った余り6）
- \(3 \times 3 = 9\) （10を割った余り9）
- \(3 \times 4 = 12\) （10を割った余り2）
- \(3 \times 5 = 15\) （10を割った余り5）
- \(3 \times 6 = 18\) （10を割った余り8）
- \(3 \times 7 = 21\) （10を割った余り1）
このように、y=7が答えです。
- \(1 = (3 \times 7) \bmod{10}\)
- \(1 = (21) \bmod{10}\)
- \(1 = 1\)
どうやって求めるのか
0から順番に実施しましたが、もっと効率よく求める方法があります。モジュラ逆数の記事の「拡張ユークリッド互除法（Extended Euclidean Algorithm）」です。この手順は少し複雑ですが、多くのプログラミング言語では標準ライブラリで簡単に計算できます。
たとえばJavaの場合、 BigInteger の modInverse メソッドを使います。
public static void main(String[] args) {
System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
}
このコードを実行すると「7」と出力され、\(3^{-1} \pmod{10} = 7\) であることが分かります。
おわりに
RSA暗号で登場する「逆数」の式は、通常の逆数 \(1/x\) ではなく、モジュラ逆数（\(xy \equiv 1 \pmod{m}\) を満たす整数y）を求めていた、という話でした。
一見難しく感じますが、例題で具体的に計算してみると理解しやすいです。プログラムでも簡単に計算できるので、ぜひご自身でも試してみてください。
コメント