No.310 - 高校数学で理解するRSA暗号の数理（１）

No.235「三角関数を学ぶ理由」では、私たちが学校で勉強を学ぶ目的の一つが「論理的に考える力を養う」こととし、その典型例として数学をとりあげました。数学は「論理のみで成り立っている」からです。そのことを改めて示すために $sin\theta$ の微分が $cos\theta$ になることを、三角関数のそもそもの定義に立ち返って証明しました。

今回はその継続・発展で、別の数学の問題を取り上げます。現代社会で広く使われている公開鍵暗号（その中の RSA暗号）です。これを取り上げる理由は、

◆	2000年にわたる数学（数論 ＝ 整数論）の基礎の上に作られた暗号である。
◆	インターネットの重要技術の一つであり、現代社会のインフラとなっている。
◆	高校生程度の前提知識があれば、論理的思考を積み重ねることで十分に理解できる（＝ タイトルの「高校数学で理解する」の意味）。

の３点です。以下の文章は元々別の目的のために作ったものですが、ここに掲載することにします。

---

公開鍵暗号

---

公開鍵暗号とは、

◆	暗号化の手順と、そこで使用する暗号化のための "鍵" が公開されている（その鍵が "公開鍵"）。
◆	暗号文を解読するための手順も公開されているが、それに使う "鍵" は秘匿されている（その鍵が "秘密鍵"）。

というタイプの暗号です。公開鍵暗号のメリットは多々ありますが、一番のメリットは「鍵を配送するコストがかからない」ことです。全ての鍵を秘匿する暗号だと、その鍵をどうやって配送して暗号化をしたい人に届けるかが大きな問題となります。暗号化通信で配送するというのは解決になりません。その暗号化通信の暗号鍵をどうやって配送するかという問題が残るからです。

公開鍵暗号では暗号化のための鍵がオープンなので、配送のコストはゼロです。暗号文を受け取りたい人が公開鍵と秘密鍵を生成し、公開鍵をオープンにすると誰でもその人に暗号文を送ることができます。

公開鍵暗号の設計の最大のポイントは、あたりまえですが、公開鍵から秘密鍵を推定したり導出したりできないことです。まさにそこに数学が使われていて、暗号文を解読できないようになっています。この「暗号化の鍵を公開してしまう」という革新的なアイデアというか、まさに "究極の逆転の発想" を論文として発表したのは、当時スタンフォード大学の研究者だったディフィー（米）とヘルマン（米）で、1976年のことでした。

ディフィーとヘルマンは公開鍵暗号の発明の功績で、コンピュータ・サイエンス分野のノーベル賞といわれるチューリング賞を 2015年に受賞した。

（https://awards.acm.org/ より）

そのディフィーとヘルマンのアイデアに基づいた最初の暗号が RSA暗号で、現代でも盛んに使われています。これは 1978年に MIT のリベスト（米）、シャミア（イスラエル）、エーデルマン（米）の３人のよって発明され、３人の頭文字をとってRSAと呼ばれています。

実はこの RSA暗号は、実用として何に使ったらいいのか、発表当時は使い道が分からなかったといいます。それが現代ではインターネットによる通信の重要技術として広く使われている。これにはコンピュータの処理速度の飛躍的向上も貢献しています。革新的な技術は、その応用環境が整った時点で、後から実用化される。よくあることです。

RSA暗号を発明した３人は、チューリング賞を 2002年に受賞している。

（https://awards.acm.org/ より）

以下、このRSA暗号の数理を順に見ていきます。

---

RSA暗号の例題

---

まずRSA暗号はどういうものか、それを極めて簡単な例題で説明します。

平文ひらぶん（＝暗号化する文）を $\mathbb{P}$ で、またそれを暗号化した暗号文を $\mathbb{C}$ で表します。例題として平文は１文字だけの英字で、それを整数に変換したものとします。RSA暗号にちなんで大文字の R が平文です。コンピュータで使われる ASCII（アスキー）コードでは、英大文字・英小文字・数字・特殊記号を $1$～$128$ の数で表すので、それを使って数字化すると R は $82$ です。つまり、

$\mathbb{P}=82$

が例題の平文です。

公開鍵は２つの数字のペア $\left(e,n\right)$、秘密鍵は一つの数字 $d$ で、例題としては、

公開鍵 ： $\left(e=133,n=143\right)$
秘密鍵 ： $d=37$

とします。この公開鍵と秘密鍵の作り方は後で述べます。平文から暗号文への変換（＝暗号化）と、暗号文から平文への変換（＝復号化）を次の計算で行います。以降の記述では、$a$ を $b$ で割った余り（＝剰余）を $amodb$ と書きます（プログラム言語やEXCELで $mod\left(a,b\right)$ と書くのと同じ意味です）。

暗号化 ： $\mathbb{C}={\mathbb{P}}^{e}modn$
復号化 ： $\mathbb{P}={\mathbb{C}}^{d}modn$

例題の平文を暗号化の式に入れると、

$\mathbb{C}={82}^{133}mod143=4$

