ユークリッドの互除法とは？
ユークリッドの互除法とは、2数の最大公約数を、大きい方を小さい方で割った余りに置き換える操作の繰り返しで求める古典的アルゴリズム。応用情報では、アルゴリズムのトレース問題や、拡張版が公開鍵暗号の鍵生成に使われる例として出る。
ゆーくりっどのごじょほう
ユークリッドの互除法の意味
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 の順に計算する。
ユークリッドの互除法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。