Check if a number is Fermat Pseudoprime in Java

Here you will learn to check if a number is Fermat Pseudoprime in Java programming. This tutorial will include some easy and understandable instructions.

In this problem, we will be having a number and a base number let us say N is the number and M is the base number. The work for us to check if the number is the Fermat Pseudoprime to the base number or not.

There are certain rules for the Fermat Pseudoprime validity,

  • N is a composite number
  • M should be greater than 1
  • N should divides (M^N-1)-1

If all the above rules satisfy then we can say that the number is Fermat Pseudoprime.

Implementation:

Firstly we will check whether the number is composite or not, we will declare a method isComposite(),

static boolean iscomposite(int n)  
{  
  int i;
  double sqrt=Math.sqrt(n);
        for (i=2;i<=sqrt;i++)  
        { 
            if (n%i==0)  
            { 
                return true; 
            } 
        } 
        return false; 
}

Next, we will be calculating the exponential values and find the mod value for rule number #3,

static int exponent(int a,int b,int mod) 
{ 
        int result=1; 
        while(b!=0)  
        { 
            if((b&1)==1)  
            { 
                result=(result*a)%mod; 
            } 
            b=b>>1; 
            a=(a*a)%mod; 
        } 
        return result; 
}

Now in the last part, we will have to put the values and check whether it satisfies or not, accordingly we will return true and false.

static int  validate(int n,int k)  
{ 
        if (k > 1 && iscomposite(n) 
                && exponent(k,n-1,n)==1)  
        { 
            return 1; 
        } 
        return 0; 
}

The main function in the program will consist of the input as variables and calling the working function,

public static void main(String[] args) 
{ 
        int N = 1290; 
        int M = 2; 
        System.out.println(validate(N, M)); 
}

Output:

0

We can try different inputs that will generate results that satisfy the rules, such as;

public static void main(String[] args) 
{ 
        int N = 645; 
        int M = 2; 
        System.out.println(validate(N, M)); 
}

Output:

1

Note: Please keep the whole code in a class

Leave a Reply

Your email address will not be published. Required fields are marked *