Primality Tests-Computational Number Theory
Computational Number Theory is the study of computational methods for solving problems in Number Theory which includes devising algorithms for Primality Tests, integer factorization.
A natural number (0,1,2….) which is also greater than 1 and has exactly one positive integer divisor other than 1, itself, is a Prime Number. Algorithms for determining whether a given number is Prime or not is known as Primality Test.
So why are we talking about Prime Numbers and Primality Tests? What’s so important?
Primality Tests, other than the field of mathematics, are used in cryptography. For instance, RSA is a public cryptosystem that is used for Secure Data Transmission. RSA Encryption uses two large prime numbers(p,q) to generate a public key, which the sender uses for encrypting the message. The sender also selects an auxiliary value (e). The receiver uses this (e) and a value (d) which can only be known through the value of p,q. RSA encryption is used for E-mails, Digital Transactions, and for a lot more. I am not going into the mathematical part of RSA encryption, that is for some other time. For now, we are going to stick with the primality tests.
We can classify various Primality Tests into essentially 2 types of Methods.
- Deterministic Methods
- Probabilistic Methods
As the name suggests, Deterministic methods provide an absolute certainty whether a number is prime or not. Deterministic tests include the Simple Methods, Pocklington-Lehmer Test, Cyclotomy Test, Elliptic Curve Primality Test, AKS Primality Test. There are more tests but these are foremost.
Whereas, Probabilistic methods can find a potential Prime number,i.e; the determined number may or may not be Prime. Probabilistic tests include Fermat Primality Test, Miller-Rabin Test, Solovay-Strassen Test, Frobenius Primality Test, Baillie-PSW Primality Test.
We will go through most of these tests over a series of blogs. In this particular blog, we will see the naive approach and simple methods.
In the code snippet below, we are checking if n is divisible by any number between 2 to n-1. This type of approach is known as Trial Division.
We know that if a number is composite, we will find all its factors (except itself) in the range 2 to n/2. We will use integer division // for excluding the decimal part. So we just have to change the upper bound of the loop on line 3.
Now we know every factor of n (except 1,n) is in between 2 to n/2, but we are only checking if the number is prime or not, we don’t need every factor, we just need only one factor other than 1 and n, to know whether the number is prime or not.
There’s another observation that we will encounter some factors twice for e.g. n=64, factors of n are 2,4,8,16,32. So if we write factors as a list of products, 2*32, 4*16, 8*8, 16*4, 32*2. We can see after 8*8, factors are repeating. So we can small down our range of loop, to 2 to √n.
Now we have reduced the iterations from max n-3 times to max √n -2 times.
We can also determine quickly every even number greater than 2 because it is already divisible by 2. We can improve this method more if we also check whether the number is divisible by 3. Thus, we have checked our number with every multiple of 2 and 3 within the range 2 to √n. Then we will start our iteration from i=5 to √n while checking numbers between i and i+6 every iteration and incrementing i by 6.
The function will look like this —
Let us understand what is happening here. For e.g; we have n=89. Firstly we are checking whether the number is 2 or 3, if it is either of those, return 0, i.e; the number is prime. Else we will check whether the number is 1 (because of the definition of prime) or divisible by 2 or 3, any of these conditions satisfying means number is not prime. For our n none of the condition satisfied. So now we start iteration from i=5, we will check our number with i and i+2 and our algorithm automatically checks for other numbers without explicitly checking for them. On the first iteration the “if statement” is checking 5 and 7, and 6, 9, 10 are already checked because they are multiples of 2 or 3, that is why we are incrementing i by 6.
Variable ‘ub’ the upper bound is 9 in this example, so after the first iteration, the value of i will be 11, the program counter will come out of the loop and returns 0, i.e; Prime Number.
Wilson’s Theorem
There is another simple method that uses factorials, Wilson’s Theorem, according to which a natural number, greater than 1, is prime if and only if the product of all positive integers less than n is one less than a multiple of n.
(n-1)! = -1 mod(n)
Number n is prime if (n-1)! +1 is divisible by n
We can implement Wilson’s Theorem with the below code snippet
Well, the logic behind this method is not very complex. If we take a number n and then (n-1)! will have the product of all positive integers less than n, then if number n is not a prime then (n-1)! will also contain the factor of n and if we multiply any positive number with the factor of our positive number, then the result will be divisible by our number.
So if we have n=9, (n-1)! = 8*7*6*5*4*3*2*1, here we can see 3 is a factor of 9, so we can rewrite (n-1)! as 3*(8*7*6*5*4*2) which will be divisible by 9, hence if we add 1 to it, it will not satisfy the condition of code and prints “Not Prime”. So, I’d say —
Clearly, this is not an efficient method, very poor actually. Early explained Trial Division Method is in fact more efficient than Wilson’s Method. We will learn more efficient methods in upcoming posts.
