Group Theory

class Group:
    """
        This class generate a group self._g based on the operation (here denoted +)
        with the function ope: (a ** b) % n

        Attributes:
            n (Integer): It's the G_n elements in the Group
            g (List): The set of the Group
            operation (Function): Function for generating the Group
            identity (Integer): The identity of the group
            reverse (Dict): For each elements of the Group of n, we have the reverse value
    """
    def __init__(self, n, g, ope):
        self._n = n
        self._g = g
        # self._operation = self.ope
        self._operation = ope
        self._identity = 0
        self._reverse = dict()

    def getG(self) -> list():
        """
            This function return the Group

            Returns:
                List of all elements in the Group
        """
        return self._g

    def closure(self) -> bool:
        """
            Check the closure law
            In a group, each element a, b belongs to G, such as a + b belongs to G

            Returns:
                Return a Boolean if the closure law is respected. True if yes otherwise it's False
        """
        for e1 in self._g:
            for e2 in self._g:
                res = self._operation(e1, e2, self._n)
                if  not res in self._g:
                    # raise Exception(f"{res} not in g. g is not a group")
                    return False
        return True 

    def associative(self) -> bool:
        """
            Check the associative law. 
            In a group, for any a, b and c belongs to G,
            they must respect this condition: (a + b) + c = a + (a + b)

            Returns:
                Return a boolean if the Associative law is respected. True if yes otherwise it's False
        """
        a = self._g[0]
        b = self._g[1]
        c = self._g[2]

        res_ope = self._operation(a, b, self._n)
        res1 = self._operation(res_ope, c, self._n)

        res_ope = self._operation(b, c, self._n)
        res2 = self._operation(a, res_ope, self._n)
        if res1 != res2:
            # raise Exception(f"{res1} is different from {res2}. g is not a group")
            return False
        return True

    def identity(self) -> bool:
        """
            Check the identity law.
            In a group, an identity element exist and must be uniq

            Returns:
                Return a Boolean if the identity elements has been found. True if found otherwise it's False
        """
        for a in self._g:
            for b in self._g:
                if not self._operation(a, b, self._n) == b:
                    break

                self._identity = a
                return True
        return False

    def getIdentity(self) -> int:
        """
            Return the identity element. The function identitu() must be called before.

            Returns:
                Return the identity element if it has been found
        """
        return self._identity

    def reverse(self) -> bool:
        """
            Check the inverse law
            In a group, for each element belongs to G
            they must have an inverse a ^ (-1) = e (identity)

            Returns:
                Return a Boolean if the all elements ha a reverse element. True if yes otherwise it's False
        """
        reverse = False
        for a in self._g:
            for b in self._g:
                if self._operation(a, b, self._n) == self._identity:
                    self._reverse[a] = b
                    reverse = True
                    break
        return reverse        

    def getReverses(self) -> dict:
        """
            This function return the dictionary of all reverses elements. The key is the element in G and the value is the reverse element

            Returns:
                Return the reverse dictionary

        """
        return self._reverse

class Cyclic(Group):
    """
        This object contain a list of the Group for a cyclic group. This class find all generator of the group.
        This class is inherited from Group object

        Attributes:
            G (list): list of all elements in the group
            n (Integer): it's the value where the group has been generated
            operation (Function): it's the operation generating the group
            generators (list): contain all generators of the group 
            generatorChecked (boolean): Check if generators has been found
    """
    def __init__(self, G:list, n, ope):
        super().__init__(n, G, ope) # Call the Group's constructor
        self._G = G
        self._n = n
        self._operation = ope
        self._generators = list()
        self._generatorChecked = False

    def generator(self):
        """
            This function find all generators in the group G
        """

        index = 1
        G = sorted(self._g)
        for g in range(2, self._n):
            z = list()
            for entry in range(1, self._n):
                res = self._operation(g, index, self._n)
                if res not in z:
                    z.append(res)
                    index = index + 1

            # We check if that match with G
            # If yes, we find a generator
            if sorted(z) == G:
                self._generators.append(g)
        self._generatorChecked = True

    def getPrimitiveRoot(self):
        """
            This function return the primitive root modulo of n

            Returns:
                Return the primitive root of the group. None if no primitive has been found
        """

        index = 1
        G = sorted(self._g)
        for g in range(2, self._n):
            z = list()
            for entry in range(1, self._n):
                res = self._operation(g, index, self._n)
                if res not in z:
                    z.append(res)
                    index += 1

            # If the group is the same has G, we found a generator
            if sorted(z) == G:
                return g
        return None

    def getGenerators(self) -> list:
        """
            This function return all generators of that group

            Returns:
                Return the list of generators found. The function generators() must be called before to call this function
        """
        if not self._generatorChecked:
            self.generator()
            self._generatorChecked = True
        return self._generators

    def isCyclic(self) -> bool:
        """
            Check if the group is a cyclic group, means we have at least one generator

            Returns:
                REturn a boolean, False if the group is not Cyclic otherwise return True
        """
        if len(self.getGenerators()) == 0:
            return False
        return True

