我正在尝试收集一些有关素数的统计数据，其中包括数字 (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});
}
最佳答案
我没有明确的答案，但我确实有一些观察和建议。
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 有上述所有内容的代码.
关于python - 64 位 Prime 因式分解 (Prime-1)/2 的最快方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40109623/