素数检测算法

Question

素性检查可能是数学中那些难题之一。那么，检查大数的素性可用的最佳且最快的算法是什么？最粗糙和最慢的方法可能是：

public static bool IsPrime(int i)
{
    for (var x = 2; x < i - 1; i++)
    {
         if (i % x == 0)
         {
             return false;
         }
    }
    return true;
}

最近，我读到768位RSA算法已经被破解，使用了网格计算阵列进行暴力破解。他们如何对巨大的质数执行暴力破解？每个处理单元是否需要处理一系列数字，将其分解并检查该范围内所有数字的素性？

- Bhaskar

---

ceil(sqrt(i)) 是您需要检查的最大因子。 - swegi

也许我太蠢了，但我认为floor(sqrt(i))是您需要检查的最大因子？ - jk.

在素性测试领域，int.MaxValue并不算作“巨大的数字”。你的数字有多大？ - AakashM

严格来说，为了确定一个数字是否为质数，您不需要检查任何因素。对于我们关心的大数字，椭圆曲线素性测试在实践中是最快的，而修改后的AKS素性测试具有最低的可证明复杂度。我认为它们两个都没有实际产生因子。RSA破解确实需要产生因子，因此基本上您问错了问题。 - Steve Jessop

Lenstra的椭圆曲线算法计算因子，如果它们存在的话。 @jk：我认为你是对的。 - swegi

Answer 1

请参考维基百科中的素性测试，以获取当前算法的指针。

关于您的朴素实现，请注意，如果该数字可被2整除，则可以立即返回false，从而只需检查奇数。此外，如果您没有找到一个因子，其中x<= sqrt(i)，那么它是质数。这是因为如果您找到了一个大于sqrt(i)的因子，那么它必须与小于sqrt(i)的因子配对。因此，如果您没有首先找到较小的因子，则完成。

在您必须前往https://mathoverflow.net/寻求帮助之前，还有一些技巧可以应用于朴素算法 :)

- Paul Dixon

---

嗯，不要到mathoverflow.net寻求帮助，因为这不是一个研究/学术话题。（关于特定素性测试算法的具体问题可能会在那里受到欢迎） - Jason S

Answer 2

破解RSA-768并不直接涉及任何素性检查算法，而是需要使用一种分解算法：RSA-768是两个非常大质数的乘积，破解它需要找到这些质数。

所使用的分解算法是Lenstra的Number Field Sieve。

您可以在此处阅读完整文章：Factorization of a 768-bit RSA modulus。

- Rasmus Faber

Answer 3

这应该会快得多：

public static bool IsPrime(int i) {        
    // only go up to the root of i 
    // +1 to be save from floating point rounding errors, ceil should work too.
    var max = sqrt(i) + 1;

    // skip numbers dividable by 2, except 2 itself
    if (i == 2) return true;
    if (i % 2 == 0) return false;
    for (var x = 3; x < max; x+=2)  {
         if (i % x == 0)  {
             return false;
         }
    }
    return true;
}

- martinus

Answer 4

我猜他们使用了某种工作量分配方式，但我怀疑他们没有使用这么简单的素性测试算法。也许他们使用了数域筛选法或Lenstra椭圆曲线因子分解。

- swegi

Answer 5

素性测试 != 因数分解。

破解特定的RSA公钥并检索私钥需要因数分解。

构建RSA公/私钥对的过程包括素性测试。大多数用于非因数分解的素性测试不会产生100％确定的答案，而是具有任意高概率的概率性（更多的测试迭代=更高的概率）。

技术上，您可以使用确定性素性测试，它快速且不涉及实际计算所涉及数字的任何因子。

- Jason S

Answer 6

我建议使用Fermat's Little Theorem。当且仅当 ((a ^ (x-1)) % x) == 1 时，'x' 的值是质数。其中'a'是任意数字，'x'不等于1、0或2。

- syntax-punk

Answer 7

public static bool IsPrime(int i)
{
    for (var x = 2; x < (i/2); x++)
    {
         if (i % x == 0)
         {
             return false;
         }
    }
    return true;
}

- D.C.