modular_inverse_fermat_little_theorem.cpp File Reference

C++ Program to find the modular inverse using Fermat's Little Theorem More...

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for modular_inverse_fermat_little_theorem.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert
namespace	modular_inverse_fermat
	Calculate modular inverse using Fermat's Little Theorem.

Functions
std::int64_t	math::modular_inverse_fermat::binExpo (std::int64_t a, std::int64_t b, std::int64_t m)
	Calculate exponent with modulo using binary exponentiation in \(O(\log b)\) time.
bool	math::modular_inverse_fermat::isPrime (std::int64_t m)
	Check if an integer is a prime number in \(O(\sqrt{m})\) time.
std::int64_t	math::modular_inverse_fermat::modular_inverse (std::int64_t a, std::int64_t m)
	calculates the modular inverse.
static void	test ()
	Self-test implementation.
int	main ()
	Main function.

Detailed Description

C++ Program to find the modular inverse using Fermat's Little Theorem

Fermat's Little Theorem state that

\[ϕ(m) = m-1\]

where \(m\) is a prime number.

\begin{eqnarray*} a \cdot x &≡& 1 \;\text{mod}\; m\\ x &≡& a^{-1} \;\text{mod}\; m \end{eqnarray*}

Using Euler's theorem we can modify the equation.

\[ a^{ϕ(m)} ≡ 1 \;\text{mod}\; m \]

(Where '^' denotes the exponent operator)

Here 'ϕ' is Euler's Totient Function. For modular inverse existence 'a' and 'm' must be relatively primes numbers. To apply Fermat's Little Theorem is necessary that 'm' must be a prime number. Generally in many competitive programming competitions 'm' is either 1000000007 (1e9+7) or 998244353.

We considered m as large prime (1e9+7). \(a^{ϕ(m)} ≡ 1 \;\text{mod}\; m\) (Using Euler's Theorem) \(ϕ(m) = m-1\) using Fermat's Little Theorem. \(a^{m-1} ≡ 1 \;\text{mod}\; m\) Now multiplying both side by \(a^{-1}\).

\begin{eqnarray*} a^{m-1} \cdot a^{-1} &≡& a^{-1} \;\text{mod}\; m\\ a^{m-2} &≡& a^{-1} \;\text{mod}\; m \end{eqnarray*}

We will find the exponent using binary exponentiation such that the algorithm works in \(O(\log n)\) time.

Examples: -

• a = 3 and m = 7
• \(a^{-1} \;\text{mod}\; m\) is equivalent to \(a^{m-2} \;\text{mod}\; m\)
• \(3^5 \;\text{mod}\; 7 = 243 \;\text{mod}\; 7 = 5\)
  Hence, \(3^{-1} \;\text{mod}\; 7 = 5\) or \(3 \times 5 \;\text{mod}\; 7 = 1 \;\text{mod}\; 7\) (as \(a\times a^{-1} = 1\))

Definition in file modular_inverse_fermat_little_theorem.cpp.

Function Documentation

binExpo()

std::int64_t math::modular_inverse_fermat::binExpo	(	std::int64_t	a,
		std::int64_t	b,
		std::int64_t	m )

Calculate exponent with modulo using binary exponentiation in \(O(\log b)\) time.

Parameters

a	The base
b	The exponent
m	The modulo

Returns

The result of \(a^{b} % m\)

Definition at line 67 of file modular_inverse_fermat_little_theorem.cpp.

                                                             {
  a %= m;
  std::int64_t res = 1;
  while (b > 0) {
    if (b % 2 != 0) {
      res = res * a % m;
    }
    a = a * a % m;
    // Dividing b by 2 is similar to right shift by 1 bit
    b >>= 1;
  }
  return res;
}

isPrime()

bool math::modular_inverse_fermat::isPrime

(

std::int64_t

m

)

Check if an integer is a prime number in \(O(\sqrt{m})\) time.

Parameters

m	An intger to check for primality

Returns

true if the number is prime

false if the number is not prime

Definition at line 86 of file modular_inverse_fermat_little_theorem.cpp.

                           {
  if (m <= 1) {
    return false;
  } 
  for (std::int64_t i = 2; i * i <= m; i++) {
    if (m % i == 0) {
      return false;
    }
  }
  return true;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 137 of file modular_inverse_fermat_little_theorem.cpp.

           {
  test();  // run self-test implementation
  return 0;
}

modular_inverse()

std::int64_t math::modular_inverse_fermat::modular_inverse	(	std::int64_t	a,
		std::int64_t	m )

calculates the modular inverse.

Parameters

a	Integer value for the base
m	Integer value for modulo

Returns

The result that is the modular inverse of a modulo m

Definition at line 103 of file modular_inverse_fermat_little_theorem.cpp.

                                                       {
  while (a < 0) {
    a += m;
  }
 
  // Check for invalid cases
  if (!isPrime(m) || a == 0) {
    return -1; // Invalid input
  }
 
  return binExpo(a, m - 2, m);  // Fermat's Little Theorem
}

test()

static void test ( )

static

Self-test implementation.

Returns

void

Definition at line 122 of file modular_inverse_fermat_little_theorem.cpp.

                   {
  assert(math::modular_inverse_fermat::modular_inverse(0, 97) == -1);
  assert(math::modular_inverse_fermat::modular_inverse(15, -2) == -1);
  assert(math::modular_inverse_fermat::modular_inverse(3, 10) == -1);
  assert(math::modular_inverse_fermat::modular_inverse(3, 7) == 5);
  assert(math::modular_inverse_fermat::modular_inverse(1, 101) == 1);
  assert(math::modular_inverse_fermat::modular_inverse(-1337, 285179) == 165519);
  assert(math::modular_inverse_fermat::modular_inverse(123456789, 998244353) == 25170271);
  assert(math::modular_inverse_fermat::modular_inverse(-9876543210, 1000000007) == 784794281);
}