ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 03 Dec 2021 09:18:14 +0100Symbolic variables in finite-fieldshttps://ask.sagemath.org/question/60028/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?Wed, 01 Dec 2021 22:08:52 +0100https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/Comment by FrédéricC for <p>Hello. I have a finite-field k and its degree n extension E</p>
<pre><code>k = GF(4, 'a')
n = 64
E = k.extension(n, 'X')
</code></pre>
<p>where I perform exponentiation</p>
<pre><code>v = E.random_element()
res = v^123456789
</code></pre>
<p>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</p>
<pre><code>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
</code></pre>
<p>But this leads to "TypeError: positive characteristic not allowed in symbolic computations".</p>
<p>I noticed that polynomials could be used instead of symbolic variables (e.g., <a href="https://ask.sagemath.org/question/59697">https://ask.sagemath.org/question/59697</a>), so another idea is to write it as</p>
<pre><code>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
</code></pre>
<p>But this leads to "OverflowError: exponent overflow (65536)". It's also slow for larger values of n.</p>
<p>The next idea is to reduce $ \alpha_i^q = \alpha_i $ using an ideal</p>
<pre><code>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
</code></pre>
<p>It seems to work for values of n = 4, but for anything larger it gets stuck on computing primary decomposition for the ideal. See <a href="https://ask.sagemath.org/question/59987">https://ask.sagemath.org/question/59987</a> for details.</p>
<p>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?</p>
https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?comment=60037#post-id-60037Maybe using `BooleanPolynomialRing` ?Thu, 02 Dec 2021 13:52:12 +0100https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?comment=60037#post-id-60037Answer by Max Alekseyev for <p>Hello. I have a finite-field k and its degree n extension E</p>
<pre><code>k = GF(4, 'a')
n = 64
E = k.extension(n, 'X')
</code></pre>
<p>where I perform exponentiation</p>
<pre><code>v = E.random_element()
res = v^123456789
</code></pre>
<p>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</p>
<pre><code>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
</code></pre>
<p>But this leads to "TypeError: positive characteristic not allowed in symbolic computations".</p>
<p>I noticed that polynomials could be used instead of symbolic variables (e.g., <a href="https://ask.sagemath.org/question/59697">https://ask.sagemath.org/question/59697</a>), so another idea is to write it as</p>
<pre><code>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
</code></pre>
<p>But this leads to "OverflowError: exponent overflow (65536)". It's also slow for larger values of n.</p>
<p>The next idea is to reduce $ \alpha_i^q = \alpha_i $ using an ideal</p>
<pre><code>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
</code></pre>
<p>It seems to work for values of n = 4, but for anything larger it gets stuck on computing primary decomposition for the ideal. See <a href="https://ask.sagemath.org/question/59987">https://ask.sagemath.org/question/59987</a> for details.</p>
<p>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?</p>
https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?answer=60038#post-id-60038There 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](https://en.wikipedia.org/wiki/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.Thu, 02 Dec 2021 14:30:45 +0100https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?answer=60038#post-id-60038Comment by x63 for <p>There is no big surprise here. Elements of <code>QR</code> 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 <code>g^(k.order() - 1) - 1</code> rather than <code>g^k.order() - g</code> you disallow zero coefficients (that is, you'll get a mapping from $(k^*)^n$ to $E$ rather than from $k^n$). If you use <code>g^k.order() - g</code>, the number of monomials becomes $4^n$.</p>
<p>Anyway, to reduce an overhead, the required mapping can be obtained via <a href="https://en.wikipedia.org/wiki/Companion_matrix">companion matrix</a> as follows:</p>
<pre><code>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)
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?comment=60048#post-id-60048Thank 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.Fri, 03 Dec 2021 09:18:14 +0100https://ask.sagemath.org/question/60028/symbolic-variables-in-finite-fields/?comment=60048#post-id-60048