CODEWITHSUNDEEP
pythonsympysymbolic-math
Frunobulax
Frunobulax

Reputation: 345

How to work with polynomials over Galois fields in SymPy

How are Galois fields represented in SymPy? I couldn't find any documentation for this online, but SymPy contains a module called "galoistools", so I thought I should give it a try. I tried the following experiment:

from sympy import *
x = symbols("x")
A = [LC(Poly(i*x, modulus=8) * Poly(j*x, modulus=8)) for i in range(1, 8) for j in range(1, i+1)]
B = [LC(Poly(i*x, domain=GF(8)) * Poly(j*x, domain=GF(8))) for i in range(1, 8) for j in range(1, i+1)]

However, the resulting lists A and B are identical, so I'm obviously misunderstanding how this is supposed to be used. I'm trying to work in GF(8), i.e. GF(2^3), which is not the same as computing modulo 8.

Upvotes: 2

Views: 3271

Answers (2)

JamesTheAwesomeDude
JamesTheAwesomeDude

Reputation: 1053

As of November 2023, the previous answer is still correct; the so-called "galoistools" module is still semantically broken—not actually implementing galois fields, but only integer extension rings—gh-9544, gh-13886, and gh-21104.

However, in July of 2018, SymPy 1.2 released, with sympy.polys.agca.extensions.FiniteExtension, which actually *does* offer methods for galois fields, including correct multiplication and inversion.

from sympy import Symbol, PurePoly
from sympy.polys.agca.extensions import FiniteExtension
X = Symbol('X')

# Conway multiplication
F_2_8 = FiniteExtension(PurePoly(X**8 + X**4 + X**3 + X**2 + 1, modulus=2))

# AES multiplication
F_AES = FiniteExtension(PurePoly(X**8 + X**4 + X**3 + X    + 1, modulus=2))

assert F_2_8(X**5 + X) * F_2_8(X**6 + 1) == F_2_8(X**6 + X**3 + X)
assert F_2_8(X**3 + X**2 + X) * F_2_8(X**3 + X**2 + X).inverse() == F_2_8(1)

It may also be worth noting that gf_add works; it's only gf_mul (and related methods) that's broken. And it's not even that broken; it only neglects the reduction step; so a "correct" gf_mul can be easily whipped up as follows:

from sympy.polys.domains import ZZ
from sympy.polys.galoistools import gf_degree, gf_irreducible_p, gf_mul, gf_rem

def actual_gf_mul(f, g, p, r, K=ZZ):
    n = gf_degree(r)-1
    assert gf_irreducible_p(r, p, K), f"gf_mul[{p},{n}]: r={r} is not irreducible"
    return gf_rem(gf_mul(f, g, p, K), r, p, K)

Upvotes: 0

user6655984
user6655984

Reputation:

At present SymPy does not have support for finite fields other than Z/pZ. The existing class GF(n) is misleadingly named; it actually implements Z/nZ as you observed.

However, using the low-level routines already present in SymPy's galoistools module, one can create a class for general finite fields GF(p^n) and for polynomials over such a field: see this answer where these classes are implemented (for the purpose of computing an interpolating polynomial, but they can be used for other things too). This is just a minimal class; it does not interface with advanced polynomial manipulation methods that are implemented in SymPy.

Upvotes: 3

Related Questions