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