なかなか興味深いバグが発生した。GCDが-1になるとは。
だいたい互除法のアルゴリズムは自然数を前提としているのではないか、そこをそのままパクってきて整数係数の多項式に使おうというのだから、当然マイナスには対応するべきであった。
一方、1がすべての整数の共通の因子であるように、-1もまた共通因子である。たとえばGCD(-7, -3)とかだったら-1を返したくなるし、GCD(-7, 3)のときはどうするとか悩むだろう。普通は自然数だけを考えればいいが、多項式の場合は係数を自然数に限定することはできない。なのでマイナスの場合を考えなければならないのだ。そしてGCD(-7, -3)でも1を返すのがたぶん正しい。
このバグが直れば、無平方分解まで行ける。たぶん。