となり、平文 "$82$" に対する暗号文は "$4$" です。${82}^{133}$ は巨大な数ですが、剰余を求めるときにこの巨大数を計算する必要は全くありません。上の程度の計算なら電卓でも簡単にできます。そのやり方は後ほど示します（「4. RSA暗号の証明」）。暗号文の復号化は、暗号文 "$4$" を復号化の式に入れると、

$\mathbb{P}=4^{37}mod143=82$

となり、元の平文である "$82$" が復元できました。なお、この例では平文をわずか１文字（$2^7$ 以下の数字）としましたが、実際に使われる暗号では $2^{1024}$ 程度（10進で約300桁程度）の数字です（＝ 平文を数字化したもの。平文が長い場合は複数に分割）。また、公開鍵 $\left(e,n\right)$ と秘密鍵 $d$ も同程度の大きさの数字です。

この計算で暗号化と復号化が可能なのは、公開鍵と秘密鍵の作り方に工夫があるからです。まず $n$ は２つの素数 $p=11$ と $q=13$ の積です。

また $e$ は、$e$ と $\left(p-1\right)\left(q-1\right)=120$ との最大公約数が $1$ であるように決めてあります。$e=133=7·19$ なので、$133$ と $120$ との共通の約数は $1$ だけです。さらに秘密鍵である $d$ は、

$d·emod\left(p-1\right)\left(q-1\right)=1$

となるように決めてあります。$37·133=4921=41·120+1$ なので成り立っています。このように鍵を仕込んでおくと暗号化と復号化が可能になる。そのことを証明するのが、本記事の目的です。その証明を、前提とする数学知識を最小限にしてやってみたいと思います。

---

公開鍵暗号は「公開鍵から秘密鍵が導出できない」ことが必須です。RSA暗号では、$n=p·q$ と素因数分解ができれば、

$d·emod\left(p-1\right)\left(q-1\right)=1$

の式を解いて $d$ が求まります。しかし実用で使われるRSA暗号は最低でも $n$ の桁数が10進数で300桁程度です（２進数で 1024ビット程度。平文も同等の長さ）。この程度の大きさの整数の素因数分解は、超高速コンピュータをもってしても困難です。もしコンピュータの速度がさらに向上するなら、鍵の桁数をさらに大きくすればよい。この素因数分解の困難性が、RSA暗号が成り立つ理由です。

---

以降でRSA暗号の暗号化と復号化の式が成り立つことの証明を行います。さらに、単に成り立つことだけでなく、RSA暗号に関わる各種の式が計算可能であることの説明をします。"式が正しい" ことと、その "式が実用的に計算可能である" ことは違うからです。素因数分解がまさにその例です。

まず、整数の性質についての用語の定義からです。用語は RSA暗号の式の証明に必要なものだけに絞ります。以降に現れる "数" やそれを表す記号は、ほとんど場合は整数のことですが、自然数（1以上の整数）を意味する場合もあります。どちらかは文脈から明らかなので、いちいち断りなく使います。

---

準備：用語の定義

---

割り切る・約数・因数・最大公約数

整数 $N$ を $a$ で割ったときの余りがゼロのとき、$N$ は $a$ で割り切れると言い、また、$a$ は $N$ を割り切ると言います。このことを記号を使って、

$a|N$

と書きます。またこのときの $a$ を $N$ の約数と呼びます。$N|N$ と $1|N$ は常に成り立つので、$1$ と $N$ は $N$ の約数です。

$N$ が 2つ以上の数の積で表されるとき、そのおのおのの数を $N$ の因数と呼びます。因数は約数と同じものですが、見方の違いと言えるでしょう。

２つの数、$N$ と $M$ があったとき、共通の約数を公約数と言います。また、公約数のうち最大のものを最大公約数と呼び、$gcd\left(N,M\right)$ で表します。

素数と素因数分解

2以上の整数 $N$ の約数が 1 と $N$ のみのとき、$N$ を素数と言い、そうでない数を合成数と言います。合成数は 1 と $N$ 以外の約数を持ちます。約数（＝因数）が素数のとき、それを素因数と呼びます。$N$ が素数の場合は $N$ が素因数です。

合成数は素因数の積で表現できます（＝素因数分解）。なぜなら、定義によって合成数 $N$ は、$1$ でも $N$ でもない数 $a$ と $b$ を使って $N=a·b$ と表現（＝分解）できますが、$a$ や $b$ が合成数なら、さらに分解を繰り返すことによって最終的には素数の積にたどり着くからです。なお便宜上、素数はそれ自身が素因数分解であるとします。

「素数」と「大きな数の素因数分解の困難性」が RSA暗号の基礎になっているのは、例題で説明した通りです。

素因数分解の一意性

素因数分解は、かけ算の順序を無視して一意に決まります（＝素因数分解の一意性）。これは自明のように思えますが、証明をすると次の通りです。

いま（かけ算の順序は無視して）異なった２種類の素数列の積で表現できる合成数がある（＝素因数分解が一意ではない）と仮定します。すると、そのような最小の数、$N$ があるはずです。このとき $N$ は、$p_i$ と $q_i$ を素数として、

$N=p_1{p}_2{p}_3\dots p_r=q_1{q}_2{q}_3\dots q_s$

