Primality Testing
• Finding an algorithm to correctly and efficiently test a very large
integer and output a prime or a composite has always been a
challenge in number theory and cryptography.
• Primality algorithms can be divided into two broad categories:
• Deterministic algorithms: Always gives a correct answer, but less
efficient than probabilistic algorithm.
Eg:
• Divisibility algorithm;
• AKS (Agarwal, Kayan and Sexena) algorithm
• Probabilistic algorithms: Gives a correct answer most of the time,
but not all the time.
Eg:
• Fermat Test
• Square Root test
• Miller-Rabin Test
Divisibility algorithm:
• Pseudocode
• Divisibility_Test(n)
{
𝑟←2
while( 𝑟 < √𝑛)
{
If 𝑟 𝑛 // 𝑟 𝑛 : r divides n
return “composite”
𝑟 ←𝑟+1
}
return “prime”
}
** Out of those √𝑛 executions, the algorithm can be improved by testing only odd numbers in if ‘n’ is odd.
**The complexity of the algorithm is 𝑂 2𝑛𝑏 where 𝑛𝑏 is the number of bits in ‘n’. When ‘n’ is very large, the divisibility
algorithm is infeasible.
AKS (Agarwal, Kayan and Sexena) algorithm
• To check p is prime:
All the coefficient of (𝑥 − 1)𝑝 −(𝑥 𝑝 −1) must be a multiple of p, where x is
variable.
Eg: p=3
(𝑥 − 1)3 −(𝑥 3 −1) = 𝑥 3 − 3𝑥 2 + 3𝑥 − 1 − 𝑥 3 + 1
= −3𝑥 2 + 3𝑥
Coefficients 3, 3 is a multiple of 3.
Fermat Test:
• From Fermat little theorem: If n is a prime, then 𝑎𝑛−1 ≡ 1 𝑚𝑜𝑑 𝑛.
• Fermat Test can be defined as:
• If n is a prime, 𝑎𝑛−1 ≡ 1 𝑚𝑜𝑑 𝑛.
• If n is a composite, it is possible that 𝑎𝑛−1 ≡ 1 𝑚𝑜𝑑 𝑛.
Fermat test comes under probabilistic algorithm,
• If n is a prime, the congruence holds.
• It does not mean that if the congruence holds, n is a prime
Eg: The number 561.
Using a=2;
2561−1 ≡ 1𝑚𝑜𝑑561.
The congruence holds, but 561 is not prime: 561 = 33 × 17.
So more testing is required by changing the value of a.
Using a=3;
3561−1 ≡ 375 𝑚𝑜𝑑561.
Eg: Miller Test(561)
• 𝑛 − 1 = 2𝑘 m : 561-1= 24 × 35, i.e. m=35, k=4.
• Using a=2, in 𝑏 = 𝑎𝑚 𝑚𝑜𝑑 𝑛
• Initialization: 𝑏 = 235 𝑚𝑜𝑑 561 = 263 𝑚𝑜𝑑 561
• K=1: 𝑏 = 2632 𝑚𝑜𝑑 561 = 166 𝑚𝑜𝑑 561
• K=2: 𝑏 = 1662 𝑚𝑜𝑑 561 = 67 𝑚𝑜𝑑 561
• K=3: 𝑏 = 672 𝑚𝑜𝑑 561 = +1 𝑚𝑜𝑑 561
• Hence 561 is composite.
