最快分解因子的最快方法是10 ^ 18

Question

给定一个数字1 <= n <= 10^18，我如何将其最小化时间复杂度？

互联网上有很多帖子介绍如何找到主要因素，但是在特定情况下，它们都（至少从我所看到的情况）没有陈述它们的好处。

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

• 使用筛子，找到前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;
}

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

Answer 1

方法

假设您有一个数字n，最高为10 ^18，并且想对它进行质分解。由于这个数字可以小到一个，最大到10 ¹⁸，所以它一直可以是素数也可以是合成数，这就是我的方法-

1. 使用Miller Rabin素数测试，确保该数字是复合的。
2. n使用最多10 ^6的质数进行因式分解，可以使用Eratosthenes筛子进行计算。

现在，更新的值为，n使得素数因子仅在10 ⁶以上，并且由于的值n仍可以高达10 ¹⁸，因此我们得出结论：该数字是素数，或者恰好具有两个素数（不一定是唯一的） 。

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

您现在拥有完整的分解。

让我们看一下上述方法的时间复杂性：

• 米勒·拉宾（Miller Rabin） O(log n)
• Eratosthenes筛网需要 O(n*log n)
• 我分享的Pollard rho的实现需要 O(n^0.25)

时间复杂度

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

空间复杂度

仅在执行筛分的步骤2中使用空间，该空间等于O(10^6)。再次，非常实用的目的。

实作

在中实现的完整代码C++14。该代码具有隐藏的错误。您可以在下一部分中揭示它，也可以跳过挑战；）

代码中的错误

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

挑战

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

奖金

n存在多少这样的值？

暗示

对于这样的n值，in的断言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。