お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

不定方程式と拡張ユークリッドの互除法

数学

こんにちは。前回のRSA暗号で\(ed \equiv 1 \bmod \varphi(N)\)を満たす\(d\)を求めることにより、秘密鍵を作る手順になっているところがありました。今回は\(d\)を求めるアルゴリズムについて取り上げます。

RSA暗号と不定方程式

先ほどの\(ed \equiv 1 \bmod \varphi(N)\)では一般化しすぎているので、具体的な値を用いて話を進めます。前回使った値\(e=7,N=11 \times 13=143,\varphi(N)=(11-1)(13-1)=120\)では、案外簡単に求まってしまうため、\(e=31\)に変更して、\(31d \equiv 1 \bmod 120\)を満たす\(d\)を求めることを考えます。この式は、\(31d\)を\(120\)で割った余りが\(1\)になることを示しています。これを満たす\(d\)の一つを求めるために、\(120u+31d=1\)と変形して不定方程式にします。(\(u,d\)は整数)式が大きく異なるように見えますが、同じ意味をもっています。\(120u\)は\(120\)の倍数になるので、\(120\)で割ったときに割り切れます。合同式の右辺\(1 \bmod 120\)は\(120\)で割った余りが\(1\)なので、無数にある余りが\(1\)となる\(d\)の中から、ちょうど\(1\)になるものを選べばよいことになります。これにより変形された\(120u+31d=1\)を満たす整数解\(u,d\)を求める問題は不定方程式といわれており、2012年度から実施されている数学Aの「整数の性質」では定番の問題になります。

不定方程式の解法

手元にある数学の参考書を見て見つけたうちの2つの解法を紹介します。

係数下げによる解法

\(120=31\times3+27\)が成り立つので、\(120u+31d=1\)は

\[ \begin{eqnarray} (31 \times 3+ 27)u+31d &=& 1 \\ 31(3u+d)+27u&=&1 \end{eqnarray} \]

となります。ここで、\(v=3u+d\)とおくと、\(31v+27u=1\)と変形できます。

次に、\(31=27\times1+4\)が成り立つので、\(31v+27u=1\)は

\[ \begin{eqnarray} (27 \times 1+ 4)v+27u &=& 1 \\ 27(v+u)+4v&=&1 \end{eqnarray} \]

となります。ここで、\(w=v+u\)とおくと、\(27w+4v=1\)と変形できます。

さらに、\(27=4\times6+3\)が成り立つので、\(27w+4v=1\)は

\[ \begin{eqnarray} (4 \times 6+ 3)w+4v &=& 1 \\ 4(6w+v)+3w&=&1 \end{eqnarray} \]

となります。ここで、\(x=6w+v\)とおくと、\(4x+3w=1\)と変形できます。

次に、\(4=3\times1+1\)が成り立つので、\(4x+3w=1\)は

\[ \begin{eqnarray} (3 \times 1+ 1)x+3w &=& 1 \\ 3(x+w)+x&=&1 \end{eqnarray} \]

となります。ここで、\(k=x+w\)とおくと、

\[ \begin{eqnarray} 3k+x&=&1 \\ x&=&-3k+1\end{eqnarray} \]

とできます。\(k=x+w\)なので、

\[ \begin{eqnarray} k&=&x+w \\ k&=&-3k+1+w \\ w&=&4k-1 \end{eqnarray}\]

となります。さらに、\(x=6w+v\)なので、

\[ \begin{eqnarray} x&=&6w+v \\ -3k+1&=&6(4k-1)+v \\ v&=&-27k+7 \end{eqnarray}\]

となります。さらに、\(w=v+u\)なので、

\[ \begin{eqnarray} w&=&v+u \\ 4k-1&=&-27k+7+u \\ u&=&31k-8 \end{eqnarray}\]

となります。さらに、\(v=3u+d\)なので、

\[ \begin{eqnarray} v&=&3u+d \\ -27k+7&=&3(31k-8)+d \\ d&=&-120k+31 \end{eqnarray}\]

となります。よって

\[\begin{eqnarray} \left\{ \begin{array}{l} d=-120k+31 \\ u = 31k-8 \end{array} \right. \end{eqnarray}(kは整数)\]

が求まります。ここで、\(k=0\)とすると、\(d=31\)という秘密鍵が求められます。

互除法を用いた解法

\(120u+31d=1\)で、\(m=120,n=31\)とします。

\(120=3 \times 31 + 27\)となるので、\(27 = 120 – 3 \times 31=m-3n\)となります。

\(31=27\times 1+4\)となるので、\(4=31-27\times 1=n-(m-3n)=-m+4n\)となります。

\(27=4\times 6+3\)となるので、\(3=27-4\times 6=(m-3n)-(-m+4n)\times 6=7m-27n\)となります。

\(4=3\times 1+1\)となるので、\(1=4-3\times 1=(-m+4n)-(7m-27n)=-8m+31n\)となります。

\(m=120,n=31\)としたので、\(-8\times 120 + 31 \times 31 =1\)が成り立ちます。

\(\begin{eqnarray} 120u + 31d &=& 1 \\ -8 \times 120 + 31 \times 31 &=& 1 \end{eqnarray}\)

の辺々を引くと\(120(u+8)+31(d-31)=0\)、すなわち\(120(u+8)=-31(d-31)\)が成り立ちます。

\(120\)と\(31\)は互いに素なので、\(k\)を整数として\(u+8=31k\)、\(d-31=-120k\)が求まります。

よって

\[\begin{eqnarray} \left\{ \begin{array}{l} d=-120k+31 \\ u = 31k-8 \end{array} \right. \end{eqnarray}(kは整数)\]

が求まります。

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

ユークリッドの互除法を拡張することで、不定方程式\(ax+by=\mathrm{GCD}(a,b)\)の一組の解を求めることができます。

  1. 初期値として、\(r_0 =a,r_1=b\),\(u_0=1,u_1=0\),\(v_0=0,v_1=1\)とします。\(ここで、a>bとします\)
  2. \(q_i\)は\(r_{i-2}\)を\(r_{i-2}\)を\(r_{i-1}\)で割った商,\(r_i=r_{i-2}-q_i r_{i-1}\)とします。\(r_i=0\)ならば,3に進みます。\(r_i \neq 0\)ならば,\(u_i=u_{i-2}-q_iu_{i-1}\),\(v_i=v_{i-2}-q_iv_{i-1}\)を計算して,再度2を実行します。
  3. \(x=u_{i-1},y=v_{i-1}\)が一組の解になります。

これを用いて,先ほどの\(120u+31d=1\)を解いてみましょう。

\(r_i\) \(q_i\) \(u_i\) \(v_i\)
\(r_0=120\) \(u_0=1\) \(v_0=0\)
\(r_1=31\) \(u_1=0\) \(v_1=1\)
\(r_2=27\) \(q_2=3\) \(u_2=1\) \(v_2=-3\)
\(r_3=4\) \(q_3=1\) \(u_3=-1\) \(v_3=4\)
\(r_4=3\) \(q_4=6\) \(u_4=7\) \(v_4=-27\)
\(r_5=1\) \(q_5=1\) \(u_5=-8\) \(v_5=31\)
\(r_6=0\) \(q_6=3\)

となり、一組の解\(u=-8,v=31\)が求められます。

今回はこれでおしまい。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai