原始性检查算法 [英] Primality check algorithm

问题描述

原始检查可能是数学中那些棘手的问题之一。所以，什么是最好的和最快的算法可用于检查一个巨大的数字的原始性。最粗糙和最慢的方法大概是：

Primality Check is probably one of "those" tough problems in mathematics. So, whats is the best and fastest algorithm available to check the primality of a huge number. The most crude and the slowest way probably is:

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

最近我读过768位RSA算法已经被破解力，使用网格计算数组。他们如何对巨大的素数执行暴力？每个处理单元占用一系列数字，因子，并检查在该范围内的所有数字的原始性。

Recently I have read that the 768-bit RSA algorithm has been cracked using brute force, using a grid computing array. How do they perform the brute force on a huge prime number? Do each processing unit take up a series of number, factor it and check for primality all the number which lies in that range?

推荐答案

查看维基百科上的原始性测试指向当前算法的指针

Check out primality tests on Wikipedia for pointers to current algorithms

关于你的天真的实现，请注意，如果数字可以被2整除，那么你可以立即返回false，允许你只检查奇数。此外，如果没有找到x <= sqrt（i）的因子，则它是素数。这是因为如果你发现一个大于sqrt（i）的因子，那么它必须与比sqrt（i）小的因子相比较。所以，如果你没有找到这个较小的因素，你就完成了。

With regard to your naive implementation, do note that you can immediately return false if the number is divisible by 2, allowing you to just check odd numbers. In addition, if you don't find a factor where x <= sqrt(i), it is prime. This is because if you did find a factor larger than sqrt(i), then it must be paired with a factor smaller than sqrt(i). So if you don't find that smaller factor first, you're done.

还有更多的技巧，你可以应用于一个朴素的算法，你必须去请关闭 http://mathoverflow.net/ 获取帮助：）

There's also couple more tricks you can apply to a naive algorithm before you have to go trooping off to http://mathoverflow.net/ for help :)

这篇关于原始性检查算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！