割り切れるかどうか判定したい!!
暗号やアルゴリズムの分野では、よく割り切れるかどうかというのが問題になります。有名なもので言えば、RSA暗号では、巨大な素数を使い、公開鍵と秘密鍵を用いた暗号化と復号の仕組みとして使われたりします。
暗号を取り扱う上でも、一般的なアルゴリズムを扱う上でも必須ツールとして使われているユークリッドの互除法について、図解しながら紹介し、それを改良した拡張ユークリッドの互除法も理解していきましょう。
ユークリッドの互除法
ユークリッドの互除法とは、二整数の最大公約数を求める高速なアルゴリズムです。
\[ gcd(a,b) = x \]
\(gcd()\) : ユークリッドの互除法
\(a , b \) : 整数
\(x \) : \(a , b \) の最大公約数
つまり、暗号使うような、互いに素である二整数であるかを判定したければ、ユークリッドの互除法で求めた最大公約数が”１”であればいいということですね。
ユークリッドの互除法のアルゴリズムと図解
使い道や利用法を見る前に、アルゴリズムの理解しましょう。
ユークリッドの互除法のアルゴリズムは、入力された２整数の片方をもう片方で割り、その余りを評価するという手順を何回も繰り返します。
ユークリッドの互除法のアルゴリズム
function gcd (a,b) : integer :
var w : integer
begin
while b \(\ne\) 0 do
begin
w: = a mod b;
a: = b;
b: = w;
end;
gcd : = a;
end;
アルゴリズムの操作を図解
取りあえず例題をもとにユークリッドの互除法を適用して、最大公約数を求めます。その後、例題の各々の動作を図解してみます。
例題：161と28の最大公約数を求めよ。
１．まず、161 を28で割り、あまりを求めます。
\[161\mod 28 = 21\]
余りが0でないので続ける。
2．次に、先ほどの除数 28 をあまり21で割り、あまりを求めます。
\[28 \mod 21 = 7\]
余りが0でないので続けます。
3．先ほどの除数 21 をあまり7で割り、あまりを求めます。
\[21 \mod 7 = 0\]
余りが0になったので、最大公約数が求まりました。最大公約数は “7”です。
検証 (本当に正しいの？)
ユークリッドの互除法で最大公約数が“7”と求まりましたが、本当に正しいのでしょうか？
\[ 161 \div 7 = 23 あまり 0 \]
\[ 28 \div 7 = 4 あまり 0 \]
161と28を7で割ってみれば、割り切れることが確認できます。公約数であることは確認できました。
では、最大公約数なのでしょうか？ 28の約数は 28 14 7 4 2 1 です。(完全数で綺麗ですね。)
161を28で割っても割り切れないことは 上の1.ステップで分かっているので、14で割り切れるか確認してみます。
\[ 161 \div 14 = 11 あまり 7\]
割り切れませんでした。これで、161と28の最大公約数が “7”であり、ユークリッドの互除法で求めたものと一致することが確認できました。
図にすると？
計算で一致することは確認できましたが、これは常に正しいのでしょうか？
これは図にしてみるとわかりやすいので図示してみます。
図を見れば、ユークリッドの互除法を順次行い、最終的にあまりが0になった時、一つ前のステップで除数(割る数)になっていたものを余りが０になった時の除数で置き換えることができることがわかります。
(図の右下の緑と青色の部分 緑＝青×３)
（約数である説明）
順次置き換えていけば、最終的に、ちょうど余りが0になった時の除数の整数倍で初めの2整数を表すことができることがわかると思います。
(図の右上 緑＝青×３、オレンジ＝緑×２＋青＝青×７、赤＝オレンジ＋緑＝青×１０)
（最大の約数である説明）
また、この図で出てきた各数(赤、オレンジ)について、もし、最大公約数が存在したとしたら、必ずこれらすべてを最大公約数で割り切れないといけません。これは、途中で出てきた余り（緑）でも成り立たなければならず。一番初めてちょうど割り切れるあまり（青）が出てきたら、これが最大のものになるはずです。
これが、ユークリッドの互除法で最大公約数を求められる仕組みです。
判定だけでは終われない？
ユークリッドの互除法を行ってみて、最終的に最大公約数が”1“になったら、２つの数が「互いに素である（最大公約数が1）」であることがわかります。
ユークリッドの互除法の利用用途
- ２つの数が「互いに素であるかどうか」を高速に判定
ユークリッドの互除法・乗法的逆元
最大公約数を求められるということは分かったと思いますが、ユークリッドの互除法をアルゴリズムを少し改良すると、乗法的逆元を求めることができます。
この改良したユークリッドの互除法を拡張ユークリッドの互除法と言います。
拡張ユークリッドの互除法で分かること
- aとnが互いに素であれば、法nにおける乗法的逆元が存在する。
つまり、
\[ ax \equiv 1 \mod n \]
これはどういうものでしょうか？また、どんな場面で便利なのでしょうか？
割り算ができない世界での「割り算」？ — 乗法的逆元のお話
乗法的逆元と聞きなれない漢字5文字が出てきて身構えたかもしれませんが、そこまで難しいものではありません。
通常の逆数、(狭義における逆数)は 数で、1を割った時の値でしたね。
この１を割るという操作の解釈を広げたものが専門用語では「乗法的逆元（じょうほうてきぎゃくげん）」と呼ばれます。暗号の世界（余りの計算の世界）における「割り算」を可能にするために必須になる考え方です。
(電子回路や情報のビット計算を知っている人なら、補数をイメージするとこの先の説明がわかりやすいかもしれません。)
以降順を追いながら、乗法的逆元を紹介します。
1. 普通の世界の「逆元」
私たちが普段使っている数の世界で、次の方程式を解いてみましょう。
\(5 \times x = 1\)
答えは簡単ですね。\(x = \frac{1}{5}\)（つまり \(0.2\)）です。
「掛けると \(1\) になる数」のことを、数学では逆数（逆元）と呼びます。
「\(5\) で割る」ということは、「逆数の \(\frac{1}{5}\) を掛ける」ことと同じ意味でしたね。
2. 余りの世界の「逆元」
では、暗号で使う「整数の余りの世界（mod）」ではどうなるでしょうか？
ここでは小数や分数は使えません。「整数」しか存在しない世界です。
例えば、「時計の文字盤（mod 13）」の世界で考えてみましょう。
ここで、さっきと同じ式を考えてみます。
\[3 \times x \equiv 1 \pmod{13}\]
「\(3\) に何か整数を掛けたら、13で割って \(1\) 余る数になる」ような \(x\) はあるでしょうか？
順番に試してみましょう。
- \(3 \times 1 = 3\)
- \(3 \times 2 = 6\)
- \(3 \times 3 = 9\)
- \(3 \times 4 = 12\)
- \(3 \times \mathbf{9} = 27\)
- \(27 \div 13 = 2\) あまり \(\mathbf{1}\)
見つかりました！ 9 です。
つまり、mod 13の世界では、「3 の逆元は 9」ということになります。
3. これがなぜ「割り算」になるの？
これがわかると何が嬉しいのでしょうか？
例えば、暗号の計算中に「ある数を 3 で割りたい（3分の1したい）」という場面が出てきたとします。
でも、この世界に小数は存在しません。
そこで、「3で割る」代わりに「逆元の 9 を掛ける」のです。
すると、不思議なことに割り算をしたのと全く同じ結果が得られます。
「割り算はできないけれど、逆元を探して掛ければ、実質割り算できる！」
暗号の世界のルール：「割り算はできないけれど、逆元を探して掛ければ、実質割り算できる！」
といった感じで、modの世界における逆数のことを乗法的逆元と言います。
拡張ユークリッドの互除法
拡張ユークリッドの互除法でできること
- 乗法的逆元があるかどうか判定
乗法的逆元を求めるとき、時計盤などの小さい数 13と3などなら総当たり的に求めても問題ないですが、RSA暗号のように桁数が数百桁になると、総当たりでは何億年もかかってしまいます。
拡張ユークリッドの互除法では、ユークリッドの互除法のアルゴリズム中でちょっと工夫をすることで、最大公約数を求めると同時に乗法的逆元を高速に求めることができます。
拡張ユークリッドの互除法のアルゴリズム
function inv (a,n) : integer :
var q,s,t,u,v,w : integer
begin
s := a, t:=n,
u: = 1,v:=0;
while s > 0 do
begin
q: = t div s;
w: = t – q*s; //コメント: w = t mod s と同じ
t: = s; s: = w; //ここまででユークリッドの互除法
w: = v + q*u; //拡張部分
v: = u; u:=w //拡張部分
end;
if v < 0 then inv := v+n else inv :=v;
end;
拡張ユークリッドの互除法アルゴリズムを考える
拡張ユークリッドの互除法のアルゴリズムを見てみると、変数が増えましたが、
q: = t div s;
w: = t – q*s;
t := s; s := w;
の部分は、割り算をして商\(q\)を求め、割った元の値から割り切れた分を引いて、変数においておく、という処理なので、ユークリッドの互除法そのままですね。
この時、割り算の商を\(q\)として、後から使えるのが拡張ユークリッドの互除法の肝になります。
乗法的逆元を求める仕組み
拡張ユークリッドの互除法の乗法的逆元を求める部分は、割り算の商\(q\)を使って計算します。
逆算していくと、なぜ求まるのか分かるので、ユークリッドの互除法の例に挙げた 28と161の計算を例に考えてみます。
【Step 1：普通の互除法（時間を進める）】
まずは、通常通り余りを求めていきます。
- \(161 = 28 \times 5 + 21\)
- \(28 = 21 \times 1 + 7\)
- \(21 = 7 \times 3 + 0\) （終了！最大公約数は7）
【Step 2：式の変形（準備）】
ここで、1.と2.の式を「余り \(= \dots\)」の形に変形しておきます。これがパズルのピースになります。
- 式A： \(21 = 161 – 28 \times 5\)
- 式B： \(7 = 28 – 21 \times 1\)
【Step 3：拡張ユークリッドの互除法（時間を巻き戻す）】
ここからが拡張版の真骨頂です。一番下の式からスタートして、上の式を次々に代入していきます。
- まず、最大公約数が出た式（式B）を用意します。
\[ 7 = 28 – \mathbf{21} \times 1 \]
- この式の \(\mathbf{21}\) の正体は、一つ前のステップ（式A）で作られたものでしたね？ これを代入します。
\[ 7 = 28 – (\mathbf{161 – 28 \times 5}) \times 1 \]
- あとは式を整理するだけです。（28と161を文字だと思って整理します）
\[ 7 = 28 – 161 \times 1 + 28 \times 5 \]
\[ 7 = 28 \times (1 + 5) – 161 \times 1 \]
\[ \mathbf{7 = 28 \times 6 – 161 \times 1} \]
なんと！ 式を変形していっただけで、
「\(28\) を \(6\) 倍して、\(161\) を \(1\) 倍したものを引くと、最大公約数の \(7\) になる」
という式が導き出せました。
結局、どうやって「乗法的逆元」になるの？
さて、この計算がどうして「暗号の鍵（乗法的逆元）」を見つけることになるのでしょうか？
もし、計算した２つの数が互いに素（最大公約数が 1）だった場合を想像してみてください。
先ほどのゴールの式が、\(7\) ではなく \(1\) になります。
例えば、\(a\) と \(n\) という数字で計算して、以下のような結果が出たとします。
\[ a \times x + n \times y = 1 \]
この式の両辺を \(n\) で割った余り（mod \(n\)）を考えてみましょう。
\(n \times y\) の部分は \(n\) の倍数なので、余りは \(0\) になって消えます。すると……
\[ a \times x \equiv 1 \pmod n \]
これはまさに、「\(a\) に \(x\) を掛けたら（\(n\)で割った余りが）\(1\) になる」という、乗法的逆元の定義そのものです。
つまり、拡張ユークリッドの互除法とは、
- \(ax + ny = \gcd(a, n)\) を満たす \(x\) と \(y\) を無理やり見つけ出し、
- その \(x\) こそが、実は私たちが探していた「乗法的逆元（魔法の数字）」だった！
というアルゴリズムだったわけですね。
まとめ
ユークリッドの互除法と拡張ユークリッドの互除法について理解できたでしょうか？
ユークリッドの互除法では、乗除をうまく行うことで単純な仕組みながら最大公約数を求めることができ、拡張ユークリッドの互除法では、ユークリッドの互除法で途中で出てくる商などの値を用いて乗法的逆元を求めることができるというアルゴリズムでした。
RSA暗号のような巨大な数でも、この「割り算の逆戻り」を行うだけで、一瞬で秘密鍵を見つけ出すことができるため。とても有用なアルゴリズムであることが理解できたと思います。
- ユークリッドの互除法(gcd)：割り算を繰り返して、最大公約数を見つける（判定する）。
- 拡張ユークリッドの互除法(inv)：計算の過程を逆にたどって、$ax + by = \gcd(a,b)$ の解を見つける（構成する）。
一見難しそうなアルゴリズムも、図に描いて「式変形のパズル」として捉えると、先人の知恵の凄さがわかりますね。
ここまで読んでいただきありがとうございます。
では、次の記事で。 lumenHero
関連記事
換字式暗号 -シーザー暗号より強い、アフィン変換型の換字式暗号-【ANGOUのすゝめ】#4
シーザー暗号は「足し算」でしたが、「掛け算」を使うとどうなる？乗算型暗号の仕組みと、鍵の条件「互いに素」、鍵の個数を導く「オイラーのφ関数」を解説。さらに両者を組み合わせた「アフィン暗号」の強度に迫ります。
