Clerro
 Write a guidebook
 4.7 .. 27 reviews
 2245 Views
•  What are Prime Numbers and why are they so cool?
•  Importance of Prime Numbers in Cryptography
•  Trial Division
•  Wilson's Theorem
•  Fermat's Little Theorem
•  Miller-Rabin Test
•  Other tests
Primes and Primality Testing

Chapter 1 of 7

What are Prime Numbers and why are they so cool?

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.

By definition,

A prime number is a natural number that has no positive divisors other than 1 and itself.

Meaning -

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 -

1. Divide 199 by every number between 1 and 199.
2. 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

$\LARGE 199 \div 2 = 99 \ with \ R:1$

Case 2 : Division by 3

$\LARGE 199 \div 3 = 66 \ with \ R:1$

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 -

$\LARGE 199\div5= 39\ with\ R\ :\ 4$

Case 5: Division by 7 -

$\LARGE 199 \div 7 = 28 \ with \ R:3$

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 -

$\LARGE 199 \div 11 = 18 \ with \ R:1$

Case 8: Division by 13 -

$\LARGE 199 \div 13 = 15 \ with \ R:4$

Case 9: Division by 17 -

$\LARGE 199 \div 17 = 11 \ with \ R:12$

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 -

$\LARGE 199 \div x = q \ with \ R:0$

which means -

$\LARGE q \ast x = 199$

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

$\LARGE 199^{883,467}$

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.

Chapter 2 of 7

Importance of Prime Numbers in Cryptography

Everytime you shop online, you are required to send your bank login details through to your bank, for completing the transaction.

Encryption makes sure no one can get access to your bank details and steal from you.  We're not going to dive deep into it, but here's how encryption basically works -

• The bank sends your computer a public key which could be a set of two numbers (N, C). It is used to encrypt your bank details (using math functions like modulus, etc.) so no one else can intercept and read it.
• Upon receipt of your details, the bank decrypts your bank details using a private key (P1, P2) which no one else, but the bank has.

Unless someone knows what P1 and P2 are, they simply cannot decrypt and get access to your bank details.

Here's the fun part now - both P1 and P2 are prime numbers - really large ones! And anyone who gets access to those, can decrypt and read your details.

So can't someone do that? Practically, not quite. You see, the component 'C' in the public key, is basically -

$\LARGE P1\ \ast \ P2\ =\ C$

While it's easy for a computer to calculate P1 times P2 and generate a C, it's practically very, very cumbersome and time-taking for even the fastest ones to work this simple equation backwards and find the prime factors of C, ie. P1 and P2.

With the current computing power, it could take a computer program years to find these monster prime factors, P1 and P2, of the composite number C used in the public key.

Anyway, this is what fundamentally makes encryption the most powerful tool in modern day cyber security.

