c++ - 大数的高效质因数分解

Question

我一直在研究一个小问题，我需要将 18 位数字计算为它们各自的质因数分解。一切都编译并且运行得很好，考虑到它确实有效，但我希望减少质因数分解的运行时间。我已经实现了递归和线程，但我认为我可能需要一些帮助来理解大量计算的可能算法。

每次我对预先制作的 4 个数字运行此程序时，大约需要 10 秒。如果有任何想法，我想将其减少到可能的 0.06 秒。

我注意到一些算法，比如 Sieve of Eratosthenes并在计算之前生成所有素数的列表。我只是想知道是否有人可以详细说明。例如，我在理解如何将埃拉托色尼筛法应用到我的程序中时遇到问题，或者这是否是一个好主意。关于如何更好地解决这个问题的任何和所有指示都会非常有帮助!

这是我的代码:

#include <iostream>
#include <thread>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

vector<thread> threads;
vector<long long> inputVector;
bool developer = false; 
vector<unsigned long long> factor_base;
vector<long long> primeVector;

class PrimeNumber
{
    long long initValue;        // the number being prime factored
    vector<long long> factors;  // all of the factor values
public:
    void setInitValue(long long n)
    {
        initValue = n;
    }
    void addToVector(long long m)
    {
        factors.push_back(m);
    }
    void setVector(vector<long long> m)
    {
        factors = m;
    }
    long long getInitValue()
    {
        return initValue;
    }
    vector<long long> getVector()
    {
        return factors;
    }
};

vector<PrimeNumber> primes;

// find primes recursively and have them returned in vectors
vector<long long> getPrimes(long long n, vector<long long> vec)
{
    double sqrt_of_n = sqrt(n);

    for (int i = 2; i <= sqrt_of_n; i++)
    {
        if (n % i == 0) 
        {
            return vec.push_back(i), getPrimes(n / i, vec); //cause recursion
        }
    }

    // pick up the last prime factorization number
    vec.push_back(n);

    //return the finished vector
    return vec;
}

void getUserInput()
{
    long long input = -1;
    cout << "Enter all of the numbers to find their prime factors. Enter 0 to compute" << endl;
    do
    {
        cin >> input;
        if (input == 0)
        {
            break;
        }
        inputVector.push_back(input);
    } while (input != 0);
}

int main() 
{

    vector<long long> temp1;   // empty vector
    vector<long long> result1; // temp vector

    if (developer == false)
    {
        getUserInput();
    }
    else
    {
        cout << "developer mode active" << endl;
        long long a1 = 771895004973090566;
        long long b1 = 788380500764597944;
        long long a2 = 100020000004324000;
        long long b2 = 200023423420000000;
        inputVector.push_back(a1);
        inputVector.push_back(b2);
        inputVector.push_back(b1);
        inputVector.push_back(a2);
    }

    high_resolution_clock::time_point time1 = high_resolution_clock::now();

    // give each thread a number to comput within the recursive function
    for (int i = 0; i < inputVector.size(); i++)
    {   
        PrimeNumber prime;
        prime.setInitValue(inputVector.at(i));
        threads.push_back(thread([&]{
            prime.setVector(result1 = getPrimes(inputVector.at(i), temp1));
            primes.push_back(prime);
        }));
    }

    // allow all of the threads to join back together.
    for (auto& th : threads)
    {
        cout << th.get_id() << endl;
        th.join();
    }

    high_resolution_clock::time_point time2 = high_resolution_clock::now();

    // print all of the information
    for (int i = 0; i < primes.size(); i++)
    {
        vector<long long> temp = primes.at(i).getVector();

        for (int m = 0; m < temp.size(); m++)
        {
            cout << temp.at(m) << " ";
        }
        cout << endl;
    }

    cout << endl;

    // so the running time
    auto duration = duration_cast<microseconds>(time2 - time1).count();

    cout << "Duration: " << (duration / 1000000.0) << endl;

    return 0;
}

Answer 1

试除法只适合小数因式分解。对于最大 2^64 的 n，您将需要更好的算法:我建议从轮分解开始获取小因子，然后使用 Pollard 的 rho 算法获取其余因子。其中trial division是O(sqrt(n))，rho是O(sqrt(sqrt(n)))，所以速度快多了。对于 2^64，sqrt(n) = 2^32，但 sqrt(sqrt(n)) = 2^16，这是一个巨大的改进。您应该期望最多在几毫秒内分解出您的数字。

我没有用于因式分解的 C++ 代码，但我有可读的 Python 代码。如果你想让我发布它，请告诉我。如果您想了解更多关于轮子分解和 rho 算法的信息，我在 my blog 有很多素数资料。 .