For layman's sake, I'm going to start off by clarifying what prime numbers are, trial division to detect one and their basic application in cryptography. Feel free to jump on to the sections on primality testing, if you're only looking for those.
A prime number is a natural number that has no positive divisors other than 1 and itself.
A prime number is a number that has exactly two factors : 1 and itself.
For example, 14 is not a prime number because it has two additional factors (numbers that multiply together to form 14) - 2, 7, besides 1 and itself. Hence it's not prime but the opposite of it - composite.
5, however, is a prime. It has no other factors except one and itself. So do 7, 13, 19, 23 and so on.
Primality Testing - finding out if a number is prime or not.
From the definition, it's pretty easy to conclude that for testing whether or not a given number is prime, simply look for it's factors. If there are more than two inevitable factors (1 and the number itself), the given number is not a prime.
Let's try to do that with a random number. Say, 199.
From our discussion above, 199 has two obvious factors - 1 and 199 itself. If 199 has no other factors, it's a prime. Else, it's composite.
So all we gotta do is -
- Divide 199 by every number between 1 and 199.
- Check the remainder in each case.
If we find even one single case, where the remainder is zero, it means 199 has a third factor apart from 1 and itself, making it a non-prime, composite number.
That's 197 instances of division starting at 2 and ending at 198 -
Case 1 : Division by 2
Case 2 : Division by 3
Case 3: Division by 4 -
We can skip this. Because if 4 was a factor of 199, 2 would have been too - which it isn't.
That said, we can skip all multiples of 2 - all even numbers.
Case 4: Division by 5 -
Case 5: Division by 7 -
Case 6: Division by 9 -
We know 9 is a multiple of 3 and if it were a factor of 199, 3 would be too - which it isn't.
This means we can skip 9 and all other multiples of 3.
Same is true with all multiples of 5, 7,11, 13..and all other prime numbers.
So for our basic primality test, it's enough if we divide 199 by all prime numbers between 1 to 199. So we jump on straight to 11, skipping 9 and 10...
Case 7: Division by 11 -
Case 8: Division by 13 -
Case 9: Division by 17 -
Did you observe something?
The quotient has been reducing as we go ahead in our division streak and divide 199 with bigger numbers. If you go further head, the quotients will become even more smaller.
For a moment if we assume 199 is not prime, there must be a divisor 'x' and a quotient 'q' with no remainder -
which means -
meaning, the number we are dividing 199 by (x) and the quotient that comes out (q) are both, factors of 199.
But in case 9 above, neither 17(the divisor) nor 11(the quotient) are factors of 199.
Given that the quotient will go on decreasing below 11, case 9 onwards, we know there aren't any factors of 199 below 11 (we checked them all). Since both the quotient and divisor need to be factors of 199 for it to be composite, we need not check for any number greater than 17 in this case (because the quotient will always be lesser than 11).
So, it's quite legit to say that we can stop our trial division once the quotient becomes smaller than the divisor.
Finally, we can save ourselves from several other attempts of division and safely say that 199 is a prime.
Why prime numbers are so cool
Imagine using the above method to test whether the number
is prime or not.
Testing if a large number is prime.
There's no slick trick to check fast enough, whether or not a large number is prime. So much so that finding large prime numbers has been an obsession for mathematicians.
Also, the very fact, that finding large prime factors of a number is hard, is the basis of cryptography which is fundamental to cyber security.
I'll try to walk you through how this works briefly, so you get a ballpark idea and are able to appreciate prime numbers even more.