228 lines
7.0 KiB
Python
228 lines
7.0 KiB
Python
#!/usr/bin/env python3
|
||
|
||
from Cryptotools.Groups.group import Group
|
||
|
||
|
||
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
|
||
identityAdd (Integer): it's the identity element in the GF(n) for the addition operation
|
||
identityMul (Integer): it's the identity element in the GF(n) for the multiplicative operation
|
||
"""
|
||
def __init__(self, q, operation):
|
||
self._q = q
|
||
self._operation = operation
|
||
self._identityAdd = 0
|
||
self._identityMul = 1
|
||
self._F = [x for x in range(q)]
|
||
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 check_identity_add(self):
|
||
"""
|
||
This function check the identity element and must satisfy this condition: $a + 0 = a$ for each element in the GF(n)
|
||
In Group Theory, an identity element is an element in the group which do not change the value every element in the group
|
||
|
||
Returns:
|
||
|
||
"""
|
||
for x in self._F:
|
||
if not self._identityAdd + x == x:
|
||
raise Exception(
|
||
f"The identity element {self._identityAdd} "\
|
||
"do not satisfy $a + element = a$"
|
||
)
|
||
|
||
def check_identity_mul(self):
|
||
"""
|
||
This function check the identity element and must satisfy this condition: $a * 1 = a$ for each element in the GF(n)
|
||
In Group Theory, an identity element is an element in the group which do not change the value every element in the group
|
||
|
||
Returns:
|
||
|
||
"""
|
||
for x in self._F:
|
||
if not self._identityMul * x == x:
|
||
raise Exception(
|
||
f"The identity element {self._identityAdd} "\
|
||
"do not satisfy $a * element = a$"
|
||
)
|
||
|
||
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)
|