（2017年10月17日にQiitaにて執筆した記事をこちらに転載しています。）

経緯

暗号通貨の技術に興味を持っていまして、勉強の為に1からビットコインアドレスを自分で作ってみようと思ったのですが、いきなり躓いたところがあったので共有したいと思いました。

躓いたところ

ビットコインアドレスを作る為の最初の手順は秘密鍵から公開鍵を作ることです。

公開鍵を作る為には楕円曲線上での加法、乗法を行う必要があります（この細かい内容については別記事にしたいと思います。）

公開鍵の作成手順を実装する為にビットコインニュースのこちらのページが非常に参考になりそうだったので読んでいたのですが、突然

def inv_mod(a, p = cP):

という関数が出てきたところで躓いてしまいました。このinv_mod()とは何者で何を計算しているのでしょうか？

inv_mod()とは何者で何を計算しているのか？

多分"inverse modular"かなんかの略だろうという推測のもと検索した結果、この世にはモジュラ逆数なる概念があることを知りました。

モジュラ逆数 - Wikipedia

このWikipediaページや関連する情報を読んで、inv_mod()がモジュラ逆数を計算しているものだということも分かりましたし、モジュラ逆数を計算する方法も分かりました。

しかしそれでも、楕円曲線上での加法や乗法を行うとき、なぜモジュラ逆数を計算する必要があるのかがまったく分かりませんでした。

モジュラ逆数を求める必要があるのはどういうときか？

これは一言で言ってしまうと、有限体上での割り算を行うときです。私は数学の専門家じゃないので用語とか定義が間違っている可能性は高いですが、要はmod 11とか計算式の右側についている場合の割り算のときです。

詳しいことはまた別途書きたいと思いますが、楕円曲線上での加法や乗法を行う時には、まさに式の中に分数、つまり割り算が出てきてますし、式にはmodが付いています。

モジュラ逆数を具体例で理解する

最初に言っておきますとQiitaに楕円曲線暗号の超簡単な理論の紹介という素晴らしい記事がありまして、以下の内容はそちらをかなり参考にさせて頂いております。是非リンク先の記事も読んで下さい。

ではまず割り算の前に足し算、引き算、掛け算については以下のように普通に出来ることを確認したいと思います。

ちなみに≡は合同を意味します。

$3+9 \equiv 1 \mod11$

$4-3 \equiv 1 \mod11$

$3 \times 4 \equiv 1 \mod 11$

はい、そうですね。普通に四則演算した結果の答えを11で割って、その余りを本当の答えとすればいいだけです。

次は割り算です。例えば

$3 \div 4 \mod11$

は一体どう計算したらよいでしょうか？ $\frac{3}{4}$ 、つまり0.75を11で割った余りが答えでしょうか？

割り算を「逆数を掛け算する」と捉える

ここでまず、そもそも $\frac{1}{4}$ とは何かを考えてみたいと思います。 $\frac{1}{4}$ とは4と掛け算すると答えが1になる値という定義することができると思います。数学用語で $\frac{1}{4}$ は4の逆数と言います。

$\frac{1}{4}$ が4の逆数であることは例えmod 11のもとに計算が行われても変わりはありません。

つまり

$3 \div 4 = 3 \times \frac{1}{4} = 3 \times (4の逆数) \mod11$

を求めればいいことになります。この4の逆数をmod 11のもとに求めればいいわけで、これがモジュラ逆数と呼ばれるものです。「mod 11のときの4の逆数」を求めればいいわけです。

mod 11のときの4の逆数は何なのかを考えてみる

コードを書いて「mod 11のときの4の逆数」を求める前に、普通に人間の感覚を使って求めたいと思います。

上述しましたが、 $\frac{1}{4}$ とは4と掛け算すると答えが1になる値という定義することができます。mod 11のとき、4に何を掛け算すると答えが1になるでしょうか？そうです。 $4 \times 3 \equiv 1 \mod11$ なので、3をかけると1になります。ちなみに14や25でも掛け算すると1になります。

つまり $3 \div 4 \mod11$ は $3 \times 3 \mod11$ と同じなのです。これで晴れて計算を行うことが出来ます。この記事のタイトルにあるように $3 \div 4 \mod11$ の答えは $9$ となります。

このように $\mod 11$ などのもとに割り算を行う場合、分母にある値の逆数（モジュラ逆数）を求めてから、掛け算の形に直して計算を行う必要があります。これがモジュラ逆数を計算する必要がある理由です。

ちなみに割り算が割り切れるときは逆数を求めなくても計算できてしまいます。もちろん逆数を求めても計算できます。

$6 \div 3 \equiv 2 \mod11$ $6 \times \frac{1}{3} = 6 \times (3の逆数) = 6 \times 4 \equiv 2 \mod11$

となって答えが同じであることが確認できたと思います。

モジュラ逆数をプログラムで求める

先ほどのWikipediaページに計算方法が紹介されています。

モジュラ逆数 - Wikipedia

ある整数 $a$ の $\mod m$ における逆数を求めたいとき、その逆数を $x$ とすると以下が成り立ちます。

