Revision history [back]

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, the most direct way to get the required mapping is via companion matrix:

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 degrees 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.

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, the most direct way to get the required mapping is via companion matrix:

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)
v:', v[:,0].T)
print('Coefficients of v^65537:',(v^65537)[:,0].T)
v^65537:', (v^65537)[:,0].T)

It works quite fast for degrees 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.

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, the most direct way to get reduce an overhead, the required mapping is 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.