Skip to content

Instantly share code, notes, and snippets.

@vbkaisetsu

vbkaisetsu/field_extension.py

Created November 6, 2016 14:34
Show Gist options
  • Save vbkaisetsu/318d9fbccfb04c16d8f95a910bcd9cf2 to your computer and use it in GitHub Desktop.
Save vbkaisetsu/318d9fbccfb04c16d8f95a910bcd9cf2 to your computer and use it in GitHub Desktop.
Download ZIP
Field Extension in Python
Raw
field_extension.py
#!/usr/bin/python3
def euculid_gcd(a, b):
x = a.zero()
y = a.identity()
x_1 = a.identity()
y_1 = a.zero()
while True:
c = a % b
if not c:
break
x_2 = x_1
y_2 = y_1
x_1 = x
y_1 = y
x = x_2 - x_1 * (a // b)
y = y_2 - y_1 * (a // b)
a = b
b = c
return (x, y, b)
def mul_poly(a, b):
c = [a[0].zero() for i in range(len(a) + len(b) - 1)]
for i, aa in enumerate(a):
for j, bb in enumerate(b):
c[i + j] += aa * bb
return c
def div_poly(a, b):
q = [a[0].zero() for i in range(max(len(a) - len(b) + 1, 0))]
r = a[:]
for i in reversed(range(len(q))):
q[i] = r[i + len(b) - 1] // b[len(b) - 1]
for k in range(len(b)):
r[i + k] -= b[k] * q[i]
return (q, r)
class SemiGroup(object):
def __mul__(self, v):
raise Exception("__mul__ is not defined")
def test(self, a, b):
if self * (a * b) != (self * a) * b:
raise Exception("Associative law test failed")
class Monoid(SemiGroup):
def identity(self):
raise Exception("identity is not defined")
def test(self, a, b):
if not self * self.identity() == self.identity() * self == self:
raise Exception("identity test failed")
SemiGroup.test(self, a, b)
class Group(Monoid):
def inverse(self):
raise Exception("inverse is not defined")
def __truediv__(self, v):
return self * v.inverse()
def test(self, a, b):
if not self * self.inverse() == self.inverse() * self == self.identity():
raise Exception("inverse test failed")
Monoid.test(self, a, b)
class AbelianGroup(Group):
def test(self, a, b):
if not (self * a == a * self and self * b == b * self):
raise Exception("Commutative propert test failed")
Group.test(self, a, b)
class AdditiveGroup(object):
def __add__(self, v):
raise Exception("__add__ is not defined")
def zero(self):
raise Exception("zero is not defined")
def __neg__(self):
raise Exception("__neg__ is not defined")
def __sub__(self, v):
return self + (-v)
def test(self, a, b):
if self + (a + b) != (self + a) + b:
raise Exception("Additive associative law test failed")
if not self + self.zero() == self.zero() + self == self:
raise Exception("zero test failed")
if not self + (-self) == (-self) + self == self.zero():
raise Exception("Additive inverse test failed")
if not (self + a == a + self and self + b == b + self):
raise Exception("Additive commutative property test failed")
class Ring(AdditiveGroup, Monoid):
def __floordiv__(self, v):
if v == v.zero():
raise Exception("Zero div")
t = self
cnt = self.zero()
while t >= v:
t -= v
cnt += self.identity()
while t < self.zero():
t += v
cnt -= self.identity()
return cnt
def __mod__(self, v):
if v == v.zero():
raise Exception("Zero div")
t = self
while t >= v:
t -= v
while t < self.zero():
t += v
return t
def test(self, a, b):
if not self * (a + b) == self * a + self * b:
raise Exception("Distributive property test failed")
if self.zero() not in (a, b):
if not (self // a * a + self % a == self and self // b * b + self % b == self):
raise Exception("Modulo failed")
AdditiveGroup.test(self, a, b)
Monoid.test(self, a, b)
class Field(Ring, AbelianGroup):
def test(self, a, b):
Ring.test(self, a, b)
if self.zero() not in (self, a, b):
AbelianGroup.test(self, a, b)
class Integer(Ring):
def __init__(self, x):
if not isinstance(x, int):
raise Exception("x is not an integer")
self.x = x
def __eq__(self, v):
return self.x == v.x
def __lt__(self, v):
return self.x < v.x
def __le__(self, v):
return self.x <= v.x
def __gt__(self, v):
return self.x > v.x
def __ge__(self, v):
return self.x >= v.x
def __bool__(self):
return bool(self.x)
def __add__(self, v):
return self.__class__(self.x + v.x)
def zero(self):
return self.__class__(0)
def __neg__(self):
return self.__class__(-self.x)
def identity(self):
return self.__class__(1)
def __mul__(self, v):
return self.__class__(self.x * v.x)
def __floordiv__(self, v):
return self.__class__(self.x // v.x)
def __mod__(self, v):
return self.__class__(self.x % v.x)
def __str__(self):
return str(self.x)
class Q(Field):
def __init__(self, x, y=None):
self.x = x
self.y = y if y else x.identity()
def __eq__(self, v):
return self.x * v.y == self.y * v.x
def __lt__(self, v):
return self.x * v.y < self.y * v.x
def __le__(self, v):
return self.x * v.y <= self.y * v.x
def __gt__(self, v):
return self.x * v.y > self.y * v.x
def __ge__(self, v):
return self.x * v.y >= self.y * v.x
def __bool__(self):
return bool(self.x)
def __add__(self, v):
return self.__class__(self.x * v.y + v.x * self.y, self.y * v.y)
def zero(self):
return self.__class__(self.x.zero())
def __neg__(self):
return self.__class__(-self.x, self.y)
def identity(self):
return self.__class__(self.x.identity())
def __mul__(self, v):
return self.__class__(self.x * v.x, self.y * v.y)
def inverse(self):
return self.__class__(self.y, self.x)
def __floordiv__(self, v):
return self.__class__((self.x * v.y) // (self.y * v.x), self.y * v.y)
def __mod__(self, v):
return self.__class__((self.x * v.y) % (self.y * v.x), self.y * v.y)
def __str__(self):
if self.y == self.y.identity():
return str(self.x)
else:
return "(%s) / (%s)" % (str(self.x), str(self.y))
def reduce(self):
_, _, p = euculid_gcd(self.x, self.y)
self.x //= p
self.y //= p
return self
class ModRing(Ring):
def __init__(self, x, n):
self.x = x
self.n = n
def __eq__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n == v.x % v.n
def __lt__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n < v.x % v.n
def __le__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n <= v.x % v.n
def __gt__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n > v.x % v.n
def __ge__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n >= v.x % v.n
def __bool__(self):
return bool(self.x % self.n)
def __add__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__(self.x + v.x, self.n)
def zero(self):
return self.__class__(self.x.zero(), self.n)
def __neg__(self):
return self.__class__(-self.x, self.n)
def identity(self):
return self.__class__(self.x.identity(), self.n)
def __mul__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__(self.x * v.x, self.n)
def __floordiv__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__((self.x % self.n) // (v.x % v.n), self.n)
def __mod__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__((self.x % self.n) % (v.x % v.n), self.n)
def __str__(self):
return "%s (mod %s)" % (str(self.x), str(self.n))
def reduce(self):
self.x %= self.n
return self
class FiniteGroup(Group, ModRing):
def inverse(self):
y, _, p = euculid_gcd(self.x, self.n)
if p == -p.identity():
y = -y
elif p != p.identity():
raise Exception("Not finite group")
return self.__class__(y, self.n)
class PolynominalRing(Ring):
def __init__(self, a):
self.a = a
def __eq__(self, v):
self.reduce()
v.reduce()
return self.a == v.a
def __bool__(self):
self.reduce()
return self.a != [self.a[0].zero()]
def __add__(self, v):
b = [self.a[0].zero() for i in range(max(len(self.a), len(v.a)))]
for i, aa in enumerate(self.a):
b[i] += aa
for i, aa in enumerate(v.a):
b[i] += aa
return self.__class__(b)
def zero(self):
return self.__class__([self.a[0].zero()])
def __neg__(self):
return self.__class__([-aa for aa in self.a])
def identity(self):
return self.__class__([self.a[0].identity()])
def __mul__(self, v):
return self.__class__(mul_poly(self.a, v.a))
def __floordiv__(self, v):
v.reduce()
q, r = div_poly(self.a, v.a)
return self.__class__(q)
def __mod__(self, v):
v.reduce()
q, r = div_poly(self.a, v.a)
return self.__class__(r)
#def apply(self, x):
#return sum(aa * x ** i for i, aa in enumerate(self.a))
def __str__(self):
s = str(" + ".join("%s x ^ %d" % (str(aa), i) for i, aa in enumerate(self.a) if aa != aa.zero()))
s = s.replace(" x ^ 0", "")
s = s.replace(" + -", " - ")
s = s.replace(" 1 x ", " x ")
if s:
return s
else:
return "0"
def reduce(self):
while len(self.a) >= 2 and self.a[-1] == self.a[-1].zero():
self.a.pop()
return self
class PolynominalModRing(Ring):
def __init__(self, x, n):
self.x = x
self.n = n
def __eq__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.x % self.n == v.x % v.n
def __bool__(self):
return bool(self.x % self.n)
def __add__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__(self.x + v.x, self.n)
def zero(self):
return self.__class__(self.x.zero(), self.n)
def __neg__(self):
return self.__class__(-self.x, self.n)
def identity(self):
return self.__class__(self.x.identity(), self.n)
def __mul__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__(self.x * v.x, self.n)
def __floordiv__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__((self.x % self.n) // (v.x % v.n), self.n)
def __mod__(self, v):
if self.n != v.n:
raise Exception("Different n")
return self.__class__((self.x % self.n) % (v.x % v.n), self.n)
def __str__(self):
return "%s (mod %s)" % (str(self.x), str(self.n))
def reduce(self):
self.x %= self.n
return self
class FinitePolynominalGroup(Group, PolynominalModRing):
def inverse(self):
y, _, p = euculid_gcd(self.x, self.n)
if p == -p.identity():
y = -y
elif p != p.identity():
raise Exception("Not finite polynominal group")
return self.__class__(y, self.n)
def main():
a = Integer(9)
b = Integer(8)
c = Integer(3)
a.test(b, c)
print(a - b - c)
print("=============")
a = Q(Integer(10))
b = Q(Integer(8))
c = Q(Integer(4))
a.test(b, c)
print((a / b - c).reduce())
print("=============")
a = ModRing(Integer(4), Integer(5))
b = ModRing(Integer(3), Integer(5))
c = ModRing(Integer(2), Integer(5))
a.test(b, c)
print((a * b - c).reduce())
print("=============")
a = FiniteGroup(Integer(4), Integer(5))
b = FiniteGroup(Integer(3), Integer(5))
c = FiniteGroup(Integer(2), Integer(5))
a.test(b, c)
print((a * b / c).reduce())
print("=============")
a = PolynominalRing([Q(Integer(1)), Q(Integer(3)), Q(Integer(3)), Q(Integer(1))])
b = PolynominalRing([Q(Integer(-1)), Q(Integer(1))])
c = PolynominalRing([Q(Integer(1)), Q(Integer(1))])
a.test(b, c)
print((a // c).reduce())
#print((a // c).apply(Q(Integer(2))))
print("=============")
a = PolynominalModRing(PolynominalRing([Q(Integer(1)), Q(Integer(3)), Q(Integer(3)), Q(Integer(1))]), PolynominalRing([Q(Integer(1)), Q(Integer(2))]))
b = PolynominalModRing(PolynominalRing([Q(Integer(-1)), Q(Integer(1))]), PolynominalRing([Q(Integer(1)), Q(Integer(2))]))
c = PolynominalModRing(PolynominalRing([Q(Integer(1)), Q(Integer(1))]), PolynominalRing([Q(Integer(1)), Q(Integer(2))]))
a.test(b, c)
print(a.reduce())
print(b.reduce())
print(c.reduce())
print((a // c).reduce())
g = PolynominalRing([Q(Integer(1)), Q(Integer(0)), Q(Integer(1))])
f = PolynominalModRing(PolynominalRing([Q(Integer(2)), Q(Integer(-3)), Q(Integer(1)), Q(Integer(2))]), g)
r = PolynominalModRing(PolynominalRing([Q(Integer(1)), Q(Integer(-5))]), g)
print(f.reduce())
print(r.reduce())
print((Q(f) / Q(r)).reduce())
print("=============")
g = PolynominalRing([Q(Integer(-2)), Q(Integer(0)), Q(Integer(1))])
f = FinitePolynominalGroup(PolynominalRing([Q(Integer(1)), Q(Integer(1))]), g)
print(f)
print((f.inverse()).reduce())
print((f * f.inverse()).reduce())
a = FinitePolynominalGroup(PolynominalRing([Q(Integer(0)), Q(Integer(1))]), g)
print(a)
print(a * a == FinitePolynominalGroup(PolynominalRing([Q(Integer(2))]), g))
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment