概要
アルゴ式が公開している素因数分解するアルゴリズム(と称しているもの)は、特定の入力に対して正しく動作しません(無限ループします)。 ポラードのロー法が失敗した場合、疑似乱数生成器のシードのみを変更するのではなく、疑似乱数生成器自体を変更してリトライする必要があります。
アルゴ式が公開しているコードとうまくいかない入力
アルゴ式が公開しているコード
アルゴ式が公開している素因数分解する(と称している)コードでは、以下のようにポラードのロー法を使っています。
long long pollard(long long N) { if (N % 2 == 0) return 2; if (is_prime(N)) return N; auto f = [&](long long x) -> long long { return (__int128_t(x) * x + 1) % N; }; long long step = 0; while (true) { ++step; long long x = step, y = f(x); while (true) { long long p = gcd(y - x + N, N); if (p == 0 || p == N) break; if (p != 1) return p; x = f(x); y = f(f(y)); } } }
この方法では、ポラードのロー法により非自明な因数を見つけられなかった場合(疑似乱数が真に循環してしまった場合)に、++step
でリトライしています。
ここで、step
の変更によりx
、つまり疑似乱数生成器のシードを変更しています。
しかし、これは問題があります。 なぜなら、疑似乱数生成器が弱い(循環周期が短い)場合、シード値を変更してもその状況が変わらないからです。
うまくいかない入力
上記pollard
関数に124376107291を入力すると、無限ループします。
この数は、352523×352817で表される半素数(素数二つの積)です。
この数の素因数分解に失敗するのは、疑似乱数生成器 が821という非常に短い周期を持つことが関係しています。 具体的には、 が成り立ちます。 この短い周期により、mod 124376107291で循環する前にmod 352523での循環やmod 352817での循環を発見することができなくなっています。
どうしたらよいのか
ポラードのロー法が失敗した場合、疑似乱数生成器のシードを変えるのではなく、疑似乱数生成器自体を変えるほうが良いです。 具体的には、以下のように変更します。
if (N % 2 == 0) return 2; if (is_prime(N)) return N; + long long step = 0; auto f = [&](long long x) -> long long { - return (__int128_t(x) * x + 1) % N; + return (__int128_t(x) * x + step) % N; }; - long long step = 0; while (true) { ++step;
この変更を加えた場合、1013以下の数の非自明な因数を一つ見つけるのに必要なgcd
の回数は最悪でも9000回になります。
1018以下の場合、最悪でもおおよそ12万回程度のgcd
呼び出しで非自明な因数を一つ見つけることができるようです(私が見つけられた数の中で最も多くgcd
を呼び出したのは、814483663644399613を入力したときで、117480回でした。2.1GHzで動く計算機で、25ms程度かかります)。
※gcd
の中で再帰的に呼び出されるgcd
の呼び出し回数は含んでいません。
その他
乱数生成器のパラメータを変えるだけでは、問題を解決することはできません。
乱数生成器として を使う場合、273772559の素因数分解に失敗します(無限ループします)。 乱数生成器として を使う場合、2059の素因数分解に失敗します(無限ループします)。 乱数生成器として を使う場合、385515865499の素因数分解に失敗します(無限ループします)。
乱数生成器として を使う場合、無限ループする入力を見つけることはできませんでしたが、7816550168663の素因数分解には一分以上時間がかかります。
乱数生成器として を使う場合、無限ループすることはありません。 ただし、実質的に試し割り法に退化しているので、まったく実用的ではありません。 例えば7482809861の素因数分解に一分以上時間がかかります。