Interestingly enough, in 1992, Peter Shor came up with an algorithm that takes in a number N and spits out it's prime factors. The catch is that Shor's algorithm can only run on a quantum computer (that's if we could build one with sufficient number of qubits and if it can work without succumbing to noise or other quantum decoherence phenomena).

Now that you have an idea how cool prime numbers can get, here's a short video for you to dive a little more deeper into encryption using prime numbers -

Next, we jump on to some popular methods for testing prime numbers and a possible algorithm we can write (in python) for each of those.

Chapter 3 of 7

Trial Division

We discussed all about testing whether or not a number is prime using trial division - which could get fairly frustrating.

No matter how frustrating, this method is deterministic in detecting a prime (resulting in100% in accuracy), contrary to most methods which are probabilistic in nature.

And so, if I had to write a program which could take in any number N and spit out the boolean - "True" only if N is prime, i'd write this :

Let's try to make the range (2, N) shorter here, so our program has a comparitively shorter runtime for slightly bigger numbers too.

Let's assume for a moment that N is composite. In that case, it has factors p and q -

$\LARGE p\ *\ q\ =\ N$

$\normalsize \mathtt{\textcolor{#edc680}{for\ all\ 2\leq\ p,q\ \leq(n-1)}}$

Now, if

$\LARGE p\ > \sqrt N\ and\ q\ >\ \sqrt N$

then clearly,

\LARGE \begin{aligned}p\ *\ q\ &\gt \sqrt{N}\ * \sqrt{N}\ \\ p\ *\ q\ &\gt\ N \end{aligned}

Which is not true! Because it contradicts  -

$\large p\ *\ q\ =\ N$

This implies  -

$\large Either\ of\ p,q\ must\ be\ lesser\ than\ \sqrt{N}$

Meaning, if we keep the range of our function between 2 and sqrt(N), we should definitely get one of it's factor (q or n) in case it's a composite number. And that's all we really need to prove it's not prime.

With that, we drastically reduce the amount of work our program would have to do.

The function could be written as -

This function is more efficient and lesser time exhaustive than the previous one, simply because it has lesser numbers to operate division on.

### How much time do we save by reducing the range?

To demonstrate this, let's just start a timer function in the beginning of our primality test and stop it right before the test returns some value.

Here's the required code for the shorter range function (same can be applied to the long range function) -

I used both functions to check the primality of the 10,000th prime number -

$\LARGE 104,729$

The function will take N = 104729 as an argument and print the runtime before returning the boolean True.

Runtime for function with range(2, N) :

Runtime for function with range(2, N)

Runtime for function with range(2, sqrt(N)+1) :

Runtime for function with range(2, sqrt(N)+1)

Let's discuss other testing methods and see what's the runtime like for a computer program.

Chapter 4 of 7

Wilson's Theorem

Wilson's theorem comes right out of the number theory and is a deterministic (resulting in100% in accuracy) method to find primes. It states that -

A natural number p, such that :

$\large p\ \gt\ 1$

is prime, if and only if :

$\large (p-1)!\ \equiv\ -1\ (mod\ p)$

I'm not going to dive deeper and demonstrate a proof here, but we'll check for this theorem to confirm 7 as a prime, then jump to writing the function for it and calculating the runtime.

### Testing Wilson's theorem for 7

For p = 7, Wilson's Theorem gives us -

$\large (7-1)!\ \equiv\ -1 \pmod 7$

which implies -

$\large (7-1)! \mod\ 7\ =\ -1 \mod\ 7$

$\large \begin{gathered} \large (7-1)! \mod\ 7\ =\ 6! \mod\ 7 \\ \Downarrow\\(6*5*4*3*2*1) \mod\ 7\\\Downarrow\\ 720 \mod\ 7\ =\ 6 \end{gathered}$

If 7 is prime (which - spoiler - it is!), then the right side of the equation must be equal to 6. And is it?

$\large -1 \mod\ 7\ =\ 6$

Sure, is. And so, 7 is prime.

### Program for testing

So let's write a function that could perform a primality test on a number using Wilson's theorem...

The runtime for this is quite poor. Testing for the same number - 104,729, the runtime was -

Runtime for primality test using Wilson's theorem

That's half as fast, compared to trial division using range (2,n).

So I'd still prefer the trial division test with range (2, sqrt(n)+1) for a primality test, which is about 300 times faster than the other two we have tried.

Chapter 5 of 7

Fermat's Little Theorem

Fermat's theorem states -

$\small \begin{gathered} \text{Let\ }p\ \text{be\ a\ prime\ number\ and\ }1\ \leq\ a \leq\ p\ \text{any integer.\ Then, } \\ \\ \large (a^p\ -\ a)\dashrightarrow\ divisible\ by\ p \end{gathered}$

Here's a sweet proof to this.

Primality testing using Fermat's theorem (pronounced : " Fermaa's ") is probabilistic in nature. This means you can never be 100% sure if 'p'  is prime.

Let me demonstrate this test using a prime number 5. According to Fermat's little theorem, all integers (a) between 1 and 5 (including 1 and 5) will give a number  -

$\large (a^5\ -\ a)$

$\large 1^5\ -\ 1\ =\ 0 \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 5}$

$\large 2^5\ -\ 2\ =\ 30 \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 5}$

$\large 3^5\ -\ 3\ =\ 240 \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 5}$

$\large 4^5\ -\ 4\ =\ 1020 \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 5}$

$\large 5^5\ -\ 5\ =\ 3120 \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 5}$

Looks like it works perfectly.

Let's try another number - 341. Brace for some huge numbers -

