Primality check algorithm

Question

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

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?

Answer 1

Check out primality tests on Wikipedia for pointers to current algorithms

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.

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