Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

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

応用代数学入門 Ruby Book

練習問題3.3

問2

d=gcd(43,56)と、整数xとyでd=43x+56yとなるものを、後退代入を用いて求めなさい。

解答

a=43,b=56とする。このとき、

 {
\begin{eqnarray}
56 & = & 43\cdot 1+13 \\
43 & = & 13\cdot 3+4 \\
13 & = & 4\cdot 3+1 \\
4 & = & 1\cdot 4+0
\end{eqnarray}
}

となるので

 {
\begin{eqnarray}
1 & = & 13 - 4\cdot 3 \\
& = & 56-43\cdot 1-(43-13\cdot 3)\cdot 3 \\
& = & 56-43\cdot 1-\{43-(56-43\cdot 1)\cdot 3\} \cdot 3 \\
& = & 56-43\cdot 1 - (43\cdot 3-56\cdot 9+43\cdot 9) \\
& = & 56-43\cdot 1-(43\cdot 12 - 56\cdot 9) \\
& = & 56\cdot 10 - 43\cdot 11 \\
\end{eqnarray}
}

であり、よって

 {
\begin{eqnarray}
1 & = & 43\cdot (-11) + 56\cdot 10 \\
\end{eqnarray}
}

となる。

問4

数式処理システムを用いることにより、整数d,x,yで

{ \displaystyle \begin{eqnarray} d = gcd(742789479, 9587374758) = 742789479x + 9587374758y \end{eqnarray} }

となるものを求めなさい。

解答

よって、

{ \displaystyle 3 = 742789479\cdot(-1357468553) + 9587374758\cdot105170955 }

となる。

応用代数学入門―暗号・符号・バーコードの仕組みが分かる

応用代数学入門―暗号・符号・バーコードの仕組みが分かる

  • 作者: ダレル・W.ハーディ,キャロル・L.ウォーカー,Darel W. Hardy,Carol L. Walker,鈴木治郎
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2005/12
  • メディア: 単行本
  • クリック: 3回
  • この商品を含むブログ (10件) を見る