平方因子の存在

自然数が与えられたとき、その数が平方因子を持つかどうかの判定は、現在のところ、因数分解してみる以上に効率的な方法が知られていない。 べつに因子自身を知る必要が無いということを考えると、因数分解は手間が掛かりすぎという感覚があり、多分これは多くの(計算数論に多少なりとも興味のある)人に喉に刺さった小骨のような苛立ちをもたらしている。 以下に述べることは、問題の解決ではなく、こんなことを考えてみたけどうまくいかんなあ、という記録である。

整数の難しい問題は、一変数多項式に手がかりを求めると良いと言われる。 多項式が平方因子を持つかどうかの判定は簡単で、$(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$ の成立を確かめよう、というのが次のタスクになる。 そこでひねり出したのが次の条件である。 $$\mathrm{\exists }a\text{ s.t. }{a}^{n-1}\not\equiv 1modn\wedge a^{n(n-1)}\equiv 1modn$$ これが $(n,\phi (n))>1$ と同値な条件になっている。 問題は、存在するという $a$ はどのぐらいの数を調べると見つかるのか、ということである。 それは各素(冪)因子での条件の中国式剰余定理での組み合わせなので、まあだいたい平方になっている素因子ぐらいは最低でも見ないと見つからないはずだ。 結局、そんなに大量に探すなら因数分解した方が早くなってしまう。 少し考えれば $1$ かどうかにこだわらず $n-1$ 乗では異なり $n(n-1)$ 乗では一致する組 $a,b$ を見つければ良いと判るが、これでも計算量は平方根程度に(確率的に)落ちるだけなのでまだ指数の手間が掛かる。

いつか改善策を思いつけたらいいな、と思ったのが5年ぐらい前の話である。