1

64 ビット整数 (32 ビットより大きい) の約数を取得しようとしています。

私の最初の方法 (小さい数値の場合) は、結果の数値が 1 になるまで数値を除算し、一致する素数の数を数え、式 (1 + P1) (1+ P2) ..*(1 + Pn) = Numberを使用することでした。約数

例えば：

24 = 2 * 2 * 2 * 3 = 2^ 3 * 3^ 1

==> ( 3 + 1)*( 1 + 1) = 4 * 2 = 8 除数

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

しかし、大きな整数の場合、このメソッドは多くの反復を必要とします。2乗数を使って因数分解するQuadratic sieveという方法を見つけました。私のスクリプトを使用すると、数値がはるかに小さいため、これははるかに簡単になります。

私の質問は、この Quadratic Sieve をどのように実装できますか?

4

1 に答える 1

2

二次ふるいは、大きな数の大きな因子を見つける方法です。2^64 ではなく、10^75 と考えてください。二次ふるいは、単純な疑似コード形式でも複雑であり、効率的にしたい場合はさらに複雑になります。これは 64 ビット整数に対して非常に過剰であり、そのような小さな数に特化した他の方法よりも遅くなります。

試行分割が遅すぎる場合は、複雑さの次のステップは John Pollard の rho メソッドです。64 ビット整数の場合は、いくつかの小さな制限 (おそらく 1000 未満の素数) まで分割を試行してから、rho に切り替えます。nの単一因数を見つける単純な擬似コードを次に示します。複合補因子で繰り返し呼び出して、分解を完了します。

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

64 ビット整数を素因数分解する方法は他にもありますが、これで作業を開始でき、ほとんどの目的にはおそらくこれで十分です。適度な速度向上のために、Richard Brent の rho アルゴリズムの変形を検索することができます。詳細を知りたい場合は、私のブログのエッセイ「素数によるプログラミング」をお勧めします。

于 2015-03-23T02:37:16.347 に答える