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 –
- B > 0
- N is an odd composite number.
- B and N are co-prime i.e. GCD(B, N) = 1
- (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.
Leave a Reply