原始检查算法

Question

Primality Check可能是数学中"那些"难题之一.所以,什么是最好和最快的算法可用于检查大量的素数.最粗糙和最慢的方式可能是:

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

查看Wikipedia上的素性测试,了解当前算法的指针

关于你的天真实现,请注意,如果数字可以被2整除,你可以立即返回false,这样你就可以检查奇数.另外,如果你没有找到x <= sqrt(i)的因子,那么它就是素数.这是因为如果您确实找到大于sqrt(i)的因子,那么它必须与小于 sqrt(i)的因子配对.因此,如果您没有首先找到较小的因素,那么您就完成了.

在您必须前往https://mathoverflow.net/寻求帮助之前,您还可以将更多技巧应用于天真的算法:)

Answer 2

破解RSA-768并不直接涉及任何素性检查算法,而是需要的是分解算法:RSA-768是两个非常大的素数的产物,并且破解它涉及找到这些素数.

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

您可以在这里阅读完整的文章:768位RSA模数的分解.

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