######################################################################################
# PRIMEFIELD.PY
# A finite field of prime order (integers mod some prime p)
# Author: Robert Campbell, <campbell@math.umbc.edu>
# Date: 26 March, 2005
# Version 0.1
######################################################################################
"""Prime order finite fields.
   Functions implemented are:
   		gcd(a,b) - Compute the greatest common divisor of a and b.
   Usage: from finitefield import *     # names do not need path, e.g. add(x,y)
          GF13 = PrimeField(13)         # Define GF(13), the integers mod 13
          a = PrimeFieldElt(GF13,[2])     # Define [2] in GF(13)
          a**12                         # Compute [2]**12 in GF(13)"""
   
   
Version = 'PRIMEFIELD.PY, version 0.1, 26 March, 2005, by Robert Campbell, campbell@math.umbc.edu'

# Note that this is done in a more complex manner than is needed in order to fit
# neatly in with higher degree finite fields

import numbthy  # Use factors
import types # Use IntType, LongType

class PrimeField:
	def __init__(self, prime):
		self.char = prime
		self.degree = 1
		self.facts_order_gpunits = numbthy.factors(self.char - 1)
	def __str__(self):  # Over-ride string conversion used by print
		return "GF("+str(self.char)+")"
	def __repr__(self):  # Over-ride string conversion used by print
		return "PrimeField("+str(self.char)+")"

class PrimeFieldElt:
	"Prime order finite fields"
	def __init__(self, field, elt=[0]):
		self.field = field
		self.coeffs = elt
	def __str__(self):  # Over-ride string conversion used by print
		return "["+str(self.coeffs[0])+"]"
	def __repr__(self):  # Over-ride string conversion used by print
		return "PrimeFieldElt("+self.field.__repr__()+",["+str(self.coeffs[0])+"])"
	def __int__(self):
		return self.coeffs[0]
	def add(self,summand):
		return PrimeFieldElt(self.field,[(self.coeffs[0]+summand.coeffs[0])%self.field.char])
	def __add__(self,summand):
		if ((type(summand) == types.IntType) or (type(summand) == types.LongType)):
			summand = PrimeFieldElt(self.field,[summand])  # Coerce if adding integer and PrimeFieldElt
		return self.add(summand)
	def __radd__(self,summand):  # Overload the "+" operator
		if ((type(summand) == types.IntType) or (type(summand) == types.LongType)):
			summand = PrimeFieldElt(self.field,[summand])  # Coerce if adding integer and PrimeFieldElt
		return self.add(summand)
	def __iadd__(self,summand): # Overload the "+=" operator
		self = self + summand
		return self
	def __neg__(self):  # Overload the "-" unary operator 
		return PrimeFieldElt(self.field,[-(self.coeffs[0])])
	def __sub__(self,summand):  # Overload the "-" binary operator 
		return self.__add__(-summand)
	def __isub__(self,summand): # Overload the "-=" operator
		self = self - summand
		return self
	def mult(self,multand):
		return PrimeFieldElt(self.field,[(self.coeffs[0]*summand.coeffs[0])%self.field.char])
	def __mul__(self,multip):  # Overload the "*" operator
		if ((type(multip) == types.IntType) or (type(multip) == types.LongType)):
			multip = PrimeFieldElt(self.field,[multip])  # Coerce if multiplying integer and PrimeFieldElt
		return self.mult(multip)
	def __rmul__(self,multip):  # Overload the "*" operator
		if ((type(multip) == types.IntType) or (type(multip) == types.LongType)):
			multip = PrimeFieldElt(self.field,[multip])  # Coerce if multiplying integer and PrimeFieldElt
		return self.mult(multip)
	def __imul__(self,multip): # Overload the "*=" operator
		self = self * multip
		return self
	def inv(self):
		return PrimeFieldElt(self.field,[numbthy.xgcd(self.coeffs[0],self.field.char)[1] % self.field.char])
	def div(self,divisor):
		return self * inv(divisor)
	def __div__(self,divisor):
		if ((type(divisor) == types.IntType) or (type(divisor) == types.LongType)):
			divisor = PrimeFieldElt(self.field,[divisor])  # Coerce if dividing integer and PrimeFieldElt
		return self / divisor
	def __rdiv__(self,dividend):
		if ((type(dividend) == types.IntType) or (type(dividend) == types.LongType)):
			dividend = PrimeFieldElt(self.field,[dividend])  # Coerce if dividing integer and PrimeFieldElt
		return dividend / self
	def __pow__(self,exponent):
		if (exponent < 0):
			self = self.inv()
			exponent = -exponent
		return PrimeFieldElt(self.field, [pow(self.coeffs[0],exponent,self.field.char)])