8.4. Naive Algorithm for Primality Testing

The algorithm uses the fact that if at all your given number p is a composite number then it will have a divisor which is less than equal to the square root of that number. The proof is very simple. So, let p be a composite number and since p is a composite number it will have a factor say a. The factor will be definitely greater than 1 because the definition of composite number is that it should have at least 1 factor different from 1 and the number itself. So, the factor a will be greater than 1 and less than p. And then since a is a factor I can say that there is a b such that a * b = p.

In this chunk, we learn about composite numbers and their properties. A composite number p must have divisors other than 1 and itself, meaning it has factors. If you have a factor a, then there is another factor b that, when multiplied by a, gives you p. Importantly, if a is a divisor, then one of the divisors (either a or b) must be less than or equal to the square root of p. This is essential for simplifying our primality testing algorithm.

Imagine you are at a sports competition with a group of people. If you have a team with 15 players, you can form smaller teams of 5 players each. If you check each smaller team (team of 5) against the total (15), you will always find the total to be divisible by at least one of these smaller teams (5). This is analogous to finding divisors of a composite number.

Based on this theorem, the naive algorithm is as follows. So, you are given an input number p you want to check whether it is prime or composite, you know that if at all it is composite, then it will have a factor within the range square root of that number. So, you try to check whether it has at least 1 factor within the range 2 to √p. You range over all possible values of i between 2 to √p and check whether the number i divides p or not. If you encounter any i then you can declare that p is composite, but if none of the numbers 2, 3, ..., √p divides your p then you can declare your p to be prime.

The naive algorithm for checking if a number p is prime involves testing potential divisors. You only need to check divisors up to the square root of p (√p). The steps are: First, list integers starting from 2 up to √p. For each integer i, check if it divides p without a remainder. This is done using the modulus operation (p mod i == 0). If you find any such i, p is composite. If you don’t find any factors in that range, then p is prime.

Think of trying to determine if a number is like finding out if a specific LEGO piece is a part of a larger build. You only need to check certain pieces (up to a point) to know if they fit in. If none of those pieces fit, you conclude that the piece can stand alone, just like concluding the number is prime.

Now, what is the running time of this algorithm? There are √p iterations and in each iteration, you are performing a division. Our measurement here will be how many divisions you are performing to declare whether a given number p is prime or not. So, you will need √p divisions. This may seem polynomial, but if p is represented by an n-bit number, the magnitude of √p can be as large as 2^(n/2). Therefore, this appears exponential in terms of the number of bits used to represent p.

When considering the efficiency of the naive algorithm, we find that it performs roughly √p iterations, each involving one division. However, if p is enormous, say a number represented with n bits, then √p becomes large as well (specifically 2^(n/2)). Thus, while it looks polynomial, it behaves exponentially with respect to the number of bits required to represent p, making it inefficient for large numbers.

Imagine you are searching for something in a vast library. Each shelf you check represents an iteration, and each book you open represents a division. If the library (number) is huge (high number of bits), even if you check half the books (square root), it still takes an enormous amount of time, showing it feels exponential as the size grows.

You might be wondering if a polynomial time algorithm exists. It was a long-standing problem until the AKS primality testing algorithm was proposed in 2002. The AKS algorithm can determine if a number p is prime in polynomial time with respect to the number of bits needed to represent p. However, the details of the AKS algorithm will not be covered here.

The naive algorithm's inefficiency sparked interest in discovering better methods for testing primality. The AKS algorithm is a breakthrough because it operates efficiently in polynomial time based on the number of bits required for the number's representation. Understanding how it works requires more advanced mathematical knowledge, but its existence addresses the earlier concerns of finding a polynomial time solution.

Consider a detective trying to crack a case using old methods which consume a lot of time. Eventually, a new tool is invented that allows the detective to solve cases much faster. Similarly, the AKS algorithm represents a significant upgrade over naive methods, making the process of determining primality quicker and more efficient.

--