素性检查算法 [英] 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

关于你的幼稚的做法，也请注意，您可以立即返回false，如果数字是能被2整除，让您只需选中奇数。另外，如果没有找到一个因子其中X = SQRT（i）中，它是素数。这是因为如果你没有找到比的sqrt（我）更大的一个因素，那么它必须与一个因素配对的小的超过的sqrt（我）。所以，如果你没有发现更小的因素第一，你就大功告成了千万。

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屋！