# Symbolic variables in finite-fields

Hello. I have a finite-field k and its degree n extension E

k = GF(4, 'a')
n = 64
E = k.extension(n, 'X')


where I perform exponentiation

v = E.random_element()
res = v^123456789


My goal is to track an element in k^n, mapped to E, as the exponentiation in E occurs. Ideally, I would write it as

alphas = var(["alpha_%d" % i for i in range(n)])
v = 0
for i in range(n):
v += alphas[i]*E.gen()^i
res = v^123456789


But this leads to "TypeError: positive characteristic not allowed in symbolic computations".

I noticed that polynomials could be used instead of symbolic variables (e.g., https://ask.sagemath.org/question/59697), so another idea is to write it as

k = GF(4, 'a')
n = 8
R = PolynomialRing(k, ["alpha_%d" % i for i in range(n)])
P = PolynomialRing(k, 'x')
E = R.extension(P.irreducible_element(n), 'X')

v = 0
for i in range(n):
v += R.gen(i)*E.gen()^i
res = v^65536


But this leads to "OverflowError: exponent overflow (65536)". It's also slow for larger values of n.

The next idea is to reduce $\alpha_i^q = \alpha_i$ using an ideal

k = GF(4, 'a')
n = 4
R = PolynomialRing(k, n, 'x')
I = R.ideal([g^(k.order() - 1) - 1 for g in R.gens()])
QR = R.quotient(I, 'alpha')
P = PolynomialRing(k, 'x')
BR = PolynomialRing(QR, 'Y')
E = BR.extension(P.irreducible_element(n), 'X')

v = 0
for i in range(n):
v += QR.gen(i)*E.gen()^i
res = v^65537


It seems to work for values of n = 4, but for anything larger it gets stuck on computing primary decomposition for the ideal. See https://ask.sagemath.org/question/59987 for details.

Is there a way to do this in SageMath or, perhaps, using one of the underlying systems, such as Singular, and then move back to SageMath?

edit retag close merge delete

Sort by » oldest newest most voted There is no big surprise here. Elements of QR have distinct monomials $\alpha_1^{d_1}\dots \alpha_n^{d_n}$, where $d_i\in[0,2]$. That is, your polynomials will contain as many as $3^n$ distinct monomials. Btw, by using g^(k.order() - 1) - 1 rather than g^k.order() - g you disallow zero coefficients (that is, you'll get a mapping from $(k^*)^n$ to $E$ rather than from $k^n$). If you use g^k.order() - g, the number of monomials becomes $4^n$.

Anyway, to reduce an overhead, the required mapping can be obtained via companion matrix as follows:

k = GF(4, 'a')
n = 8
R = PolynomialRing(k, ["alpha_%d" % i for i in range(n)])
QR = R.quotient([r^k.order()-r for r in R.gens()])
P = PolynomialRing(k, 'x')
f = P.irreducible_element(n)

v = sum( QR.gen(i)*companion_matrix(f)^i for i in range(n) )

print('Coefficients of v:', v[:,0].T)
print('Coefficients of v^65537:', (v^65537)[:,0].T)


It works quite fast for exponents around powers of 2 (like 65537), but it'll be slow for something random simply because there will be polynomials with about $4^n$ terms.

more

Thank you for the idea. I will leave my mistake with the ideal in the question to match your answer. I also tested it with n = 32 and got the result in a couple of minutes, so it's a big improvement to where I was.