と表現できます。ここで $p_1$ に着目すると $p_1|N$ なので、$p_1|q_i$ となる $q_i$ があるはずです。かけ算の順序は無視するので、$p_1|q_1$ として一般性を失いません。ところが $q_1$ は素数なので、$q_1=p_1$ しかあり得ない。そこで式の全体を $p_1$ で割ると、

$\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$p_1$}\right.=p_2{p}_3\dots p_r=q_2{q}_3\dots q_s$

となります。これは $\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$p_1$}\right.$ が２つの異なった形に素因数分解できることを示しています。ところが $\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$p_1$}\right.$ は $N$ より小さい数なので「$N$ が２つの異なった形に素因数分解できる最小の数」ということに矛盾します。従って「２つの異なった形で素因数分解できる数がある」という仮定が誤りであり、素因数分解の一意性が示されました。

互いに素

整数 $N$ と 整数 $M$ の最大公約数が $1$ のとき、つまり $gcd\left(N,M\right)=1$ のとき、「$N$ と $M$ は互いに素である」と言います。これは $N$ と $M$ が共通の素因数を持たないことと同じです。なお、$gcd\left(N,1\right)=1$ は常に成り立つので、$1$ は他の数と互いに素です。

以降の、RSA暗号の証明に至るプロセスでは「互いに素」に関連した数々の定理や証明が出てきます。RSA暗号は「素数」と「互いに素」の上に構築された暗号です。

---

用語の定義はここまでです。以降はRSA暗号の成立性の証明に入ります。まず、数の "合同" の概念からです。

---

１. 合同

---

合同の概念はRSA暗号の根幹の一つです。$m$ を 2 以上の整数とするとき、２つの整数 $a$, $b$ について

・	$a$ を $m$ で割ったときの余りと、$b$ を $m$ で割ったときの余りが等しいとき、 あるいは同じことで、
・	$\left(a-b\right)$ が $m$ で割り切れるとき、つまり $m|\left(a-b\right)$ のとき、

$a$ と $b$ は $m$ を法として合同であると言い、

$a\equiv b\left(modm\right)$

と書きます。少々ややこしいですが、はじめに書いたように $amodb$ とすると「$a$ を $b$ で割った余り」の意味です。以下に、合同の性質でRSA暗号の証明に必要なものをあげます。

1.1
$a\equiv b\left(modm\right)$　かつ、 $c\equiv d\left(modm\right)$　のとき、 1.1a　$a+c\equiv b+d\left(modm\right)$ 1.1b　$a-c\equiv b-d\left(modm\right)$ 1.1c　$ac\equiv bd\left(modm\right)$

これらの性質は、それぞれの数を、

$$\begin{gathered} a=k_a·m+r_1 \\ b=k_b·m+r_1 \\ c=k_c·m+r_2 \\ d=k_d·m+r_2 \end{gathered}$$

というように書いて計算をすればすぐにわかります。たとえば 1.1c（合同式の乗算）を証明するには、$a$ と $c$ の式をかけ算し、$b$ と $d$ の式をかけ算して、

$$\begin{gathered} m\left|\left(ac-r_1{r}_2\right) \\ m\right|\left(bd-r_1{r}_2\right) \end{gathered}$$

が得られますが、２つの数が共に $m$ で割り切れると、その差も $m$ で割り切れます。従って、

$$\begin{gathered} m\left|\left(\left(ac-r_1{r}_2\right)-\left(bd-r_1{r}_2\right)\right) \\ m\right|\left(ac-bd\right) \\ ac\equiv bd\left(modm\right) \end{gathered}$$

となります。

1.2	合同式の累乗（冪乗）
$a\equiv b\left(modm\right)$ なら、2以上の $r$ について、 $a^r\equiv b^r\left(modm\right)$ である。

これは 1.1c で、$c=a$、$d=b$ とおいて 1.1c を "繰り返して使う" ことでわかります。"繰り返して使う" ことを証明として書くなら数学的帰納法になるでしょう。以降は「互いに素」に関連した合同の性質です。

1.3	互いに素（１）
$ax\equiv bx\left(modm\right)$ かつ、 $x$ と $m$ が互いに素なら、 $a\equiv b\left(modm\right)$

合同の定義により

$$\begin{gathered} m\left|\left(ax-bx\right) \\ m\right|x\left(a-b\right) \end{gathered}$$

となります。ここで一般的に次の 1.3a が成り立つことに注意します。

1.3a
$m$ は $x$ と互いに素とする。 $m|xn$ ならば $m|n$

$m$ と $x$ は互いに素なので、$m$ と $x$ に共通の素因数はありません。従って、$m$ を素因数分解したときに現れる素因数は、すべて $n$ の素因数のはずです。でないと、$m|xn$ とはならないからです。従って $m|n$ となります。このことを $m|x\left(a-b\right)$ に適用すると、

$$\begin{gathered} m|\left(a-b\right) \\ a\equiv b\left(modm\right) \end{gathered}$$

となり、1.3 が証明されました。1.3 は以降の証明にたびたび出てくる重要な定理です。1.3 を一般化したのが次の 1.4 です。

1.4	互いに素（２）
$ax\equiv by\left(modm\right)$ かつ、 $\phantom{a}x\equiv \phantom{b}y\left(modm\right)$ かつ、 $x$ と $y$ は $m$ と互いに素なら、 $a\equiv b\left(modm\right)$

