素性检验算法

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算法被破解，使用的是网格计算阵列，使用暴力破解。他们如何在一个巨大的质数上使用蛮力？是否每个处理单元占用一系列数字，将其分解并检查位于该范围内的所有数字的素性？

Answer 1

在维基百科上查看primality tests，找到当前算法的指针

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

在你不得不去https://mathoverflow.net/寻求帮助之前，还有几个技巧可以应用于一个朴素的算法:)

Answer 2

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

所使用的因式分解算法是伦斯特拉的Number Field Sieve。

你可以在这里阅读全文：Factorization of a 768-bit RSA modulus。

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;
}