8.6. AKS Primality Testing Algorithm

Now, the next question is how exactly we check whether a given number is a prime number or not. So, I will be discussing the naive algorithm, which many of you might be aware of. 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. And 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. And 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 times b = p that means that b is basically . So, now, the claim of the theorem statement here is that either ≤ or ≤ and this can be easily proved using contradiction. So, on contrary assume that > and >. Then this gives me a contradiction that > , which is not the case because my premise is that p is equal to the product of a and b. 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, that is what you try to do here you try to 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, 4, √p divides your p then you can declare your p to be prime.

The naive primality testing algorithm checks whether a number p is prime by verifying that it has no divisors other than 1 and itself. This is done by testing for divisors in the range from 2 up to the square root of p. If any integer divides p evenly (i.e., if p modulo that integer equals zero), then p is declared composite. If no such divisor is found, then p is prime. This method relies on the fact that any composite number must have at least one factor less than or equal to its square root, which ensures the algorithm doesn't have to check all numbers up to p.

Imagine trying to determine if a number of apples you have is a special kind called prime apples. Instead of checking every single apple (which would take forever), you only check those apples that are half as many as the total. If you find any apple that can pair perfectly with another without leftovers, you know those aren’t special apples (composite). If none can pair up evenly, then you can conclude you have special prime apples!

So, you might be wondering, this is a polynomial time algorithm, but that is not the case. So, imagine p is represented by an n bit number then the magnitude of your √p will be 2^(n/2), because your p could be as large as 2^n. So, √p could be as large as 2^(n/2). So, it might look like a polynomial time algorithm, but it is not, it is an exponential time algorithm exponential in the number of bits that you need to represent your value p. So again, take the case when n is equal to say 1024 bit, and say your p is as large as 2 to the power 1024 bit number, then basically your i is between 2 to something of order 512. That means you will be basically performing these many divisions: 2^512 divisions to check whether a given number p of 1024 bit is a prime number or not. And this is an enormously large quantity; it is not a small quantity. So, this is not a polynomial time algorithm.

The naive algorithm, while seemingly straightforward, has a significant limitation regarding its time complexity. When considering very large numbers (n-bit numbers), the number of iterations it requires grows exponentially, specifically it performs up to 2^(n/2) iterations. This is due to the requirement of checking all possible divisors up to the square root of p. Therefore, for large n (such as n = 1024), it can require an unmanageable number of calculations, categorizing the algorithm as exponential rather than polynomial time.

Think of trying to find the best route for a road trip. A naive approach would be to check every possible combination of stops, which could mean considering billions of routes. It may seem feasible for a few stops, but once you add more destinations, it quickly becomes an unmanageable task. Unlike strategically selecting the most promising routes, the naive approach leads to an overwhelming amount of possibilities to explore.

Now, you might be wondering that whether we have a polynomial time algorithm or not. And coming up with a polynomial time algorithm for checking whether a given number is prime or not had been a long standing open problem, people thought that we do not have any polynomial time algorithm. But in 2002, there was this algorithm proposed called as AKS primality testing, which is a polynomial time algorithm. Polynomial in the number of bits that you need to represent your input number p and this is called Agarwal Kayal Saxena primality testing algorithm which in polynomial time can tell you whether your given number p is a prime number or not.

The AKS primality testing algorithm was developed to provide an efficient method for determining if a number is prime. Unlike the naive algorithm, which has exponential complexity for large numbers, the AKS algorithm operates in polynomial time relative to the number of bits required to represent the number being tested. This breakthrough mixed theoretical computer science and mathematics, proving that a polynomial-time algorithm exists.

Imagine you’re trying to find out if a book is a rare first edition. Instead of going through every single title (like the naive method), an organized library system can quickly filter through databases to much more efficiently find what you’re looking for. The AKS algorithm is that efficient system – it cuts through heavy computational requirements to quickly deliver results.

So, due to interest of time, I would not be discussing the AKS primary key testing algorithm but if you are interested you can see the original paper the paper title was “Primes is in P.”

While this lecture does not delve into the specific workings of the AKS algorithm, it is important to note that it revolutionized the field of number theory by demonstrating that prime testing could be done in polynomial time. Interested students are encouraged to further explore the original work, titled ‘Primes is in P,’ for more detailed insights into this groundbreaking achievement.

Think of this like a teaser for a thrilling book or movie. The excitement lies in its potential and what it promises. While the lecture didn't explore every detail of the AKS algorithm, it sparks interest, encouraging further exploration and discovery into its fascinating concept.

--