ユークリッドの互除法とは？

ユークリッドの互除法の意味

2数の最大公約数を、大きい方を小さい方で割った余りに置き換える操作の繰り返しで求める古典的アルゴリズム。応用情報では、アルゴリズムのトレース問題や、拡張版が公開鍵暗号の鍵生成に使われる例として出る。

ユークリッドの互除法の具体例

gcd(1071,462) は 1071 mod 462＝147、462 mod 147＝21、147 mod 21＝0 となり21。計算量は O(log min(a,b)) で、両者を素因数分解して共通因数を探す方法より桁違いに速い。

ユークリッドの互除法は試験でどう引っ掛けられる？

引き算を繰り返す版と余りを使う版があり、前者は2数の差が大きいと極端に遅くなる。最小公倍数は a×b÷gcd で求まるが、先に掛けると桁あふれしやすいので a÷gcd×b の順に計算する。

ユークリッドの互除法と関連する用語

• 公開鍵暗号方式（RSA）
• 計算量とO記法（オーダ記法）

ユークリッドの互除法が出た過去問

• 次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x,y)はxをyで割った余りを返す。

  正解：aとbの最大公約数

  要点：ユークリッドの互除法は余りの繰返しで最大公約数を求める

  xをyで割った余りをとり、yを新しいx、余りを新しいyとする操作を余りが0になるまで繰り返すのはユークリッドの互除法である。終了時のxには最後に割り切れたときの除数が入っており、これがaとbの最大公約数になる。例えばa=12、b=18なら計算を追うと6が残る。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問3（IPA）