Check if a number is Euler Pseudoprime in Python
Hello coders, in this tutorial we are going to check whether a given number is Euler Pseudoprime or not in Python. Before we proceed firstly we will discuss what is Euler Pseudoprime number, So let’s start.
What is Euler Pseudoprime?
A number n is said to be Euler Pseudoprime to base b when it follows the condition:
- The base of the number is greater than 0(zero) and the number n should be a composite number
- ( b^((n-1)/2)))%n is equal to n or n-1
- b and n should be coprime numbers.
For example
n=121 and b=3 then the number is Euler Pseudoprime
Now The Python code for implementation of the above concept:-
def isComposite(n) : for i in range(2, int(sqrt(n)) + 1) : if (n % i == 0) : return True; return False; def Power(x, y, p) : res = 1; x = x % p; while (y > 0) : if (y & 1) : res = (res * x) % p; y = y >> 1; # y = y/2 x = (x * x) % p; return res; def isEulerPseudoprime(N, A) : if (A <= 0) : return False; if (N % 2 == 0 or not isComposite(N)) : return False; if (gcd(A, N) != 1) : return false; mod = Power(A, (N - 1) // 2, N); if (mod != 1 and mod != N - 1) : return False; return True; if __name__ == "__main__" : N = 121; A = 3; if (isEulerPseudoprime(N, A)) : print("Yes"); else : print("No");
Output:-
Yes
Also read: Check if a given number is Fibonacci number in Python
Leave a Reply