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

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

}

Answer 2

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 http://mathoverflow.net/ for help :)

Answer 3

I suppose there is some kind of workload distribution, but I doubt that they used such a simple algorithm for the primality test. Maybe they used the number field sieve or Lenstra's elliptic curve factorization.

Answer 4

This should be quite a bit faster:

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

Answer 5

Cracking RSA-768 did not directly involve any primality check algorithm, rather what was needed was a factorization algorithm: RSA-768 is the product of two very large primes, and cracking it involves finding these primes.

The factorization algorithm used was Lenstra's Number Field Sieve.

You can read the full article here: Factorization of a 768-bit RSA modulus.

Answer 6

Primality testing != factorization.

Breaking a particular RSA public key and retrieving the private key, requires factorization.

The process of constructing an RSA public/private key pair includes primality testing. Most primality testing not used for factorization does not produce a 100% definite answer, but rather it is probabilistic with arbitrarily high probability (more test iterations = higher probability).

And technically you can have a deterministic primality test that is fast and does not involve actually computing any factors of the number in question.