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.

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.

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.

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.”