# 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

Maybe using BooleanPolynomialRing ?

( 2021-12-02 13:52:12 +0200 )edit

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.

( 2021-12-03 09:18:14 +0200 )edit