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:

1.  The base of the number is greater than 0(zero) and  the number n should be a composite number
2. ( b^((n-1)/2)))%n is equal to n or n-1
3. 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