python - Factor (Prime-1)/2 for 64-bit Prime 的最快方法？

Question

我正在尝试收集有关素数的一些统计数据，其中包括数字 (prime-1)/2 的因数分布。我知道有统一选择数的因子大小的通用公式，但我还没有看到任何关于小于一个素数的因子分布的信息。

我编写了一个程序，从 2^63 之后的第一个素数开始遍历素数，然后使用试除以 2^32 以内的所有素数对 (prime - 1)/2 进行因式分解。然而，这非常慢，因为要遍历大量素数(和大量内存)。我将每个质数存储为一个字节(通过存储从一个质数到下一个质数的增量)。我还对最大 2^64 的数字使用 Miller-Rabin 素数测试的确定性变体，因此我可以轻松检测剩余值(成功除法后)何时为素数。

我已经尝试使用 pollard-rho 和椭圆曲线分解的变体，但很难在试验除法和切换到这些更复杂的方法之间找到正确的平衡。此外，我不确定我是否正确实现了它们，因为有时它们似乎需要很长时间才能找到一个因素，并且根据它们的渐近行为，我希望它们对于这么小的数字会很快。

我还没有找到任何关于因式分解多个数字的信息(与仅仅尝试因式分解一个数字相比)，但似乎应该有某种方法可以利用这一点来加快任务速度。

非常感谢关于此问题的任何建议、替代方法的指示或其他指导。

---

编辑:我存储素数的方式是存储下一个素数的 8 位偏移量，隐含的第一个素数为 3。因此，在我的算法中，我单独检查除以 2，然后开始循环:

factorCounts = collections.Counter()
while N % 2 == 0:
    factorCounts[2] += 1
    N //= 2
pp = 3
for gg in smallPrimeGaps:
    if pp*pp > N:
        break
    if N % pp == 0:
        while N % pp == 0:
            factorCounts[pp] += 1
            N //= pp
    pp += gg

另外，我用轮筛算出试除素数，然后用几个素数取余的算法得到给定起点后的下一个素数。

---

我使用以下代码来测试给定数字是否为质数(现在将代码移植到 C++):

bool IsPrime(uint64_t n)
{
    if(n < 341531)
        return MillerRabinMulti(n, {9345883071009581737ull});
    else if(n < 1050535501)
        return MillerRabinMulti(n, {336781006125ull, 9639812373923155ull});
    else if(n < 350269456337)
        return MillerRabinMulti(n, {4230279247111683200ull, 14694767155120705706ull, 1664113952636775035ull});
    else if(n < 55245642489451)
        return MillerRabinMulti(n, {2ull, 141889084524735ull, 1199124725622454117, 11096072698276303650});
    else if(n < 7999252175582851)
        return MillerRabinMulti(n, {2ull, 4130806001517ull, 149795463772692060ull, 186635894390467037ull, 3967304179347715805ull});
    else if(n < 585226005592931977)
        return MillerRabinMulti(n, {2ull, 123635709730000ull, 9233062284813009ull, 43835965440333360ull, 761179012939631437ull, 1263739024124850375ull});
    else
        return MillerRabinMulti(n, {2ull, 325ull, 9375ull, 28178ull, 450775ull, 9780504ull, 1795265022ull});
}

Answer 1

我没有一个明确的答案，但我确实有一些观察和一些建议。

在 2^63 和 2^64 之间大约有 2*10^17 个素数，所以你写的任何程序都会运行一段时间。

让我们谈谈 2^63 到 2^64 范围内数字的素数测试。任何通用测试都会做比您需要的更多的工作，因此您可以通过编写专用测试来加快速度。我建议对基数 2 和基数 3 进行强伪素数测试(如 Miller-Rabin 中的测试)。如果这些测试中的任何一个显示数字是合数，那么你就完成了。否则，在以 2 和 3 为底的强伪质数表中查找数字(二分搜索)(请 Google 为您查找这些表)。两个强伪素数测试后跟一个表查找肯定会比您当前执行的确定性 Miller-Rabin 测试更快，后者可能使用六个或七个碱基。

对于因式分解，尝试除法到 1000，然后是 Brent-Rho，直到已知质因数的乘积超过被分解数的立方根应该相当快，几毫秒。那么，如果剩下的余因子是复合的，它必然只有两个因子，所以 SQUFOF 将是一个很好的拆分它们的算法，比其他方法更快，因为所有算术都是用小于数字平方根的数字完成的因式分解，在您的情况下，这意味着可以使用 32 位算术而不是 64 位算术来完成因式分解，因此它应该很快。

代替因式分解和素性测试，更好的方法是使用埃拉托色尼筛法的变体来因式分解大块数字。这仍然会很慢，因为有 2.03 亿个筛选质数小于 2^32，并且您将需要处理分段筛的簿记，但考虑到您一次分解大量数字，这可能是最好的方法你的任务。

我在 my blog 有上述所有内容的代码.