1 | initial version |

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.

2 | No.2 Revision |

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.

3 | No.3 Revision |

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.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.