$a$, $b$, $x$, $y$ を、$m$ と 剰余 $r$ を使って次のように表します。

$$\begin{gathered} \begin{array}{ll}a& =k_a·m+r_a\\ b& =k_b·m+r_b\\ x& =k_x·m+r\\ y& =k_y·m+r\end{array} \\ \left(0\le r_a,r_b,r<m\right) \end{gathered}$$

このようにおくと、$ax\equiv by\left(modm\right)$ より、

$r·r_a\equiv r·r_b\left(modm\right)$

となります。一方、$r$ と $m$ は互いに素です。なぜなら、もし $r$ と $m$ が $1$ ではない共通の約数 $c$ をもつとすると、上の $x$ の式から $c$ は $x$ の約数にもなり、$x$ と $m$ が互いに素ではなくなるからです。また、$y$ の式から $c$ は $y$ の約数でもあり、$y$ と $m$ が互いに素という前提にも反します。このように $r$ と $m$ は互いに素なので 1.3 を使って、

$r_a\equiv r_b\left(modm\right)$

となりますが、$0\le r_a,r_b <m$ なので、$r_a=r_b$ となり、

$a\equiv b\left(modm\right)$

が示されました。

1.5	互いに素（３）
$m$ と $n$ は互いに素とする。 $a\equiv b\left(modm\right)$ かつ、 $a\equiv b\left(modn\right)$ なら、 $a\equiv b\left(modmn\right)$

$a\equiv b\left(modm\right)$ なので、合同の定義から $m|\left(a-b\right)$ です。また、$a\equiv b\left(modn\right)$ なので、合同の定義から $n|\left(a-b\right)$ であり、$a-b=k_{1}n$ と表せます。この式の $a-b$ を $m|\left(a-b\right)$ に代入すると、

$m|k_{1}n$

となります。$m$ と $n$ は互いに素なので 1.3a を使うと、

$m|k_1$

となり、従って $k_1=k_{2}m$ と表せることになります。この $k_1$ を $a-b=k_{1}n$ に代入すると、

$$\begin{gathered} a-b=k_{2}mn \\ mn|\left(a-b\right) \\ a\equiv b\left(modmn\right) \end{gathered}$$

となって 1.5 が証明できました。

---

合同には数々の性質や定理がありますが、RSA暗号の証明に必要なものは以上です。次に、２つの数の最大公約数を求める「ユークリッドの互除法」です。これは最大公約数を求める計算方法というだけでなく、RSA暗号において公開鍵と秘密鍵を生成する際に必須のものです。

---

２. ユークリッドの互除法

---

ユークリッドの互除法は ２つの自然数（$a$ と $b$。$a>b$ とします）の最大公約数を求める計算方法です。これはユークリッドの数学書である『原論』にあります。『原論』は紀元前 300年頃の成立といいますから、2300年ほど前の書物ということになります。

この計算方法では、割り算（除算）を何ステップか繰り返します。割り算において被除数（＝割られる数）と除数（＝割る数）、商（＝答）、剰余（＝余り）の関係は、

被除数 ＝ 商 × 除数 ＋ 剰余

ですが、まず第１ステップとして、

被除数１	＝ $a$
除数１	＝ $b$

とおき、

被除数１ ＝ 商１ × 除数１ ＋ 剰余１

の計算をして、商１と剰余１を求めます。次に第２ステップとして、

被除数２	＝ 除数１
除数２	＝ 剰余１

とおいて割り算を行い、商２と剰余２を求めます。つまり、

被除数２ ＝ 商２ × 除数２ ＋ 剰余２

です。この「除数と剰余を新たな被除数と除数にして割り算をする」ステップを次々と繰り返して行くと、剰余は次第に小さくなっていき、ついには剰余がゼロ（＝ 被除数が除数で割り切れる）となります。この時点での除数（＝ 一つ前のステップの剰余）が $a$ と $b$ の最大公約数です。

なぜそうなるのかが以下ですが、ポイントは割り算の式から明らかなように「被除数と除数の公約数は、剰余の約数でもある」ことです。つまり $a$ と $b$ の約数であるという性質が剰余に引き継がれ、それは割り算のステップを繰り返してもずっと続きます。しかも、剰余はステップが進むにつれて小さくなっていくので、最大公約数に近づく。そして割り切れたときの除数（一つ前のステップの剰余）は、約数であると同時に最大の約数である。おおまかにはそのような理解です。

2.1	ユークリッドの互除法
$a$と $b$ を自然数とし、$a>b$ とする。 $\begin{array}{llll}a& =q_1·b_{\phantom{1}}+r_1& \text{ ⋯}& \text{(1)}\\ b& =q_2·r_1+r_2& \text{ ⋯}& \text{(2)}\\ r_1& =q_3·r_2+r_3& \text{ ⋯}& \text{(3)}\\ r_2& =q_4·r_3+r_4& \text{ ⋯}& \text{(4)}\\ \text{⋮}& & & \\ r_{i-4}& =q_{i-2}·r_{i-3}+r_{i-2}& \text{ ⋯}& \text{(i−2)}\\ r_{i-3}& =q_{i-1}·r_{i-2}+r_{i-1}& \text{ ⋯}& \text{(i−1)}\\ r_{i-2}& =q_{i\phantom{-0}}·r_{i-1}+r_{i\phantom{-0}}& \text{ ⋯}& \text{(i)}\\ r_{i-1}& =q_{i+1}·r_i& \text{ ⋯}& \text{(i+1)}\end{array}$ となったとき、 $gcd\left(a,b\right)=r_i$ である。

