間違ったポラードのロー法の使い方

概要

アルゴ式が公開している素因数分解するアルゴリズム(と称しているもの)は、特定の入力に対して正しく動作しません(無限ループします)。 ポラードのロー法が失敗した場合、疑似乱数生成器のシードのみを変更するのではなく、疑似乱数生成器自体を変更してリトライする必要があります。

アルゴ式が公開しているコードとうまくいかない入力

アルゴ式が公開しているコード

アルゴ式が公開している素因数分解する(と称している)コードでは、以下のようにポラードのロー法を使っています。

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で表される半素数素数二つの積)です。

この数の素因数分解に失敗するのは、疑似乱数生成器  f : x \mapsto x^2+1\!\!\!\mod\!124376107291 が821という非常に短い周期を持つことが関係しています。 具体的には、 \forall x\in \mathbb{Z}, f^{653}(x) = f^{1474}(x) が成り立ちます。 この短い周期により、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の呼び出し回数は含んでいません。

その他

乱数生成器のパラメータを変えるだけでは、問題を解決することはできません。

乱数生成器として  f : x \mapsto x^2 +2\!\!\!\mod\!N を使う場合、273772559の素因数分解に失敗します(無限ループします)。 乱数生成器として  f : x \mapsto x^2 +4\!\!\!\mod\!N を使う場合、2059の素因数分解に失敗します(無限ループします)。 乱数生成器として  f : x \mapsto x^2 +5\!\!\!\mod\!N を使う場合、385515865499の素因数分解に失敗します(無限ループします)。

乱数生成器として  f : x \mapsto x^2 +3\!\!\!\mod\!N を使う場合、無限ループする入力を見つけることはできませんでしたが、7816550168663の素因数分解には一分以上時間がかかります。

乱数生成器として  f : x \mapsto x^2\!\!\mod\!N を使う場合、無限ループすることはありません。 ただし、実質的に試し割り法に退化しているので、まったく実用的ではありません。 例えば7482809861の素因数分解に一分以上時間がかかります。