algorithm - 将一个数分解为 10^18 的最快方法

Question

给定一个数字1 <= n <= 10^18，我怎样才能以最小的时间复杂度分解它？

互联网上有很多关于如何找到主要因素的帖子，但没有一个（至少从我所见）说明它们的好处，比如在特定情况下。

除了 Eratosthenes 的筛子，我还使用 Pollard 的 rho 算法：

• 使用 sieve，找出前 10 个⁷数中的所有素数，然后n尽可能地用这些素数除。
• 现在使用 Pollard 的 rho 算法尝试找出其余的素数，直到 n 等于 1。

我的实现：

#include <iostream>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;

typedef unsigned long long ull;
typedef long double ld;
typedef pair <ull, int> pui;
#define x first
#define y second
#define mp make_pair

bool prime[10000005];
vector <ull> p;

void initprime(){
    prime[2] = 1;
    for(int i = 3 ; i < 10000005 ; i += 2){
        prime[i] = 1;
    }
    for(int i = 3 ; i * i < 10000005 ; i += 2){
        if(prime[i]){
            for(int j = i * i ; j < 10000005 ; j += 2 * i){
                prime[j] = 0;
            }
        }
    }
    for(int i = 0 ; i < 10000005 ; ++i){
        if(prime[i]){
            p.push_back((ull)i);
        }
    }
}

ull modularpow(ull base, ull exp, ull mod){
    ull ret = 1;
    while(exp){
        if(exp & 1){
            ret = (ret * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return ret;
}

ull gcd(ull x, ull y){
    while(y){
        ull temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

ull pollardrho(ull n){
    srand(time(NULL));
    if(n == 1)
        return n;
    ull x = (rand() % (n - 2)) + 2;
    ull y = x;
    ull c = (rand() % (n - 1)) + 1;
    ull d = 1;
    while(d == 1){
        x = (modularpow(x, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        d = gcd(abs(x - y), n);
        if(d == n){
            return pollardrho(n);
        }
    }
    return d;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
initprime();
ull n;
cin >> n;
ull c = n;
vector <pui> o;
for(vector <ull>::iterator i = p.begin() ; i != p.end() ; ++i){
    ull t = *i;
    if(!(n % t)){
        o.push_back(mp(t, 0));
    }
    while(!(n % t)){
        n /= t;
        o[o.size() - 1].y++;
    }
}
while(n > 1){
    ull u = pollardrho(n);
    o.push_back(mp(u, 0));
    while(!(n % u)){
        n /= u;
        o[o.size() - 1].y++;
    }
    if(n < 10000005){
        if(prime[n]){
            o.push_back(mp(n, 1));
        }
    }
}
return 0;
}

有没有更快的方法来分解这些数字？如果可能，请连同源代码一起解释原因。

标签： algorithmprimesprime-factoringsieve-of-eratosthenesfactorization

Answer 1

方法

假设您有一个n高达 10 ¹⁸的数字，并且您想对它进行质因数分解。由于这个数字可以小到统一，大到 10 ¹⁸，一直以来它可以是素数也可以是合数，这将是我的方法 -

1. 使用米勒拉宾素数测试，确保数字是复合的。
2. n使用高达 10 ⁶的素数进行因式分解，可以使用Eratosthenes 的筛法计算。

现在更新的值n是这样的，它的质因数仅高于 10 ⁶并且由于值n仍然可以与 10 ¹⁸一样大，我们得出结论，该数字要么是质数，要么恰好有两个质因数（不一定不同） .

3. 再次运行 Miller Rabin 以确保该数字不是素数。
4. 使用Pollard rho 算法得到一个素因子。

你现在有了完整的因式分解。

让我们看看上述方法的时间复杂度：

• 米勒·拉宾O(log n)
• 埃拉托色尼筛法O(n*log n)
• 我分享的 Pollard rho 的实现需要O(n^0.25)

时间复杂度

步骤 2 花费的最大时间等于O(10^7)，这又是上述算法的复杂度。这意味着您可以在一秒钟内找到几乎所有编程语言的因式分解。

空间复杂度

空间仅在步骤 2 中使用，其中实施了 sieve 并且等于O(10^6)。再次，非常实用的目的。

执行

完整的代码在C++14. 该代码有一个隐藏的错误。您可以在下一部分中展示它，也可以跳到挑战；）

代码中的错误

在line 105中，迭代直到i<=np。否则，您可能会错过prime[np]=999983主要因素的情况

挑战

给我一个值n，如果有的话，共享代码会导致错误的素数分解。

奖金

有多少这样的价值观n存在？

暗示

对于这样的 n 值，断言Line 119可能会失败。

解决方案

让我们打电话P=999983。n = p*q*rp, q, r 是素数 >=的所有形式的数字，如果其中P至少一个等于，P将导致错误的素数分解。

奖金解决方案

恰好有四个这样的数字：{P ₀ ³ , P ₀ ² P ₁ , P ₀ ² P ₂ , P ₀ P ₁ ² }，其中 P ₀ = P = 999983, P ₁ = next_prime(P ₀ ) = 1000003, P ₂ = next_prime(P ₁ ) = 1000033。