$a$ と $b$（$a>b$）の公約数を $x$ とします。すると、$x|a$ かつ $x|b$ なので、$\text{(1)}$ 式から $x|r_1$ になります。この $x|r_1$ と $x|b$ から $\text{(2)}$ 式を使って $x|r_2$ が得られます。

その次には $x|r_1$ 、$x|r_2$ 、(3) 式から $x|r_3$ になる。以上を最後まで繰り返すと、次のようになります。

$\begin{array}{lllll}x|a\text{,}& x|b\text{,}& \text{(1)式}& \stackrel{}{\to }& x|r_1\\ x|b\text{,}& x|r_1\text{,}& \text{(2)式}& \stackrel{}{\to }& x|r_2\\ x|r_1\text{,}& x|r_2\text{,}& \text{(3)式}& \stackrel{}{\to }& x|r_3\\ \text{⋮}& & & & \\ x|r_{i-4}\text{,}& x|r_{i-3}\text{,}& \text{(i−2)式}& \stackrel{}{\to }& x|r_{i-2}\\ x|r_{i-3}\text{,}& x|r_{i-2}\text{,}& \text{(i−1)式}& \stackrel{}{\to }& x|r_{i-1}\\ x|r_{i-2}\text{,}& x|r_{i-1}\text{,}& \text{(i)式}& \stackrel{}{\to }& x|r_i\end{array}$

以上のように、最終的には $x|r_i$ となり、

$a$ と $b$ の公約数は $r_i$ の約数である

ことが示せました。同時に、

$a$ と $b$ の公約数の最大値は $r_i$ である

ことも分かります。

---

次に、ユークリッドの互除法の最終プロセスに現れる剰余は、全てのステップの剰余の約数になっていることを示します。このことを最終ステップから順に遡って検証すると、

となり、$r_i|b$ かつ $r_i|a$、つまり、

$r_i$ は $a$ と $b$ の公約数である

ことが示せました。

---

従って、

◆	$r_i$ は $a$ と $b$ の公約数である
◆	$a$ と $b$ の公約数の最大値は $r_i$ である

の２つから、$gcd\left(a,b\right)=r_i$ が証明できました。

計算量

RSA暗号にとってのユークリッドの互除法の意味ですが、次の２つが重要です。まず第１に「２つの数の最大公約数は、素因数分解なしに計算できる」ことです。これはすなわち「２つの数が互いに素であることが素因数分解なしに示せる」ことも意味します。

我々が普通、学校で習う最大公約数の求め方は、２つの数を素因数分解して共通の素因数を探すというものでした。共通のものがなければ最大公約数は $1$（＝互いに素）です。しかし、数が巨大になると素因数分解が困難になります（それがRSA暗号が成り立つゆえんです）。ユークリッドの互除法を使うと「最大公約数」や「互いに素」が素因数分解なしに示せるのです。

第２は、ユークリッドの互除法が高速に計算できることです。ユークリッドの互除法では、一つのステップの剰余が次のステップの除数になります。次のステップの剰余は除数より小さいので、

$0<r_{i+1}<r_i$

となりますが、$r_{i+1}$ が $0$ に近いと計算は急速に収束します。また $r_{i+1}$ が $r_i$ に近い場合でも、その次のステップの商が大きくなり、$r_{i+2}$ が $0$ に近くなるので、計算は収束することになります。従って、最も計算が長引くのは、$r_{i+1}$ が $r_i$ の半分程度で、それが連続する場合だと推測できます。

実は、ユークリッドの互除法のステップが最も長くなるケースが知られています。それは 割り算の商が常に $1$ になるケースで、$a$ と $b$ が（たまたま）フィボナッチ数列の隣り合う２項だとそうなります。フィボナッチ数列とは、

$$\begin{gathered} F_0=0\text{, }{F}_1=1 \\ {F}_{n+2}=F_{n+1}+F_n \end{gathered}$$

で定義される数列で、実際に書いてみると、

$0,1,1,2,3,5,8,13,21,34,55,89,\cdots$

です。いま、$a=144$、$b=89$ としてユークリッドの互除法の計算をしてみると

となって、10ステップかかります。剰余が減る割合が常に 0.6 倍程度で、なかなか減りません。商が常に 1 なのでこうなります。しかし、なかなか減らないが毎回 0.6 倍程度にはなり、マクロ的には急速に小さくなる。証明は省略しますが、$a$ と $b$ が10進で $N$ 桁の数字でフィボナッチ数列の隣り合う２項だった場合でも、ユークリッドの互除法は $5\ast N$ ステップ以下で終了します。

これは $a$ と$b$ が300桁程度の数字のとき、それが偶然にもフィボナッチ級数の隣り合う２項であるという最悪の最悪の場合でも 1500回の割り算で終了することを意味します。この程度の計算はもちろんコンピュータで可能です。