$\large 2^{341}\ -\ 2\ =\ \scriptsize {\begin{matrix}4479489484355608\\4211148845611368\\8855624329099446\\9299069799978201\\9275837423603218\\9076175498654321\\4231550 \end{matrix}} \dashrightarrow\ \small \textcolor{#228B22} {divisible\ by\ 341}$

$\large 3^{341}\ -\ 3\ =\ \scriptsize {\begin{matrix}4 992 842 419 769 444411 575 714 115 125\\880 074 355 727 994157 202 873 032 702\\852 991 828 893 873287 975 661 182 639\\605 572 486 502 613841 657 002 635 137\\622 031 360 394 139015 053 716 643 508\\803 196 884 400 \end{matrix}} \dashrightarrow\ \small \textcolor{#e5260d} {\begin{matrix}not\\ divisible\ by\\ 341\end{matrix}}$

Wait. What just happened there?

While applying Wilson's theorem to 341, when we have :

$\large a\ =\ 2\ \dashrightarrow\ \textcolor{#228B22}{341\ is\ prime}$

But when we have :

$\large a\ =\ 3\ \dashrightarrow\ \textcolor{#e5260d}{341\ is\ not\ prime}$

And we actually do have factors of 341 -

$\large 11\ *\ 31\ =\ 341$

proving that it is a composite number.

And that's why we call 341 a pseudoprime. Because it passes Fermat's primality test for base 2.

Interestingly, in the above example, 2 is called Fermat's liar because it suggests 341 is a prime and 3 is called Fermat's witness because it proves 341 is composite.

Key takeaway here is that -

While applying Fermat's theorem for primality testing, a number has to fail the test just once to be ruled out as composite - with confidence.

### Carmichael Numbers

To make things worse, there actually exists an infinite set of numbers (found at a very, very low frequency) that will pass Fermat's test for all bases, and are still composite!

We call these Carmichael numbers.

561 is the first carmichael number. And believe it or not, it passes Fermat's test for every base - meaning :

$\large 2^{561}\ -\ 2\ \dashrightarrow\ \small \textcolor{#228B22} {\begin{matrix}divisible\ by\ 561\end{matrix}}$

$\large 3^{561}\ -\ 3\ \dashrightarrow\ \small \textcolor{#228B22} {\begin{matrix}divisible\ by\ 561\end{matrix}}$

$\large 4^{561}\ -\ 4\ \dashrightarrow\ \small \textcolor{#228B22} {\begin{matrix}divisible\ by\ 561\end{matrix}}$

$\LARGE \begin{gathered}...\\... \end{gathered}$

$\large 560^{561}\ -\ 560\ \dashrightarrow\ \small \textcolor{#228B22} {\begin{matrix}divisible\ by\ 561\end{matrix}}$

And yet -

$\large 561\ =\ 3\ *\ 11\ *\ 17 \dashrightarrow\ \textcolor{#F70808}{Composite!}$

Carmichael numbers are quite rare to find though. In the first 25 billion numbers, there are only 2183 numbers that are charmichael.

These caveats, where Fermat's test may tell us a number is prime while it may just be a Pseudoprime or Carmichael, are what make Fermat's test probabilistic in nature.

Nevertheless, let's see how we can increase the probability of our result to be maximum and write a program for this.

### Program for testing

Let's start off by simplifying the testing equation so we can easily write a logic around it. We need to check -

$\large \begin{gathered} \large \mathsf{if\ }p\ \mathsf{divides\ }a^p-a \\ \Downarrow\ \\ a^p \equiv\ a \mod\ p \end{gathered}$

Now, if 'p' is prime, it doesn't share a factor with 'a' and the greatest common divisor - GCD (a,p) is always 1. Applying the cancellation law, we can re-write the above equation as -

$\large \begin{gathered} a^{p-1} \equiv 1 \mod\ p \\ \Downarrow\\ a^{p-1} \mod\ p \equiv 1 \end{gathered}$

Now, we can build a logic for our function much more easily. Here's what our function will do -

1. Take any input 'p' (for testing if it's prime).
2. Generate a random integer 'a < p'
3. The function will first check if -
GCD(a, p) = 1
If 'not' ----> then 'p' is definitely composite!
4. If GCD (a, p) = 1, then we move on to apply Fermat's test.

$\normalsize \begin{gathered} a^{p-1} \mod\ p\ =\ 1\ \rightarrow\ \textcolor{#228B22}{p\ is\ prime} \\ a^{p-1} \mod\ p\ \neq 1\ \rightarrow\ \textcolor{#f70808}{p\ is\ composite} \end{gathered}$

Now, to increase the probability of our result to be accurate, we can repeat the test 'k' times for several random values of 'a'. This way, it'll be less unlikely that 'a' would turn out to be Fermat's liar each time.

So the program would take 2 arguments - the number to test (p) and the number of times we want the test to repeat (k) with random 'a' values. Here's the code -

Do you notice how the number of tests our function has to perform does not scale with the number, unlike trial division?

This is key to Fermat's primality test performance. It's runtime is drastically lower than trial division test for large numbers.

I calculated the runtime for testing the prime -

$\LARGE 54734431$

Here's what I got with trial division (short range) :

Runtime for Trial division

And here's the runtime for Fermat's test with 100 repetitions (k = 100)

Runtime for Fermat's test

About 30 times faster. And this will increase further for bigger and bigger numbers as per the relation -

$\normalsize O\ (k\ * \log^2p\ *\ \log\log p\ *\ \log\log\log p)$

where 'k' is number of times we test and 'p' is the number that's being tested.

Fermat's test is fast, no doubt. But the probabilistic nature and the chance of encountering carmichael numbers could make one question it's reliability.

Chapter 6 of 7

Miller-Rabin Test

This test works as fast as Fermat's test with an added bonus of detecting carmichael numbers!

Here's how it works -

To test a number 'p' for primality, choose a number -

$\large a\ \lt\ p$

Now let there be a number 's' an odd number 'd', such that -

$\large 2^s*d = p-1$

If the following holds true -

\large \begin{aligned}a^d\ \ &\rlap{\, /}{\equiv} \ \ \ \ \ \ 1 \pmod p\\&and\\ a^{2^{r}*d}\ \ &\rlap{\, /}{\equiv}\ -1 \pmod p \end{aligned}

$\small for\ all\ 0\ \le\ r\ \le\ (s-1)$

'p' is composite and 'a' is the witness of it. Else, 'p' is probably prime.

This clearly means that the Miller-Rabin test is contrapositive to testing a prime. It tells you whether a number is composite or not. If not, it 'probably' is a prime.

### Example application : Is 31 prime?

We've got -

$\large p\ =\ 31$

Next, we need to find an 's' and 'd' such that -

\large \begin{aligned}p-1\ &=\ 2^s*d \\ \Rightarrow\ 31-1\ &=\ 2^s*d \\ \Rightarrow\ \ \ \ \ \ \ \ 30\ &=\ 2^s*d \end{aligned}

We can write 30 as -

$\large \begin{gathered} 30\ =\ 2^1*15 \\ \therefore\ \ \ s\ =\ 1\ \ and\ \ d\ =\ 15 \end{gathered}$

Having found 's' and 'd', we can now pick a random 'a', such that -

$\large a\ <\ p\ (p=31)$

I'll work here with a = 2 for the sake of simplicity.

Now, if for 31 to be composite, each of the following must hold true -

\large \begin{aligned}a^d\ \ &\rlap{\, /}{\equiv} \ \ \ \ \ \ 1 \pmod p\\&and\\ a^{2^{r}*d}\ \ &\rlap{\, /}{\equiv}\ -1 \pmod p \end{aligned}

which can be written as -

\large \begin{aligned}a^d\ \mod\ p \ \ &\rlap{\, /}{\equiv} \ \ \ \ \ \ 1 \mod\ p\ \\ &and\\ a^{2^{r}*d}\ \mod\ p \ \ &\rlap{\, /}{\equiv}\ -1 \mod\ p \end{aligned}

Let's get on to testing the first inequivalence. Computing the left side, we got -

$\large 2^{15} \mod\ 31\ =\ 1$

And the right side would be -

$\large 1 \mod\ 31\ =\ 1$

So we get -

$\large a^d \mod\ p\ \equiv \ 1 \mod\ p$

Hence, 31 failed the very 1st test for being composite. And so, it's probably a prime number

### Program for testing

Miller-Rabin is, again, a probabilistic primality test. And since it involves a base variable 'a', by running the test 'k' times, we can increase the probability of our outcome to be more accurate.

Here's what we'll need to do in our code -

1.  If the number is 2 or 3, the function will simply return 'Prime'.
2. If not, we will check if the given number 'p' is even. If it is, it's definitely composite (multiple of 2).
3. If not, we will find variables 's' and 'd' such that -
(2^s)*d = p-1.
4. Finally, we will loop the function to generate random number 'a' < 'p' each time and begin testing via the two inequality relationships.

Here's what we have -

As mentioned earlier, the runtime for this is almost equal to Fermat's test.

Let's discuss some other cool tests in the next section.

Chapter 7 of 7

Other tests
There many more tests out there with varying accuracy and speed. I'm going to discuss some in this section and perhaps keep adding updates to this guidebook as more tests surface.

### Solovay–Strassen Test

This is quite similar in performance as the Rabin-Miller test but slightly less accurate. To test a number 'p', find an integer 'a' < 'p'.

If the expression -

\large \begin{aligned} a^{(p-1)/2}\ \ \rlap{\,\,\,\,/}{\equiv}\ \ \left( {\dfrac{a}{p}} \right) \pmod p\ \end{aligned}

then 'p' is composite and 'a' is the witness of it.

### Lucas Test

Lucas test is another probabilistic, contrapositive primality test. It tells you whether a number is 'p' composite. If not, it may be prime.

So this test is dependent on the Lucas sequence. It's similar to the Fibonacci sequence with the only difference that the second element is 3, instead of 1.

$\large \begin{gathered} 1,3,4,7,11,18,29,47,76,123,... \\ \footnotesize \mathsf {Lucas\ sequence :E\scriptstyle(i)}\ \mathsf {= E \scriptstyle(i-1)} \mathsf{+E \scriptstyle(i-2)} \end{gathered}$

Now let me demonstrate how this test works -

For 5 to be prime, pick the 5th element in the sequence (11) and take 1 from it -

$\normalsize 11-1=10$

All we need to do now is to check if 10 is a multiple of 5. If it is, then 5 may be prime. If not, it's composite.

In this case -

$\normalsize \begin{gathered}10=5*2 \\ \therefore 5\ is\ not\ composite.\ \end{gathered}$

### The Lucas-Lehmer Test (LLT)

This is a deterministic test to test out any Mersenne Prime!

Mersenne prime numbers are primes that can be expressed as one less than some power of two.

For example -

\small \begin{aligned} 3&=2^2-1 \\ 7&=2^3-1 \\ 31&=2^5-1 \\ ...\ & and\ so\ on \ \end{aligned}

Now this test, is dependent on a sequence called the Lucas-Lehmer sequence. Where every number is 2 less than the square of it's predecessor -

$\large \begin{gathered} 4,\ 14,\ 194,\ 37634,\ 1416317954,\ ... \\ \footnotesize \mathsf {Lucas-Lehmer\ sequence :E\scriptstyle(i)}\ \mathsf {= (E \scriptstyle(i-1)} \mathsf{)^{2}-2} \end{gathered}$

Although the series gets monstrous very quickly, the test is fairly simple. For any mersenne number 'N' -

$\large N = 2^p-1$

find the (p-1)th element in the Lucas-Lehmer sequence and see if 'N' divides that element. If it does, 'N' is definitely prime. If not, it's definitely composite!

Let's check if 7 - a mersenne number is prime or not. 7 can be written as -

$\small \begin{gathered} 7=2^3-1 \\ which\ gives\ p=3 \end{gathered}$

So we need to check if the (p-1)th element ie. the 2nd element, which equals 14 is multiple of 7...

$\small \because 7\ divides\ 14$

$\small \therefore 7\ is\ definitely\ prime.$

### Modified, faster LTT

Since LTT is deterministic in nature, it's worth tweaking it so we have a faster Mersenne Prime algorithm. So what we can do is, make the Lucas-Lehmer sequence simpler.

Here's how we do it -

1.  To test a number 'N', build the Lucas-Lehmer sequence as usual until you reach the element which is larger than 'N'. This should be easy, as the sequence starts spitting bigger numbers very soon.
2. Next, replace that first element (E) that's bigger than 'N' with (E mod N).
3. To get the next number from here on, simply find ((E^2)-2 mod N).

If 'N' is prime, you will reach a point in the series where an element is 0. And you would have found 'N' to be prime without dealing with any monster number.

### AKS Primality Test

This is probably the most efficient deterministic test and one that a lot of mathematicians are excited about. It has a fairly okay runtime and it's 100% accurate.

So, to test 'P' we start off by building a polynomial -

$\large (x-1)^p\ -\ (x^p-1) \ \small \dashrightarrow equation 1$

If all coefficients of  equation 1 are divisible by 'p', then 'p' is 100% prime.

Let's test p = 3.

The polynomial should be -

$\small \begin{gathered}(x-1)^3\ -\ (x^3-1) \\ \Downarrow \\ -3x^2\ +\ 3x \end{gathered}$

Clearly, the coefficient 3 is divisible by p = 3.

$\small \therefore \ 3\ is\ prime.$

Rate this guide
(Doesn't require signup)
Submit