最快分解因子的最快方法是10 ^ 18 [英] Fastest way to prime factorise a number up to 10^18

问题描述

给出一个数字 1< = n< = 10 ^ 18 ，我该如何将其分解为最少的时间复杂度?

Given a number 1 <= n <= 10^18, how can I factorise it in least time complexity?

Internet上有很多帖子介绍了如何找到主要因素，但在特定情况下，却没有一个因素(至少从我所看到的情况)阐明了它们的好处.

There are many posts on the internet addressing how you can find prime factors but none of them (at least from what I've seen) state their benefits, say in a particular situation.

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

I use Pollard's rho algorithm in addition to Eratosthenes' sieve:

• 使用筛子，找到前10个 ⁷ 个数字中的所有质数，然后将 n 尽可能除以这些质数.
• 现在使用Pollard的rho算法尝试查找其余素数，直到n等于1.

• Using sieve, find all prime numbers in the first 10⁷ numbers, and then divide n with these primes as much as possible.
• Now use Pollard's rho algorithm to try and find the rest of the primes until n is equal to 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;
}

有没有更快的方法来分解这些数字?如果可能，请说明原因以及源代码.

Is there any faster way to factor such numbers? If possible, please explain why along with the source code.

推荐答案

方法

让我们说您有一个数字 n 最多为10 ¹⁸ ，并且您想对它进行质因子分解.由于这个数字可以小到一个，最大可以是10 ¹⁸ ，因此一直都是素数和复合数，这就是我的方法-

Approach

Lets say you have a number n that goes up to 10¹⁸ and you want to prime factorise it. Since this number can be as small as unity and as big as 10¹⁸, all along it can be prime as well as composite, this would be my approach -

1. 使用

1. Using miller rabin primality testing, make sure that the number is composite.
2. Factorise n using primes up to 10⁶, which can be calculated using sieve of Eratosthenes.

现在， n 的更新值使得素数因子仅高于10 ⁶ ，并且由于 n 的值仍为得出结论，这个数字最大为10 ¹⁸ ，要么是素数，要么正好有两个素数(不一定是唯一的).

Now the updated value of n is such that it has prime factors only above 10⁶ and since the value of n can still be as big as 10¹⁸, we conclude that the number is either prime or it has exactly two prime factors (not necessarily distinct).

1. 再次运行Miller Rabin以确保数字不是素数.
2. 使用

1. Run Miller Rabin again to ensure the number isn't prime.
2. Use Pollard rho algorithm to get one prime factor.

您现在已经完成了因子分解.

You have the complete factorisation now.

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

Lets look at the time-complexity of the above approach:

• 米勒·拉宾(Miller Rabin)接受 O(log n)
• 妖怪之筛需要 O(n * log n)
• 我共享的Pollard rho的实现需要 O(n ^ 0.25)

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

Step 2 takes maximum time which is equal to O(10^7), which is in turn the complexity of the above algorithm. This means you can find the factorisation within a second for almost all programming languages.

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

Space is used only in the step 2 where sieve is implemented and is equal to O(10^6). Again, very practical for the purpose.

完整代码在 C ++ 14 中实现.该代码有一个隐藏的错误.您可以在下一部分中显示它，也可以跳过挑战;)

Complete Code implemented in C++14. The code has a hidden bug. You can either reveal it in the next section, or skip towards the challenge ;)

在 105行中，迭代直到 i< = np .否则，您可能会错过 prime [np] = 999983 是主要因素

In line 105, iterate till i<=np. Otherwise, you may miss the cases where prime[np]=999983 is a prime factor

挑战

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

Challenge

Give me a value of n, if any, where the shared code results in wrong prime factorisation.

存在多少这样的 n 值?

对于这样的n值，第119行中的断言可能会失败.

解决方案

让我们调用 P = 999983 .所有形式为 n = p * q * r 的数字，其中p，q，r是质数> = P ，因此至少其中一个等于P 将导致错误的素因数分解.

Lets call P=999983. All numbers of the form n = p*q*r where p, q, r are primes >= P such that at least one of them is equal to P will result in wrong prime factorisation.

奖金解决方案

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

There are exactly four such numbers: {P₀³, P₀²P₁, P₀²P₂, P₀P₁²}, where P₀ = P = 999983, P₁ = next_prime(P₀) = 1000003, P₂ = next_prime(P₁) = 1000033.

这篇关于最快分解因子的最快方法是10 ^ 18的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！