C++ Program to Perform Fermat Primality Test

Fermat's Little theorem states that if 'p' is a prime number and 'a' is an integer that is not divisible by p, then a^(p-1) ? 1 modulo p or a^(p-1) mod p = 1. We will use Fermat's Little theorem to test whether the given number is a prime number or not.

In this article, we have a number num and a given number of iterations itr. Our task is to implement a primality test for the given number using Fermat's theorem in C++.

Steps to Perform Fermat Primality Test

The steps to perform Fermat's Primality test are as follows:

• We have used the modExp() function to compute the value of (base^exp) % mod. To compute this, we use bits value where we compute the result and base value if the bit value of exp is 1 or odd and compute only base if the bit value is even or 0. We use the modulo operation to keep the value in the range of exponent.
• The isPrime() function uses Fermat's Primality Test to check if a number n is prime or not. It accepts two arguments: an integer 'n' and a number of iterations 'k'.
• We have used two if statements, where the first statement marks 1 and 4 as non-prime and the second if statement marks 2 and 3 as prime numbers.
• Then, we used a for loop such that in each iteration we chose a random integer in the range [2, n - 2].
• Random selected 'a' is checked if it satisfies Fermat's Little theorem or not using the modExp() function.
• For the given 'a', if the value of modExp() is not equal to 1, then it is not a prime number and returns false.
• If all the 'a' satisfies Fermat's Little theorem, then the number is prime, and the function returns true.

C++ Program to Perform Fermat Primality Test

Here is the C++ implementation to test if the given number is prime or not using Fermat's Little theorem:

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; long long modExp(long long base, long long exp, long long mod) { long long result = 1; base %= mod; while (exp > 0) { if (exp & 1) result = (result * base) % mod; exp >>= 1; base = (base * base) % mod; } return result; } // Fermat Primality Test bool isPrime(int n, int k) { if (n <= 1 || n == 4) return false; if (n <= 3) return true; for (int i = 0; i < k; i++) { int a = 2 + rand() % (n - 4); if (modExp(a, n - 1, n) != 1) return false; } return true; } int main() { srand(time(0)); int num = 61; // Number to test int itr = 5; // Number of iterations for the test if (isPrime(num, itr)) cout << num << " is prime number." << endl; else cout << num << " is not a number." << endl; return 0; } 

The output of the above code is:

61 is prime number.