sympy/ntheory/residue.py

   1 from sympy.core.numbers import gcd
   2 from primetest import isprime
   3
   4 def totient_(n):
   5     """returns the number of integers less than n
   6     and relatively prime to n"""
   7     if n < 1:
   8         raise ValueError, "n must be a positive integer"
   9     tot=0
  10     for x in xrange(1,n):
  11         if gcd(x,n)==1:
  12             tot+=1
  13     return tot
  14
  15 def n_order(a,n):
  16     """ returns the order of a modulo n
  17     Order of a modulo n is the smallest integer
  18     k such that a^k leaves a remainder of 1 with n.
  19     """
  20     assert gcd(a,n)==1
  21     if a>n : a=a%n
  22     for x in xrange(1,totient_(n)+1):
  23         if (a**x)%n==1:
  24             return x
  25
  26 def is_primitive_root(a,p):
  27     """
  28     returns True if a is a primitive root of p
  29     """
  30     assert gcd(a,p) == 1,"The two numbers should be relatively prime"
  31     if a>p:
  32         a=a%p
  33     if n_order(a,p)==totient_(p):
  34         return True
  35     else:
  36         return False
  37
  38 def is_quad_residue(a,p):
  39     """
  40     returns True if a is a quadratic residue of p
  41     p should be a prime and a should be relatively
  42     prime to p
  43     """
  44     assert isprime(p) and p!=2,"p should be an odd prime"
  45     assert gcd(a,p)==1,"The two numbers should be relatively prime"
  46     if a>p:
  47         a=a%p
  48     rem=(a**((p-1)/2))%p    # a^(p-1 / 2) % p
  49     if rem==1: return True
  50     else : return False
  51
  52 def legendre_symbol(a,p):
  53     """
  54     return 1 if a is a quadratic residue of p
  55     else return -1
  56     p should be an odd prime by definition
  57     """
  58     assert isprime(p) and p!=2,"p should be an odd prime"
  59     assert gcd(a,p)==1,"The two numbers should be relatively prime"
  60     if a>p:
  61         a=a%p
  62     if is_quad_residue(a,p)==True: return 1
  63     else : return -1
  64
  65
  66
  67
  68
  69
  70
  71
  72