8.5. Running Time of the Naive Algorithm

The naive algorithm for primality testing is based on the fact that if a number p is composite, it will have a divisor less than or equal to the square root of p. To check if p is prime, we iterate over all integers from 2 to the square root of p and check if any of these numbers divide p without leaving a remainder. If any number does, p is composite; otherwise, it is prime.

The naive algorithm works by taking an integer p and testing whether any integers from 2 up to the square root of p can divide p evenly. The reasoning is that any factor of p, if it exists, must not exceed the square root of p. For example, if p is 36, its divisors include numbers smaller than 6 (the square root of 36), like 2, 3, 4, and 6. If any of these divide 36 evenly, we conclude p is composite. If we reach 6 without finding any divisors, we conclude p is likely prime.

Think of it like testing whether a key fits into various locks. If you have a set of locks (the numbers from 2 to √p), you only need to check those that could possibly fit (the factors of p). If you find one that fits, the lock (the number p) is not unique (composite); if not, it might be unique (prime).

The running time of the naive algorithm relies on the number of divisions performed, which is equal to the integer part of the square root of p. However, if p is represented by an n-bit number, this results in a worst-case scenario of performing about 2^(n/2) divisions. Therefore, while the algorithm seems polynomial, its actual complexity is exponential in terms of the number of bits used to represent p.

The complexity of the naive algorithm suggests that for an n-bit number, the maximum value p can take is 2^n. The square root of this is √p = 2^(n/2). Thus, the number of divisions we might need to make is about 2^(n/2), which grows very quickly as n increases. Although the process is only doing basic arithmetic (divisions), the sheer number of operations required leads us to classify this algorithm as exponential time because the operations grow exponentially with the size of the input.

Imagine trying to find a 'secret entrance' in a giant maze. The maze’s size doubles (exponentially) as you check each possible entrance. Even if it seems like checking doors (divisions) is simple, the time it takes grows extraordinarily fast with each new entrance, much like how the performance of the algorithm declines as p gets larger.

A significant breakthrough was made in 2002 with the development of the AKS primality testing algorithm, which is a polynomial time algorithm for primality testing. This algorithm can determine whether a number p is prime in a runtime that is polynomial with respect to the number of bits needed to represent p.

The AKS algorithm is important because it can verify the primality of a number p effectively in a time that grows polynomially with the length of p’s binary representation, or the number of bits n. For large integers, algorithms that run in polynomial time are feasible and efficient because they manage computational resources better than exponential time algorithms, which become impractical even for moderately large inputs.

Think of baking cookies. If you have a recipe that takes an exponentially long time to make each additional dozen, you might only bake a few. But with a polynomial recipe, even if you double the quantity, it still remains manageable. The AKS algorithm ensures that even very large numbers can be tested for primality without taking an unreasonably long time.

--