数学：微分すると０

ネタがないので、因数分解振り返り。最初はバグかと思ったのだが、mod $p$ の世界の多項式は、定数項のみでなくても微分すると $0$ になることがある。これは Cantor-Zassenhaus の論文に書いてあった。論文に書くほどのことではない気がするが、親切にもそう書いてあったので、気がついた。 mod $p$ なら次数が $p$ の倍数の項は微分すると係数に $p$ の倍数が出てきてゼロになるのである。そこから多項式が微分して $0$ なら、次数が $p$ の倍数の項しかないということで、これはある多項式の $p$ 乗になっているということである。これもCantor-Zassenhaus の論文に書いてあった。

$\displaystyle (t^2+t+1)^p = t^{2p}+t^p+1$

となる。これで微分して $0$ でもmod $p$ の世界で無平方分解が出来る。同時にわかることは、プログラムで計算する時に、 $p$ 乗する際は実際に $p$ 回掛けるのではなく、係数ベクトルを $p$ 個おきになるように変えればよい。さらに、ここから以前から悩んでいたjavascriptで扱うにはやや指数が大きくなる問題も解決できた。ので一応書いておく。 Cantor-Zassenhaus 法では、 $p$ を素数、 $d$ を因数分解する多項式の次数とすると、mod $p$ の世界でランダムな多項式 $b(t)$ を $(p^{d}-1)/2$ 乗する必要があり、この $(p^{d}-1)/2$ 乗で悩んでいたのである。 $p$ 乗の計算は簡単だが、これは $p$ 乗ではない。そこで $p$ 乗に直すことにした。 $p$ は奇素数なので $p=2m+1$ とおく。

$\displaystyle \begin{eqnarray*} \frac{p^d-1}{2} &=& \frac{p^{d-1}p-1}{2} \\ &=& \frac{p^{d-1}(2m+1)-1}{2} \\ &=& \frac{2m(p^{d-1}) + p^{d-1}-1}{2} \\ &=& m(p^{d-1}) + \frac{p^{d-1}-1}{2} \end{eqnarray*}$