SageMathというのはオープンソースの数式処理システムで、Pythonと周辺のライブラリをうまく拡張して作られていて便利なので、CTFの特にCrypto分野では重宝します。

Half-GCDというのは（特に上の）2つの一変数多項式のGCDを求めるアルゴリズムで、愚直なユークリッドの互助法に比べて多くの場合高速に動作するのが便利で、多項式の次数が大きいとき、計算を現実的な時間で終わらせるための工夫として用いられます。詳しくは 多項式GCD | Nyaan’s Library やhalf-GCD - 37zigen's project を参照ください（私は理解してません）。

Half-GCDは（アルゴリズムとしては以前からあったものの）、CTFのCrypto分野ではここ数年で有名になったテクニックで、時折このアルゴリズムを利用してうまく高速に解くことが求められる問題が出題されます。既に幾度か出題されたこともあって、SageMath実装が世に出回っているのでそれをコピペするだけで利用可能ではあるのですが、多種多様なアルゴリズムを利用できるSageMathでHalf-GCDが標準搭載されていないというのも不思議な話です。

不思議な話と思って調べて見たのですがissueは既にあって実装も進んでいるものの、既存の実装と衝突する部分があり本体に取り込むには至っていないようでした。最近の様子をみると、リリース予定がどんどん後ろに倒れてついには予定がなくなってしまっており悲しい…。

ところでこのissueで参照されている実装を眺めていたところ、SageMathが利用しているライブラリであるPARIではHalf-GCDが実装されていて、これをSageMathから使うことは簡単そうだということがわかりました。

以下のように使えます。プライベートなメソッドを利用しているのがちょっと心苦しいところですが、これまで 60 - 70行の実装をコピペしていたところが1行の呼び出しで済んでしまうので楽ですね。

PR.<x> = PolynomialRing(Zmod(N))
f1 = x**e - c1
f2 = (x + a)**e - c2

g = PR(f1._pari_with_name('x').gcd(f2._pari_with_name('x')))

早く本体に取り込まれて欲しい。応援しています