Check if a number is Fermat Pseudoprime

0 0 5 minutes read

Given a number N and a base number A. The task is to check whether the number is a Fermat Pseudoprime to the base.
The number N is called as Fermat Pseudoprime to the base A, if

1. A > 1
2. N is a composite number
3. N divides A^N-1 – 1.

Examples:

Input : N = 645, a = 2
Output :1
645 = 3*5*43, Hence it is a composite number
Also 645 divides 2^(644)-1
Hence it is a Fermat Pseudoprime.
Input : N = 6, a = 2
Output :0

Approach: The approach is to check the below conditions:

Check if A > 1.
Check if N is a composite number.
Check if N divides A^N-1 – 1.

If all of the above conditions satisfy then N is a fermat pseudoprime to base A.
Below is the implementation of the above approach:

C++

// C++ program to check if N is Fermat pseudoprime
// to the base A or not
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the given number is composite
bool checkcomposite(int n)
{
    // Check if there is any divisor of n less than sqrt(n)
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return 1;
    }
    return 0;
}
 
// Effectively calculate (x^y) modulo mod
int power(int x, int y, int mod)
{
 
    // Initialize result
    int res = 1;
 
    while (y) {
 
        // If power is odd, then update the answer
        if (y & 1)
            res = (res * x) % mod;
 
        // Square the number and reduce
        // the power to its half
        y = y >> 1;
        x = (x * x) % mod;
    }
 
    // Return the result
    return res;
}
 
// Function to check for Fermat Pseudoprime
bool Check(int n, int a)
{
 
    // If it is composite and satisfy Fermat criterion
    if (a>1 && checkcomposite(n) && power(a, n - 1, n) == 1)
        return 1;
 
    // Else return 0
    return 0;
}
 
// Driver code
int main()
{
 
    int N = 645;
    int a = 2;
     
   //  Function call
    cout << Check(N, a);
 
    return 0;
}

Java

// Java program to check if N is Fermat pseudoprime 
// to the base A or not 
class GFG 
{
 
    // Function to check if 
    // the given number is composite 
    static boolean checkcomposite(int n) 
    {
        // Check if there is any divisor of n 
        // less than sqrt(n) 
        for (int i = 2; i <= Math.sqrt(n); i++) 
        {
            if (n % i == 0) 
            {
                return true;
            }
        }
        return false;
    }
 
    // Effectively calculate (x^y) modulo mod 
    static int power(int x, int y, int mod)
    {
 
        // Initialize result 
        int res = 1;
 
        while (y != 0) 
        {
 
            // If power is odd,
            // then update the answer 
            if ((y & 1) == 1) 
            {
                res = (res * x) % mod;
            }
 
            // Square the number and reduce 
            // the power to its half 
            y = y >> 1;
            x = (x * x) % mod;
        }
 
        // Return the result 
        return res;
    }
 
    // Function to check for Fermat Pseudoprime 
    static int Check(int n, int a) 
    {
 
        // If it is composite and 
        // satisfy Fermat criterion 
        if (a > 1 && checkcomposite(n)
                && power(a, n - 1, n) == 1) 
        {
            return 1;
        }
 
        // Else return 0 
        return 0;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 645;
        int a = 2;
 
        // Function call 
        System.out.println(Check(N, a));
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to check if N is Fermat pseudoprime
# to the base A or not
 
from math import sqrt
 
# Function to check if the given number is composite
def checkcomposite(n):
     
    # Check if there is any divisor of n less than sqrt(n)
    for i in range(2,int(sqrt(n))+1,1):
        if (n % i == 0):
            return 1
    return 0
 
# Effectively calculate (x^y) modulo mod
def power(x, y, mod):
    # Initialize result
    res = 1
 
    while (y):
        # If power is odd, then update the answer
        if (y & 1):
            res = (res * x) % mod
 
        # Square the number and reduce
        # the power to its half
        y = y >> 1
        x = (x * x) % mod
 
    # Return the result
    return res
 
# Function to check for Fermat Pseudoprime
def Check(n,a):
    # If it is composite and satisfy Fermat criterion
    if (a>1 and checkcomposite(n) and power(a, n - 1, n) == 1):
        return 1
 
    # Else return 0
    return 0
 
# Driver code
if __name__ == '__main__':
    N = 645
    a = 2
 
    # Function call
    print(Check(N, a))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to check if N is Fermat pseudoprime 
// to the base A or not 
using System;
 
class GFG
{
     
    // Function to check if 
    // the given number is composite 
    static bool checkcomposite(int n) 
    { 
        // Check if there is any divisor of n 
        // less than sqrt(n) 
        for (int i = 2; i <= Math.Sqrt(n); i++) 
        { 
            if (n % i == 0) 
                return true; 
        } 
        return false; 
    } 
     
    // Effectively calculate (x^y) modulo mod 
    static int power(int x, int y, int mod) 
    { 
     
        // Initialize result 
        int res = 1; 
     
        while (y != 0) 
        { 
     
            // If power is odd, then update the answer 
            if ((y & 1) == 1) 
                res = (res * x) % mod; 
     
            // Square the number and reduce 
            // the power to its half 
            y = y >> 1; 
            x = (x * x) % mod; 
        } 
     
        // Return the result 
        return res; 
    } 
     
    // Function to check for Fermat Pseudoprime 
    static int Check(int n, int a) 
    { 
     
        // If it is composite and satisfy Fermat criterion 
        if (a > 1 && checkcomposite(n) && 
                     power(a, n - 1, n) == 1) 
            return 1; 
     
        // Else return 0 
        return 0; 
    } 
     
    // Driver code 
    static public void Main ()
    {
        int N = 645; 
        int a = 2; 
     
        // Function call 
        Console.WriteLine(Check(N, a)); 
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript program to check if
// N is Fermat pseudoprime
// to the base A or not
 
// Function to check if the given
// number is composite
function checkcomposite(n)
{
    // Check if there is any divisor 
    // of n less than sqrt(n)
    for (let i = 2; i <= Math.sqrt(n); i++) 
    {
        if (n % i == 0)
            return 1;
    }
    return 0;
}
 
// Effectively calculate (x^y) modulo mod
function power(x, y, mod)
{
 
    // Initialize result
    let res = 1;
 
    while (y) {
 
        // If power is odd, then update the answer
        if (y & 1)
            res = (res * x) % mod;
 
        // Square the number and reduce
        // the power to its half
        y = y >> 1;
        x = (x * x) % mod;
    }
 
    // Return the result
    return res;
}
 
// Function to check for Fermat Pseudoprime
function Check(n, a)
{
 
    // If it is composite and satisfy
    // Fermat criterion
    if (a>1 && checkcomposite(n) && 
    power(a, n - 1, n) == 1)
        return 1;
 
    // Else return 0
    return 0;
}
 
// Driver code
 
    let N = 645;
    let a = 2;
     
       //  Function call
    document.write(Check(N, a));
 
</script>

Output:

Time Complexity : O(sqrt(N))

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!