---

本題に戻ります。最初の「RSA暗号の例題」のところで公開鍵の作り方を書きました。まず２つの素数、$p$ と $q$ を選び、$n=p·q$ とします。次に、$\left(p-1\right)\left(q-1\right)$ との最大公約数が $1$ であるような数（＝互いに素）を選び、それを $e$ とします。その $\left(e,n\right)$ のペアを公開鍵とするのでした。

$n$ と同程度の大きさの数、$e$ をランダムに選んだとき、その $e$ が $\left(p-1\right)\left(q-1\right)$ と互いに素であるかどうかは、ユークリッドの互除法で検証可能です。そしてこの検証は $p$ と $q$ が巨大な数であっても可能です。つまりユークリッドの互除法は公開鍵が現実に作成できるという数学的根拠になっています。

アルゴリズム

2.1 において、$a$ と $b$ の最大公約数は $r_i$ でしたが、この $r_i$ は (1)式における $b$ と $r_1$ の最大公約数にもなります。なぜなら、$b$ と $r_1$ の最大公約数を求めるためには (2)式から互除法の計算を始めればよく、その結果は $r_i$ になるからです。これは次を意味します。

2.1a
$a$と $b$ を自然数とし、$a>b$ とする。$a$ を $a=q·b+r\left(1\le q,0<r\right)$ と書き表せるとき、 $gcd\left(a,b\right)=gcd\left(b,r\right)$ である。

つまり、ユークリッドの互除法は

「	$a$ と $b$ の最大公約数を求める問題」を「より小さな数である $b$ と $r$ の最大公約数を求める問題」に置き換える

ものといえます。この置き換えは次々と可能で、置き換えるたびに問題がより "小さく" なっていく。これがユークリッドの互除法の本質です。

そのユークリッドの互除法は "世界最古のアルゴリズム" と言われています。そして、アルゴリズムを記述するのに最適な言語はプログラミング言語です。2.1a の考え方に基づき、ユークリッドの互除法で最大公約数を計算するプログラムを掲げます。

