Fermat's Little Theorem & Primality Testing Code Implementations
Complete Fermat's Little Theorem & Primality Testing code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Fermat's Little Theorem & Primality Testing Guide ยท Launch Interactive Visualizer
C++ Implementation
// Fermat's Little Theorem in C++
class Fermat {
public:
static long long modPow(long long a, long long b, long long mod) {
long long result = 1;
a %= mod;
while (b > 0) {
if (b % 2 == 1)
result = (result * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return result;
}
// Modular inverse using Fermat's Little Theorem (mod must be prime)
static long long modInverseFermat(long long a, long long p) {
return modPow(a, p - 2, p);
}
};JAVA Implementation
// Fermat's Little Theorem in Java
public class Fermat {
public static long modPow(long a, long b, long mod) {
long result = 1;
a %= mod;
while (b > 0) {
if ((b & 1) == 1)
result = (result * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return result;
}
// Modular inverse using Fermat's Little Theorem (mod must be prime)
public static long modInverseFermat(long a, long p) {
return modPow(a, p - 2, p);
}
}JAVASCRIPT Implementation
// Fermat's Little Theorem in JavaScript
// Computes a^b % mod using fast exponentiation
function modPow(a, b, mod) {
let result = 1;
a = a % mod;
while (b > 0) {
if (b % 2 === 1) {
result = (result * a) % mod;
}
a = (a * a) % mod;
b = Math.floor(b / 2);
}
return result;
}
// Computes modular inverse of a modulo p (p must be prime)
function modInverseFermat(a, p) {
return modPow(a, p - 2, p);
}PYTHON Implementation
# Fermat's Little Theorem in Python
# Fast exponentiation
def mod_pow(a, b, mod):
result = 1
a %= mod
while b > 0:
if b % 2 == 1:
result = (result * a) % mod
a = (a * a) % mod
b //= 2
return result
# Modular inverse using Fermat's Little Theorem (mod must be prime)
def mod_inverse_fermat(a, p):
return mod_pow(a, p - 2, p)