しまった. nを素数にするとFFTが使えない. となると, 計算量はO(n^2 log^c n)か. メリットが消えてしまうな. 直そう. 直ったかと思ったがダメぽい? n=2^kとして, x^n+1はZ上既約. また2nがq-1を割り切らないとき, Zq上でも既約かと思ったがそうではない. 根…

ref:わたしが知らないスゴ本は、きっとあなたが読んでいる: 数学ぎらいは幸せになれないか? 「生き抜くための数学入門」のコメント欄.簡便のため, Nは0を含むとする. 数学的な記法で表すと以下になる. 証明 任意の自然数について, であることは明らか. 以下,…