2.1b	アルゴリズム
ユークリッドの互除法で a と b の最大公約数を求める関数 EUCLID（Javascriptで記述） function EUCLID( a, b ) { 　if( a % b == 0 )  // ① 　　return b; 　else 　　return EUCLID( b, a % b ); }

①の "%" は Javascript の剰余演算子で、"a % b" は "a を b で割った余り" という意味です（a mod b と同じ）。なお、このプログラムは $a<b$ でも動作します。

もちろん、Javascript でなくても、C++ でも Python でも記述できます。このようにプログラムで書くと簡潔になって、ユークリッドの互除法というアルゴリズムの本質がクリアにわかります。

拡張ユークリッドの互除法

ユークリッドの互除法の "副産物" として、次の定理が成り立ちます。

2.2
$a$ と $b$ を自然数とする。このとき適当な整数 $u$、$v$ をとって、 $gcd\left(a,b\right)=u·a+v·b$ と表せる。

この定理の証明ですが、ユークリッドの互除法の計算過程を振り返ると、

$\begin{array}{llll}a& =q_1·b_{\phantom{1}}+r_1& \text{ ⋯}& \text{(1)}\\ b& =q_2·r_1+r_2& \text{ ⋯}& \text{(2)}\\ r_1& =q_3·r_2+r_3& \text{ ⋯}& \text{(3)}\\ r_2& =q_4·r_3+r_4& \text{ ⋯}& \text{(4)}\\ \text{⋮}& & & \\ r_{i-3}& =q_{i-1}·r_{i-2}+r_{i-1}& \text{ ⋯}& \text{(i−1)}\\ r_{i-2}& =q_{i\phantom{-0}}·r_{i-1}+r_{i\phantom{-0}}& \text{ ⋯}& \text{(i)}\\ r_{i-1}& =q_{i+1}·r_i& \text{ ⋯}& \text{(i+1)}\end{array}$

でした。ここで $\text{(1)}$ を変形して、

$r_1=u·a+v·b$

とします。$u=1\text{, }v=-q_1$ です。次に、今求めた $r_1$ と $\text{(2)}$ を使うと、

$r_2=u·a+v·b$

の形に表せることになります。 です。さらに、求まった $r_1$ と $r_2$ と $\text{(3)}$ を使って、

$r_3=u·a+v·b$

と表せることが分かります。このステップを順に続けていって $\text{(i)}$ まで到達すると、

$r_i=u·a+v·b$
　$u$, $v$ は $q_j\left(1\le j\le i\right)$ の式

となることがわかります。$r_i=gcd\left(a,b\right)$ だったので、2.2 が証明できました。$u$ と $v$ のうち、一つは正の整数、もう一つはゼロか負の整数です。一つがゼロであるのは、$a=b$ のときです。なお、2.2 を満たす $u$、$v$ に、

$u·a+v·b=0$

を満たす $u$、$v$ をそれぞれ足し込んでも 2.2 が成立することが明白です。つまり 2.2 を満たす $u$、$v$ は１組というわけではありません。

なお、2.2 は次のように言い換えることができます。

2.2a	不定方程式の整数解
$a$ と $b$ を自然数とする。このとき、不定方程式 $ax+by=gcd\left(a,b\right)$ は整数解をもつ。

拡張ユークリッドの互除法のアルゴリズム

ユークリッドの互除法を拡張して、$a$ と $b$ が与えられたとき、$\gcd \left(a,b\right)$ と、

$au+bv=gcd\left(a,b\right)$

を満たす $u$ と $v$（＝無数にある解のうちの一つのペア）を同時に計算してしまうアルゴリズムを考えてみます。

考え方は 2.1b のユークリッドの互除法と同じで、解くべき問題を「等価でより小さな問題」に置き換えます。そのために $a=qb+r$ とおくと、2.1aより、

$gcd\left(a,b\right)=gcd\left(b,r\right)$

なので、問題は次のように書き換えられます。

$\left(qb+r\right)u+bv=gcd\left(b,r\right)$

ここで、未知数の $u$ と $v$ を次のように変換します。

$$\begin{gathered} u=V \\ v=U-qV \end{gathered}$$

これを代入して式を整理すると

$bU+rV=gcd\left(b,r\right)$

となり、"小さな問題" に変換することができました。この考え方でアルゴリズムを記述すると次のとおりです。

2.2b	拡張ユークリッドの互除法
a と b から拡張ユークリッドの互除法で（u, v, 最大公約数）の３つを同時に求める関数 extdEUCLID（Javascriptで記述） function extdEUCLID( a, b ) { 　var r = a % b;  // ① 　if( r == 0 ) 　　return { u : 0, v : 1, gcd : b };  // ② 　else { 　　var q = Math.floor( a / b );  // ③ 　　var s = extdEUCLID( b, r );  // ④ 　　return { 　　　u : s.v,  // ⑤ 　　　v : (s.u - q * s.v),  // 　　　gcd : s.gcd  // 　　}; 　} }

以下は、このアルゴリズムの補足説明です。

①	var：変数の宣言。%：剰余演算子。
②	a が b で割り切れるなら解が求まる。自然な解を関数値として返す。関数値は３つの変数（u, v, gcd）をひとまとめにしたオブジェクト。
③	商を求め、小数点以下を切り捨て整数化する。Javascript には実数・整数の区別がないので整数化（組み込み関数の Math.floor）が必要。
④	小さな問題として計算する。
⑤	変数を元に戻して、関数値（u, v, gcd）を返す。

この拡張ユークリッドの互除法のアルゴリズムは、2.1b のユークリッドのアルゴリズムとほぼ同じです。ただし、$u$ と $v$ の計算のために変数を変換しているので、最大公約数を計算したあとに元の変数値を求める必要があります（＝⑤）。そこが違います。

このことから、拡張ユークリッドの互除法の計算量は、ユークリッドの互除法のほぼ２倍だと推測できます。計算は少々複雑になりますが、たとえ $a$ や $b$ が巨大な数であっても、コンピュータで高速に計算できる。このことは次の「整数の逆数」の項で述べるように、RSA暗号にとっての重要ポイントになります。

整数の逆数

2.2 から導かれる次の定理は、RSA暗号にとって重要です。

2.3	逆数の存在定理
$gcd\left(a,m\right)=1$ なら（＝ $a$ と $m$ が互いに素なら）、 $a·b\equiv 1\left(modm\right)$ となる $b$ が存在する。この $b$ は $1\le b<m$ の範囲では一意に定まる（＝ $m$ を法として唯一）。

2.2 において $a$と互いに素な数 $m$ を選び、$b=m$ とおくと、$gcd\left(a,m\right)=1$ なので、適当な $u$ と $v$ をとることにより、

$u·a+v·m=1$

とすることができます。すなわち、

$a·u\equiv 1\left(modm\right)$

となり、2.3 が示されました。2.3 において $b_1$ と $b_2$ の２つの解があるとすると、

$$\begin{gathered} a·b_1\equiv 1\left(modm\right) \\ a·b_2\equiv 1\left(modm\right) \\ a\left(b_1-b_2\right)\equiv 0\left(modm\right) \\ m|a\left(b_1-b_2\right) \end{gathered}$$

となり、$a$ と $m$ は互いに素なので 1.3a より、

$$\begin{gathered} m|\left(b_1-b_2\right) \\ {b}_1\equiv b_2\left(modm\right) \end{gathered}$$

となります。従って、$1\le b<m$ の範囲に $b$ があり、かつ、この範囲で $b$ は一意に定まります。$m$ を法として $b$ と合同な数も解であることは明白ですが、それらの解は $m$ を法として唯一です。

---

2.3 の "逆数" を計算するアルゴリズムは、拡張ユークリッドの互除法2.2 のアルゴリズム（2.2b）と基本的に同じです。

2.3	逆数の計算アルゴリズム
m を法とする a の逆数を求める関数 INVERSE（Javascriptで記述） function INVERSE( a, m ) { 　var b = extdEUCLID( a, m ).u % m; // ① 　if( b < 0 ) b = b + m; 　return b; // 　function extdEUCLID( a, b ) { 　　var r = a % b; 　　if( r == 0 ) 　　　return { u : 0, v : 1, gcd : b }; 　　else { 　　　var q = Math.floor( a / b ); 　　　var s = extdEUCLID( b, r ); 　　　return { 　　　　u : s.v, 　　　　v : (s.u - q * s.v), 　　　　gcd : s.gcd 　　　}; 　　} 　} // extdEUCLID 終わり // } // INVERSE 終わり

①で、extdEUCLID のアルゴリズム（2.2b）を使って $u$ を求め、それを $m$ 未満の自然数に直して答えの $b$ を求めています。このアルゴリズムは正確に言うと、$a$ と $m$ が与えられたとき、

$a·b\equiv gcd\left(a,m\right)\left(modm\right)$

となる $b$ を求めるアルゴリズムです。$a$ と $m$ が互いに素でなくても成立します。

---

この "逆数の存在定理" は RSA暗号において秘密鍵の算出に使われています。冒頭の「RSA暗号の例題」に書いたように、RSA暗号の公開鍵と秘密鍵は、まず秘密の２つの素数 $p$ と $q$ を決め、

$n=p·q$

とします。そして $e$ を、

$gcd\left(e,\left(p-1\right)\left(q-1\right)\right)=1$

となるように決め、$n$ と $e$ を公開鍵とするのでした。そして秘密鍵 $d$ を、

$d·e\equiv 1\left(mod\left(p-1\right)\left(q-1\right)\right)$

を満たす数とします。この秘密鍵 $d$ の計算は、$mod\left(p-1\right)\left(q-1\right)$ の世界で $e$ の逆数を求めていることに他なりません。逆数の存在が保証されるのは、$e$ を $\left(p-1\right)\left(q-1\right)$ と互いに素という条件で決めたからです。さらに、この逆数の計算アルゴリズムは 2.2b の拡張ユークリッドの互除法と同じなので高速に計算できることが重要ポイントです。

---

普通、整数の "逆数"は（整数の範囲で）定義できません（1以外は）。しかし、"$modm$ の合同の世界" では、$m$ と互いに素な数 $a$ に対して逆数が定義できることになります。つまり整数の範囲で「割り算」が定義できる。

たとえば $mod10$ の世界では $7\times 3=1$ であり、$7$ の逆数は $3$ です。割り算は逆数のかけ算なので、たとえば $8÷7=8\times 3=4$（$mod10$ の世界）といった演算が定義できます。"検算" をすると $4\times 7=8$（$mod10$ の世界）なので合っています。

$mod10$ の場合は実用的な意味はありませんが、$p$ を素数としたとき「$modp$ の世界」は大変重要です。というのも $p$ 未満の自然数はすべて $p$ と互いに素だからです。つまり $p$ 未満の全ての自然数に対して "逆数" が定義できる。ということは、$p$ 未満の２つの自然数の "除算" が定義できます。さらに、$0$ と $p$ 未満の自然数を合わせると加減乗除が行えることになります。

加減乗除が定義された集合を「体（Field）」と呼びます。有理数、実数、複素数は「体」ですが、「$0$ と $p$ 未満の自然数」も体になります。これを ${\mathbb{F}}_p$ と表記します。この集合の要素の数は有限個なので「有限体」です。 ${\mathbb{F}}_{13}$ の場合（$mod13$）で "逆数" の計算をしてみると、

$\begin{array}{rr}1·& 1\equiv 1\left(mod13\right)\\ 2·& 7\equiv 1\left(mod13\right)\\ 3·& 9\equiv 1\left(mod13\right)\\ 4·& 10\equiv 1\left(mod13\right)\\ 5·& 8\equiv 1\left(mod13\right)\\ 6·& 11\equiv 1\left(mod13\right)\\ 7·& 2\equiv 1\left(mod13\right)\\ 8·& 5\equiv 1\left(mod13\right)\\ 9·& 3\equiv 1\left(mod13\right)\\ 10·& 4\equiv 1\left(mod13\right)\\ 11·& 6\equiv 1\left(mod13\right)\\ 12·& 12\equiv 1\left(mod13\right)\end{array}$

となり、$0$ 以外の ${\mathbb{F}}_{13}$ の要素は、その逆数（＝逆元）と１対１に対応していることがわかります。

${\mathbb{F}}_p$ においては "整数 "の加減乗除を "自由かつ厳密に" 行うことができます。これは、全ての情報を２進数に帰着させて扱うデジタル・コンピュータとの相性がよい。このため、公開鍵暗号の中には ${\mathbb{F}}_p$ の演算を利用したものがあります。

なお、$p$ を素数としたとき「$p$ 未満の自然数はすべて $p$ と互いに素」ということは「$\left(p-1\right)!$ と $p$ は互いに素」ということです（" $!$ " は階乗記号）。これは次の「フェルマの小定理」の証明に出てきます。

（次回に続く）

---

タグ：JavaScript 素数 アルゴリズム 素因数分解 最大公約数 合同 平文 RSA暗号 フィボナッチ数列 公開鍵 公約数 ヘルマン 暗号文 累乗 約数 秘密鍵 公開鍵暗号 ディフィー リベスト シャミア エーデルマン 冪乗 因数 合成数 互いに素 ユークリッドの互除法 拡張ユークリッドの互除法