def _is_nthpow_residue_bign_prime_power(a, n, p, k):
 if (a % p):
  if (p != 2):
   return _is_nthpow_residue_bign(a, n, pow(p, k))
  if (n & 1):
   return True
  c = trailing(n)
  return ((a % pow(2, min((c + 2), k))) == 1)
 else:
  a %= pow(p, k)
  if (not a):
   return True
  mu = multiplicity(p, a)
  if (mu % n):
   return False
  pm = pow(p, mu)
  return _is_nthpow_residue_bign_prime_power((a // pm), n, p, (k - mu))

def _is_nthpow_residue_bign_prime_power ( a , n , p , k ) : if ( a % p ) : if ( p != 2 ) : return _is_nthpow_residue_bign ( a , n , pow ( p , k ) ) if ( n & 1 ) : return True c = trailing ( n ) return ( ( a % pow ( 2 , min ( ( c + 2 ) , k ) ) ) == 1 ) else : a %= pow ( p , k ) if ( not a ) : return True mu = multiplicity ( p , a ) if ( mu % n ) : return False pm = pow ( p , mu ) return _is_nthpow_residue_bign_prime_power ( ( a // pm ) , n , p , ( k - mu ) )
returns true/false if a solution for x**n == a (mod) does/doesnt exist .