Fermat's Little Theorem

Modular Multiplicative Inverse Using Fermat's Little Theorem

Definition:

The modular multiplicative inverse of an integer a modulo m is an integer b such that a * b ≡ 1 (mod m). In other words, b is the inverse of a in the ring of integers modulo m.

Fermat's Little Theorem for Modular Inverses:

Fermat's Little Theorem provides a direct way to calculate the modular multiplicative inverse of a modulo p when p is a prime number. It states that: $a^{(p-2)} ≡ a^{(-1)}$ This means that raising a to the power of p-2 modulo p gives you the modular multiplicative inverse of a.

Code

Code Implementation (Python):

def modular_exponentiation(base, exponent, mod):
    """Calculates the modular exponentiation of base^exponent mod mod efficiently.

    Args:
        base: The base number.
        exponent: The exponent.
        mod: The modulus.

    Returns:
        The result of base^exponent mod mod.
    """

    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent //= 2
    return result

def modular_inverse(a,   
 p):
    """Calculates the modular multiplicative inverse of a modulo p using Fermat's Little Theorem.in O(logn)

    Args:
        a: The base number.
        p: The prime modulus.

    Returns:
        The modular multiplicative inverse of a modulo p, or None if it doesn't exist.
    """

    if p <= 1:
        raise ValueError("Modulus must be a prime number greater than 1.")
    return modular_exponentiation(a, p - 2, p)
    

Code Implementation (C++):

 
include "bits/stdc++.h>

using namespace std;

int modular_exponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

int modular_inverse(int a, int p) {
    if (p <= 1) {
        throw invalid_argument("Modulus must be a prime number greater than 1.");
    }
    return modular_exponentiation(a, p - 2, p);
}

int main() {
    int a = 3;
    int p = 7;

    int inverse = modular_inverse(a, p);
    cout << "The modular multiplicative inverse of " << a << " modulo " << p << " is " << inverse << endl;

    return 0;
}

Code Implementation (Java):

import java.util.Scanner;

public class FermatsLittleTheorem {
    public static int modular_exponentiation(int base, int exponent, int mod) {
        int result = 1;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent /= 2;
        }
        return result;   

    }

    public static int modular_inverse(int a, int p) {
        if (p <= 1) {
            throw new IllegalArgumentException("Modulus must be a prime number greater than 1.");
        }
        return modular_exponentiation(a, p - 2, p);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the value of a: ");
        int a = scanner.nextInt();

        System.out.print("Enter   
 the prime modulus p: ");
        int p = scanner.nextInt();

        int inverse = modular_inverse(a, p);
        System.out.println("The modular multiplicative inverse of " + a + " modulo " + p + " is " + inverse);
    }
}

Time Complexity

• Best Case: O(log p)
• Average Case: O(log p)
• Worst Case: O(log p) where p is the exponent (in this case, the prime modulus).

Space Complexity

• O(1) as the iterative algorithm for modular exponentiation uses only a few variables.

Explanation

Fermat's Little Theorem computes the modular inverse by evaluating a^(p-2) mod p. Using the repeated squaring algorithm (binary exponentiation), the power is halved at each step. This means the algorithm loops O(log p) times, making it extremely efficient for large primes. The space complexity is constant O(1) as variables are updated iteratively without requiring any recursive call stacks or external memory arrays.

Explanation of the Code:

modular_exponentiation: This function efficiently calculates the modular exponentiation of base^exponent mod mod using the repeated squaring algorithm. modular_inverse: This function calculates the modular multiplicative inverse of a modulo p using Fermat's Little Theorem. It first checks if p is a prime number greater than 1. If so, it calculates $a^{(p-2)}$ mod p using the modular_exponentiation function. The result is the modular multiplicative inverse of a modulo p. main: This is the main function where the program execution starts. It prompts the user to enter values for a and p, calculates the modular inverse using the modular_inverse function, and prints the result. Example Usage:

Run the Java program and enter the values of a and p. For example, if you enter a = 3 and p = 7, the output will be:

The modular multiplicative inverse of 3 modulo 7 is 5

Sources and related content

Applications in Competitive Programming

Fermat's Little Theorem has several practical applications in competitive programming:

1. Modular Exponentiation Efficiently calculating large powers modulo a prime: Fermat's Little Theorem can be used to reduce the exponent modulo a prime before performing the exponentiation. This can significantly improve the efficiency of calculations involving large exponents.
2. Finding Modular Inverses Calculating modular inverses efficiently: For prime moduli, Fermat's Little Theorem provides a direct method to find the modular inverse of an element. This is crucial for solving problems involving modular division or solving linear congruences.
3. Solving Diophantine Equations Solving linear congruences: Fermat's Little Theorem can be used to solve linear congruences of the form ax ≡ b (mod p) where p is a prime number.
4. Cryptography RSA Algorithm: Fermat's Little Theorem forms the basis of the RSA public-key encryption algorithm. It is used to generate the public and private keys, as well as to perform encryption and decryption.