AntInLoop

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)