C++ Program To Implement Fermats Little Theorem

In this guide, you'll discover how to apply Fermat's Little Theorem in C++. Prior to delving into its implementation, it's essential to grasp the concept of Fermat's Little Theorem.

What is the Fermat's Little Theorem?

The principle known as Fermat's Little Theorem, attributed to the French mathematician Pierre de Fermat, who introduced it during the 17th century, plays a vital role in the field of number theory. This theorem establishes a significant connection between prime numbers and modular arithmetic.

In accordance with Fermat's Little Theorem, when p is a prime number, the expression "a^p - a" is a multiple of p for any integer value of a.

Special Case

Fermat's Little Theorem can be employed to demonstrate that when "a" is not divisible by "p", then "a^(p-1) - 1" is a whole number multiple of "p".

In this case, p cannot divide a.

Some key points about Fermat's Little Theorem

There are several key points about the Fermat's Little Theorem. Some main key points of the Fermat's Little Theorem are as follows:

• ✅ Prime Numbers: Fermat's Little Theorem focuses only on prime numbers. It provides a method for determining if a given number is prime. However, it is probabilistic and not always definitive.
• ✅ Cryptography: The theory's applications in cryptography include the RSA encryption algorithm. Since it offers an effective method of determining the modular inverse, it serves as a basis for generating public and private keys.
• ✅ Testing for Probabilistic Primality: Fermat's Little Theorem offers a probabilistic primality test, but it is insufficient to establish primality independently, particularly when dealing with big numbers. For more accurate primality testing, other tests, such as the Miller-Rabin test , can be used along with Fermat's Little Theorem.
• ✅ Modular Arithmetic: Fermat's Little Theorem is a key concept in modular arithmetic. It provides an effective way to find modular inverses. "a^p-2" is the modular inverse of an integer a modulo p for any integer a that is not divisible by a prime number p. Cryptographic algorithms like RSA make considerable use of this characteristic for both encryption and decryption.

Example:

Let's consider an example to demonstrate Fermat's Little Theorem using C++.

#include <iostream>
using namespace std;
//Function for power modulo calculation
int power_Modulo(int base, int expo_nent, int modulo)
{
    int ans = 1;
    base = base % modulo; 
    // Update base if it is >= mod
    while (expo_nent > 0) 
    {
        //If the expo_nent is odd, multiply the result by the base.
        if (expo_nent % 2 == 1)
            ans = (ans * base) % modulo;
        // expo_nent must be even now
        expo_nent = expo_nent >> 1;
        // expo_nent = expo_nent / 2
        base = (base * base) % modulo;
    }
    return ans;
}
// This Function finds an integer's multiplicative inverse modulo a prime number.
int finding_Multiplicative_Inverse(int n, int pri_me)
{
    // Only when 'n' and 'pri_me' are coprime does the multiplicative inverse exist.
    // Using Fermat's Little Theorem: if 'prime' is prime, then (num^(prime-2)) % prime is the multiplicative inverse of 'num.'
    return power_Modulo(n, pri_me - 2, pri_me);
}
// Main Function
int main() 
{
    int n, pri_me;
    // Input the number and the prime modulo
    cout << "Enter the to find modular multiplicative inverse: ";
    cin >> n;
    cout << "Enter the prime modulo value: ";
    cin >> pri_me;
    // Find the multiplicative inverse
    int in_verse = finding_Multiplicative_Inverse(n, pri_me);
    if (in_verse != 1)
        cout << "The multiplicative inverse of " << n << " modulo " << pri_me << " is: " << in_verse << endl;
    else
        cout << "The multiplicative inverse of " << n << " modulo " << pri_me << " does not exist." << endl;
    return 0;
}

Output:

Enter the to find modular multiplicative inverse: 5
Enter the prime modulo value: 7
The multiplicative inverse of 5 modulo 7 is: 3

Explanation:

• ✅ This C++ program applies Fermat's Little Theorem to determine a number's modular multiplicative inverse modulo a prime. The powerModulo function uses binary exponentiation to compute (base^exponent) mod modulo efficiently.
• ✅ The findingMultiplicativeInverse Function employs Fermat's Little Theorem to determine a number's multiplicative inverse modulo a prime.
• ✅ The user provides the prime modulo value and the number to determine the multiplicative inverse for the main Function. After that, the findingMultiplicativeInverse Function is used by the program to compute the multiplicative inverse, and the result is printed.

Conclusion:

Fermat's Little Theorem serves as a potent and adaptable resource with various practical uses in the fields of mathematics and computer science, including number theory, cryptography, and primality testing. Its elegance and straightforwardness make it an essential element in contemporary computational mathematics.