不定方程式と拡張ユークリッドの互除法
こんにちは。前回の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の「整数の性質」では定番の問題になります。
不定方程式の解法
手元にある数学の参考書を見て見つけたうちの２つの解法を紹介します。
係数下げによる解法
\(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)\)の一組の解を求めることができます。
- 初期値として、\(r_0 =a,r_1=b\)，\(u_0=1,u_1=0\)，\(v_0=0,v_1=1\)とします。\(ここで、a>bとします\)
- \(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を実行します。
- \(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\)が求められます。
今回はこれでおしまい。それではまた。