Midnight Floating Thought

自然数が与えられたとき、その数が平方因子を持つかどうかの判定は、現在のところ、因数分解してみる以上に効率的な方法が知られていない。 べつに因子自身を知る必要が無いということを考えると、因数分解は手間が掛かりすぎという感覚があり、多分これは多くの(計算数論に多少なりとも興味のある)人に喉に刺さった小骨のような苛立ちをもたらしている。 以下に述べることは、問題の解決ではなく、こんなことを考えてみたけどうまくいかんなあ、という記録である。 整数の難しい問題は、一変数多項式に手がかりを求めると良いと言われる。 多項式が平方因子を持つかどうかの判定は簡単で、$(f,f^{\prime })$ を計算すると平方因子が求まる。 (もちろん $f^{\prime }$ は $f$ を微分したもの、$(,)$ は最大公約因子の記号、である) 例えば $f(X)=X^3+7X^2+8X-16$ とすると、 $f^{\prime }(X)=3X^2+14X+8$ で、 $f(X)$ と $f^{\prime }(X)$ の最大公約因子は $X+4$。 よって $f(X)$ は $X+4$ で2回割り切れる。 整数には微分が定義されていないので、そのまま使えるわけではないが、類似の現象を探すのが良さそうである。 次の関係に注目してみたい。 「$n$ が平方因子を持つ正整数ならば、$(n,\phi (n))>1$」 注意点としては、逆が成り立たないし、$\phi (n)$ の計算の手間も因数分解と大体同等だと思われる、という二つがある。 逆が成り立たないことは、$p_1|p_2-1$ となる $n$ の素因数の組 $p_1,p_2$ がある場合にも $(n,\phi (n))>1$ となることを見れば良い。 オイラー関数の計算の手間が因数分解と同等か正確なところは判らないが、RSA 暗号の安全性と関わってそういう議論があったはずだ。 オイラー関数を計算してはいけないという縛りの下に $(n,\phi (n))>1$ の成立を確かめよう、というのが次のタスクになる。 そこでひねり出したのが次の条件である。 \[\exists a \text{ ...