Half GCD

Half GCD は、Euclid の互除法を分割統治的に高速化するためのアルゴリズムです。

CTF では、多項式や大きな整数の最大公約数計算を含む数論・暗号問題で扱われることがあります。