Check if a number is Euler Pseudoprime in Java

In this article, we are going to see and understand how to check if a number is Euler Pseudoprime or not in Java.

Definition:-  An integer ‘N’ is called Euler Pseudoprime to the base B if they satisfy the following conditions –

1.  B > 0
2. N is an odd composite number.
3. B and N are co-prime i.e. GCD(B, N) = 1
4. (B^{(N – 1) / 2} ) % N is either 1 or N – 1.

Example:-

1. N = 341 , B = 4

Here, as B>0 and N is an odd composite number, B and N are co-prime and (4^{(341 – 1) / 2} ) % 341 = 1

Therefore it is an Euler Pseudoprime number.

2. N =341, B = 3

Here, as B>0 and N is an odd composite number, B and N are co-prime but (3^{(341 – 1) / 2} ) % 341 = 67

Therefore it is not an Euler Pseudoprime number.

The code below will check if a number is Euler Pseudoprime in Java.

class Euler
{

    // Function to Check if two numbers are coprime or not
    public boolean check_coprime(int b,int n)
    {
        // get gcd result of b and n
        int result = gcd(b,n);

        // if result is not 1 then it is not coprime
        if(result != 1)
            return false;
        return true;
    }

    // Function to Check gcd of the numbers
    public int gcd(int x, int y) 
    {
        if(x==0)
          return y;
        if (y==0)
          return x;
        if (x==y) 
            return x; 
        if (x>y) 
            return gcd(x-y,y); 
        return gcd(x,y-x); 
    }

    // Function to Check if the given number n is an odd composite number or not
    public boolean check_ifOddcomposite(int n) 
    {
        for(int k=2;k<= n/2;k++)
        {
            // if it is divisible by any number less then n/2 
            // and if it is odd number then it is odd composite number
            if (n%k == 0 && n%2 == 1)
                return true;
        }
        return false;
    }

    // Function to calculate result of (A ^ P) % N 
    public int calc_Result(int A, int P, int N)
    {
        int result = 1;
        // Update value of 'A' if it is greater than or equal to 'N'
        A = A%N;
        while(P>0) 
        {
            // If 'P' is odd, multiply 'A' with result
            if(P % 2 == 1)
            {
                result = (result*A) % N; 
            }
            P = P/2;
            A = (A * A) % N; 
        }
        return result; 
    }

    // Function to check if the Number is a Euler Pseudoprime number or not
    public void check_EulerPseudoprimeNo(int N, int B)
    {
        // Checking all the conditions
        // Check if base is valid 
        if(B >= 0){
            // Check if N is a odd composite number 
            if(check_ifOddcomposite(N)){
                // Check if B and N are coprime 
                if(check_coprime(B,N)){
                    // Calculate result of (B ^ (N – 1)/2 ) % N and store in 'res' variable
                    int res = calc_Result(B, (N-1)/2 , N);

                    // Check if the result is either 1 or N-1 
                    if (res == 1 || res == N - 1){
                        // All the conditions for Euler Pseudoprime are satisfied
                        System.out.println("It is a Euler Pseudoprime Number");
                        return;
                    }
                }
            }
        }
        // If any condition fails
        System.out.println("Not a Euler Pseudoprime Number");
    }
}

class Main{

    public static void main(String args[]) 
    {
        int N,B;
        N=121;
        B=3;

        // Creating object of Euler class
        Euler obj=new Euler();

        // Calling funtion check_EulerPseudoprimeNo
        obj.check_EulerPseudoprimeNo(N,B);
    
    } 
}

In the above code, first, we are defining important functions like check_coprime(), gcd(), and check_ifOddcomposite() to check for our first two conditions of Euler Psuedoprime. Then, to check for the third condition, we define calc_result and then to check if all conditions satisfy and whether it is an Euler Psuedoprime or not, we define check_EulerPseudoprimeNo().

As a result, the following output is generated:-

C:\Users\KIRA\Desktop\case study>javac Main.java

C:\Users\KIRA\Desktop\case study>java Main
It is a Euler Pseudoprime Number

I hope you like the article, feel free to comment down your queries.