"""
Finite fields in Python.

"""

#def FF(p):
#    return FF_prime(p)

class FF:
    """
    Implements "prime" finite fields.

    EXAMPLES:
        sage: F = FF(5)
        sage: print F
        Finite field with 5 elements
        sage: F
        FF(5)

    """
    def __init__(self, p):
        self.characteristic = p

    def __repr__(self):
        """
        Called to compute the "official" string representation of an object. 
        If at all possible, this should look like a valid Python expression 
        that could be used to recreate an object with the same value.

        EXAMPLES:
            sage: F = FF(5)
            sage: F
            FF(5)

        """
        return "FF(%s)"%self.characteristic

    def __str__(self):
        """
        Called to compute the "informal" string description of an object. 

        EXAMPLES:
            sage: F = FF(5)
            sage: print F
            Finite field with 5 elements

        """
        return "Finite field with %s elements"%self.characteristic
 
    def __lt__(self, other):
        """
        Returns True of self < other, False otherwise.
        """
        return False

    def __gt__(self, other):
        """
        Returns True of self > other, False otherwise.
        """
        return False

    def char(self):
        return self.characteristic

    def __eq__(self, other):
        """
        Returns True of self = other and False otherwise.

        EXAMPLES:
            sage: F1 = FF(5)
            sage: F2 = FF(7)
            sage: F1 == F2
            False
            sage: F2 = FF(5)
            sage: F1 == F2
            True
        """
        p = self.char()
        q = other.char()
        return p == q

    def __call__(self, a):
        """
        Reduces a mod p.

        EXAMPLES:
            sage: F1(12)
            2
        """
        p = self.characteristic
        return FFElement(p, a)

    def __contains__(self, a):
        """

        EXAMPLES:
            sage: F = FF(5)
            sage: 2 in F
            True
            sage: 6 in F
            False

        """
        p = self.characteristic
        if a>=0 and a<p:
            return True
        else:
            return False

class FFElement:
    def __init__(self, p, a):
        self.characteristic = p
        self.element = a%p
        self.base_field = FF(p)

    def __repr__(self):
        """
        Called to compute the "official" string representation of an object. 
        If at all possible, this should look like a valid Python expression 
        that could be used to recreate an object with the same value.

        EXAMPLES:

        """
        return "FFElement(%s, %s)"%(self.characteristic, self.element)

    def __str__(self):
        """
        Called to compute the "informal" string description of an object. 

        EXAMPLES:

        """
        return "Finite field element %s in %s"%(self.element, self.base_field)
 
    def __add__(self, other):
        """
        Implements +. Assumes both self and other are instances of 
        FFElement class.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a+b
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            2
        """
        p = self.characteristic
        return (self.element+other.element)%p

    def __sub__(self, other):
        """
        Implements -.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a-b
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            6
        """
        p = self.characteristic
        return (self.element-other.element)%p

    def __mul__(self, other):
        """
        Implements multiplication *.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a*b
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            6
        """
        p = self.characteristic
        return (self.element*other.element)%p

    def __div__(self, other):
        """
        Implements /.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a/b
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            5
        """
        p = self.characteristic
        a = self.element
        b = other.element
        return (a*b.__pow__(-1))%p

    def __pow__(self, n):
        """
        Implements ^ or **.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a**(-1); b^2
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            2
            4
        """
        p = self.characteristic
        a = self.element
        n = int(n)
        #print "computing %s ^ %s mod %s"%(a,n,p)
        if a%p == 0 and not(n<0):
            return 0
        if p == 2 and n == -1:
            return a%p
        if n == 0:
            return 1
        if n == 1:
            return a%p
        if n>1:
            if n%2 == 0:
                return ((a.__pow__(int(n/2)))**2)%p
            if n%2 == 1:
                return (a*(a.__pow__(int(n/2)))**2)%p
        if n == -1:
            return (a.__pow__(p-2))%p
        if n<-1:
            return ((a.__pow__(-1))**(-n))%p
        return 0 # should never happen

    def inverse(self):
        """
        Implements the inverse.

        EXAMPLES:
            sage: F = FF(7)
            sage: a = F(102); b = F(-2)
            sage: a; b; print a; print b; a.inverse(); b.inverse()
            FFElement(7, 4)
            FFElement(7, 5)
            Finite field element 4 in Finite field with 7 elements
            Finite field element 5 in Finite field with 7 elements
            2
            3
        """
        p = self.characteristic
        a = self.element
        if a%p == 0:
            raise ValueError, "Element must be non-zero."
        if p == 2:
            return a%p
        return (a.__pow__(p-2))%p