Primality test (naive approach)

Testing number's primality is a quite important task in computer science. For the most part, prime numbers are used in public key cryptography algorithms. Also there are applications for hash tables and pseudorandom numbers generators. There are two types of algorithms to check whether number is prime: deterministic and probabilistic. To tell the truth, there are dozens of primality test algorithms. In current article we are going to develop and discuss the most naive approach, called trial division, and its modifications.

What is a prime number?

Prime number is a number, which have exactly two distinct natural number divisors, 1 and itself. The most naive approach to check whether a number is prime is to follow the definition. Algorithm to check number's n primality:

• if number is 1, return false;
• otherwise, for all integers m from 2 to n - 1, check if n is divisible by m. If it is, n is composite;
• if no divisors were found, we can conclude, that n is prime.

Note. The 1 is not a prime number, because it doesn't satisfy the definition.

Improving the method

Can we make this simple approach better? Yes. First, let us notice, that we can check divisors less or equal to square root of n only. The proof follows.

Statement. If n has a divisor d (1 < d < n), than it has a divisor d₀ (1 < d₀ < √n).

If n is divided by square root entirely, than it is a perfect square and not prime. Otherwise, assume, that first found divisor is d₁, √n < d₁ < n. But n is divided entirely by d₂ = n / d₁, which is less than √n. Therefore, the assumption is false and if there are a divisor greater than √n, than there is a "pair" less than √n. Statement is proven.

One more improvement

We should mention one more improvement. Assume, than n is odd (2 is not a divisor). If n is not divisible by 2 without remainder, than it is not divisible entirely by any other even number. The algorithm after those two improvements changes:

• if number is 1, return false;
• if number is 2, return true;
• if number is even, return false;
• otherwise, for all odd integers m from 3 to √n, check if n is divisible by m. If it is, n is composite;
• if no divisors were found, we can conclude, that n is prime.

Generalization of this idea is when algorithm checks prime divisors only.

Complexity analysis

Assuming, that divisibility of two numbers is a unit operation (which is not correct for large numbers), algorithm's complexity is O(√n). The last improvement changes the constant only. When checking just prime divisors, algorithm's complexity becomes O(√n / ln(n)).

The main application of primes is cryptography, which expects us to generate primes with hundreds of digits. Apparently, the algorithm won't check numbers around 10¹⁰⁰ in a reasonable time. Though, algorithm is applied on practice to do a "pre-check". A huge number being tested for primality is examined to be divisible by first million primes. If no divisors found, probabilistic algorithm is used then.

First hundred primes

       2       3       5       7      11      13      17      19      23      29

      31      37      41      43      47      53      59      61      67      71

      73      79      83      89      97     101     103     107     109     113

     127     131     137     139     149     151     157     163     167     173

     179     181     191     193     197     199     211     223     227     229

     233     239     241     251     257     263     269     271     277     281

     283     293     307     311     313     317     331     337     347     349

     353     359     367     373     379     383     389     397     401     409

     419     421     431     433     439     443     449     457     461     463

     467     479     487     491     499     503     509     521     523     541

Code snippets

Java implementation

public boolean isPrime(int number) {

      if (number == 1)

            return false;

      if (number == 2)

            return true;

      if (number % 2 == 0)

            return false;

      for (int d = 3; d <= (int) Math.sqrt(number); d++)

            if (number % d == 0)

                  return false;

      return true;

}

C++ implementation

bool isPrime(int number) {

      if (number == 1)

            return false;

      if (number == 2)

            return true;

      if (number % 2 == 0)

            return false;

      for (int d = 3; d <= (int)sqrt((double)number); d++)

            if (number % d == 0)

                  return false;

      return true;

}

Recommended books

1. Victor Shoup. A Computational Introduction to Number Theory and Algebra.
2. Peter J. Giblin. Primes and Programming.
3. David M. Bressoud. Factorization and Primality Testing.
4. Hans Riesel. Prime Numbers and Computer Methods for Factorization.

One response to "Primality test (naive approach) tutorial"

1. Observer on April 17, 2009 said:

   The for loop in the above code is as:
   

   for (int d = 3; d <= (int)sqrt((double)number); d++)

   However since we have already tested for even numbers, i.e. number % 2, we can safely increment the count to d + 2:
   

   for (int d = 3; d <= (int)sqrt((double)number); d = d + 2)

   Undoubtedly. But our primary goal was to show the naive approach and it's unsuitability to work in real cryptography applications. We can increase the speed of the algorithm with the enhancement you've suggested, but it still won't give us suitable asymptotic complexity.

Leave a reply
Your name (optional):
Your e-mail (optional):
Message: