Ask Your Question
1

Symbolic variables in finite-fields

asked 2021-12-01 22:08:52 +0100

x63 gravatar image

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 flag offensive close merge delete

Comments

Maybe using BooleanPolynomialRing ?

FrédéricC gravatar imageFrédéricC ( 2021-12-02 13:52:12 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2021-12-02 14:30:45 +0100

Max Alekseyev gravatar image

updated 2021-12-02 14:44:05 +0100

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.

edit flag offensive delete link more

Comments

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.

x63 gravatar imagex63 ( 2021-12-03 09:18:14 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-12-01 22:08:52 +0100

Seen: 52 times

Last updated: Dec 02 '21