class Galois:
    """
        This class contain the Galois Field (Finite Field)

        Attributes:
            q (Integer): it's the number of the GF
            operation (Function): Function for generating the group
    """
    def __init__(self, q, operation):
        self._q = q
        self._operation = operation
        self._add = [[0 for x in range(q)] for y in range(q)] 

        # TODO: May do we do a deep copy between all groups ?
        self._div = [[0 for x in range(q)] for y in range(q)] 
        self._mul = [[0 for x in range(q)] for y in range(q)] 
        self._sub = [[0 for x in range(q)] for y in range(q)] 
        self._primitiveRoot = list()

    def primitiveRoot(self):
        """
            In this function, we going to find the primitive root modulo n of the galois field

            Returns:
               Return the list of primitive root of the GF(q) 
        """
        for x in range(2, self._q):
            z = list()
            for entry in range(1, self._q):
                res = self._operation(x, entry, self._q)
                if res not in z:
                    z.append(res)

            if self.isPrimitiveRoot(z, self._q - 1):
                if x not in self._primitiveRoot: # It's dirty, need to find why we have duplicate entry
                    self._primitiveRoot.append(x)
        return z

    def getPrimitiveRoot(self):
        """
            Return the list of primitives root

            Returns:
                Return the primitive root
        """
        return self._primitiveRoot

    def isPrimitiveRoot(self, z, length):
        """
            Check if z is a primitive root 

            Args:
                z (list): check if z is a primitive root
                length (Integer): Length of the GF(q)
        """
        if len(z) == length:
            return True
        return False

    def add(self):
        """
            This function do the operation + on the Galois Field

            Returns:
                Return a list of the group with the addition operation
        """
        for x in range(0, self._q):
            for y in range(0, self._q):
                self._add[x][y] = (x + y) % self._q
        return self._add

    def _inverseModular(self, a, n):
        """
            This function find the reverse modular of a by n

            Returns:
                Return the reverse modular
        """
        for b in range(1, n):
            if (a * b) % n == 1:
                inv = b
                break
        return inv

    def div(self):
        """
            This function do the operation / on the Galois Field

            Returns:
                Return a list of the group with the division operation
        """
        for x in range(1, self._q):
            for y in range(1, self._q):
                inv = self._inverseModular(y, self._q)

                self._div[x][y] = (x * inv) % self._q
        return self._div

    def mul(self):
        """
            This function do the operation * on the Galois Field

            Returns:
                Return a list of the group with the multiplication operation
        """
        for x in range(0, self._q):
            for y in range(0, self._q):
                self._mul[x][y] = (x * y) % self._q
        return self._mul

    def sub(self):
        """
            This function do the operation - on the Galois Field

            Returns:
                Return a list of the group with the subtraction operation
        """
        for x in range(0, self._q):
            for y in range(0, self._q):
                self._sub[x][y] = (x - y) % self._q
        return self._sub

    def check_closure_law(self, arithmetic):
        """
            This function check the closure law.
            By definition, every element in the GF is an abelian group, which respect the closure law: for a and b belongs to G, a + b belongs to G, the operation is a binary operation

            Args:
                Arithmetics (str): contain the operation to be made, must be '+', '*', '/' or /-'
        """
        if arithmetic not in ['+', '*', '/', '-']:
            raise Exception("The arithmetic need to be '+', '*', '/' or '-'")

        if arithmetic == '+':
            G = self._add
        elif arithmetic == '*':
            G = self._mul
        elif arithmetic == '/':
            G = self._div
        else:
            G = self._sub

        start = 0
        """
            In case of multiplicative, we bypass the first line, because all elements are zero, otherwise the test fail
        """
        if arithmetic == '*' or arithmetic == '/':
            start = 1

        isClosure = True
        for x in range(start, self._q):
            gr = Group(self._q, G[x], self._operation)
            if not gr.closure():
                isClosure = False
            del gr

        if isClosure:
            print(f"The group {arithmetic} respect closure law")
        else:
            print(f"The group {arithmetic} does not respect closure law")

    def printMatrice(self, m):
        """
            This function print the GF(m)

            Args:
                m (list): Matrix of the GF
        """
        header = str()
        header = "    "
        for x in range(0, self._q):
            header += f"{x} "

        header += "\n--|" + "-" * (len(header)- 3) +"\n"

        s = str()

        for x in range(0, self._q):
            s += f"{x} | "
            for y in range(0, self._q):
                s += f"{m[x][y]} "
            s += "\n"

        s = header + s
        print(s)