$ax \equiv 1 \mod m$

これは言い換えると、 $ax$ から1を引くと $m$ もしくは $m$ を整数倍した数になるということです。その整数倍を $qm$ と表現すると以下が成り立ちます。modじゃなくて普通の計算式になっていることにご注意ください。

$ax - 1 = qm$

整理するとこうなります。

$ax - qm = 1$

我々は $x$ を求めたいわけですが、ここで拡張ユークリッドの互除法というアルゴリズムを使って求めることが出来ます。

ユークリッドの互除法という最大公約数（GCD）を求めるアルゴリズムをご存知かと思いますが、その拡張版として、

$ax + by = \gcd(a, b)$

を成り立たせる整数ペア $x$ , $y$ もついでに求めることができるというアルゴリズムです。上の $ax - qm = 1$ ではGCDは既に1だと分かっていますけれど、

$ax + (-mq) = \gcd(a, m)$

とすれば同じアルゴリズムで $x$ と $q$ が求まりそうです。こちらのWikipediaページに乗っているコードを参考にしてC#で書いてみたいと思います。

using System;

namespace ModInverseTest
{
    class Program
    {
        public static void ExtendedEuclid(int a, int b)
        {
            var x = 0;
            var y = 1;
            var gcd = b;

            var prev_x = 1;
            var prev_y = 0;
            var prev_gcd = a;

            var temp = 0;

            while (gcd > 0)
            {
                int quotient = prev_gcd / gcd;

                temp = x;
                x = prev_x - quotient * temp;
                prev_x = temp;

                temp = y;
                y = prev_y - quotient * temp;
                prev_y = temp;

                temp = gcd;
                gcd = prev_gcd - quotient * temp;
                prev_gcd = temp;
            }

            Console.WriteLine(string.Format("{0}*{1} + {2}*{3} = gcd({0},{2}) = {4}",
                a,
                prev_x,
                b,
                prev_y,
                prev_gcd));
        }

        static void Main(string[] args)
        {
            ExtendedEuclid(1071, 1029);
        }
    }
}

以下が出力結果です。

1071*-24 + 1029*25 = gcd(1071,1029) = 21

では最後にこの関数を改造して、モジュラ逆数を求めるプログラムを書いてみます。冒頭で書いた通り私はこの関数を楕円曲線上の演算にて使う予定なので、大きな数にも対応できるようにBigInteger型を使います（ちなみにJavaのBigInteger型を使うと、ModInverse()というメソッドが既に実装されているようです。）

using System;
using System.Numerics;

namespace ModInverseTest
{
    class Program
    {
        public static BigInteger ModInverse(BigInteger a, BigInteger m)
        {
            if (a < 0)
            {
                a = BigInteger.ModPow(a, 1, m) + m;
            }

            BigInteger x = 0, y = 1, gcd = m;
            BigInteger px = 1, py = 0, pgcd = a;
            BigInteger temp = 0;

            while (gcd > 0)
            {
                BigInteger quotient = pgcd / gcd;

                temp = x;
                x = px - quotient * temp;
                px = temp;

                temp = y;
                y = py - quotient * temp;
                py = temp;

                temp = gcd;
                gcd = pgcd - quotient * temp;
                pgcd = temp;
            }

            return px;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("a = 3, m = 11, mod_inverse = " + ModInverse(3, 11));
            Console.WriteLine("a = 4, m = 11, mod_inverse = " + ModInverse(4, 11));
        }
    }
}

以下が出力結果です。

a = 3, m = 11, mod_inverse = 4
a = 4, m = 11, mod_inverse = 3

正しくモジュラ逆数が求められています。

最後になりますが、モジュラ逆数のWikipediaにもあったように、もし $m$ が素数であれば以下が成り立つようです。

$(整数aのモジュラ逆数) = a^{m-2} \mod m$

.NETのBigIntegerにもModPow()という関数が用意されているので、mが素数のときであれば以下のように関数を書くこともできます。

public static BigInteger ModInverse(BigInteger a, BigInteger m)
{
    return BigInteger.ModPow(a, m - 2, m);
}

まとめ

もともとはビットコインアドレスをスクラッチから自分で作ってみようと思っていたのですが、モジュラ逆数のことで躓いてしまい、色々と調べたり試したりすることになりました。

モジュラ逆数を求められないと、modが付いているとき（有限体上で）の式で割り算が出来ません。そしてこの割り算ができないと、楕円曲線上での加法や乗法ができません。そして楕円曲線上での加法や乗法ができないと、秘密鍵から公開鍵を作成できません。結果ビットコインアドレスを作ることができません。

以上です。次はビットコインアドレスの作り方を記事にします。

参照

追記（2017年10月26日）

負の数の逆数を入力とすると、逆数が0となってしまう問題がありました。修正の為、入力が負の数だった場合、同等の正の数に変換するようにしました。

Never Too Late

いつだってゼロからやり直そう

3 ÷ 4 ≡ 9 mod 11を計算するのに必要なモジュラ逆数を理解する

経緯