The following is a structural solution, selfexplanatory, using either structural maps or "canonical" lifts.

```
p = 13
R.<X> = PolynomialRing( GF(p) )
K.<v> = GF( p** 4, modulus=X^ 4 - 2 )
L.<w> = GF( p**16, modulus=X^16 - 2 )
embd = Hom( K, L )( w^4 ) # embd : K -> L, v -> w^4
f1 = K(1)
for _ in range(34):
A = K.random_element()
f1 = f1^2 * A
g1 = embd(f1)
print "f1 is in K = %s" % f1
print "we map f1 in K to g1 in L via\n", embd
print "g1 is in L = %s" % g1
G1 = R(g1) # the polynomial lift, the coefficients can now be easily extracted
g1coeff = G1.coefficients( sparse=False )
print "g1 has the coefficients", g1coeff
print "g1 has the hex coefficients", [ hex(ZZ(c)) for c in g1coeff ]
hexcoeff = [ hex(ZZ(c)) for c in g1coeff ]
hexcoeff . reverse()
hexrep = ''.join( hexcoeff )
print "hex representation:", hexrep
```

I considered that making all computations in `K`

, as long as possible, then at the end pass to `L`

, should be optimal.
Alternatively, one can push immediately every `A`

in the loop to `embd( A )`

from `K`

to `L`

, and compute everything in `L`

, if the real life intention / application needs it there .

Results in this run:

```
f1 is in K = v^3 + 9*v^2 + 8*v + 10
we map f1 in K to g1 in L via
Ring morphism:
From: Finite Field in v of size 13^4
To: Finite Field in w of size 13^16
Defn: v |--> w^4
g1 is in L = w^12 + 9*w^8 + 8*w^4 + 10
g1 has the coefficients [10, 0, 0, 0, 8, 0, 0, 0, 9, 0, 0, 0, 1]
g1 has the hex coefficients ['a', '0', '0', '0', '8', '0', '0', '0', '9', '0', '0', '0', '1']
hex representation: 100090008000a
```

This should be all you need, enjoy!

The element

`f1`

is defined and stays all time during the loop in`R16`

. For instance:A random element in

`R16`

is also like:and if we repeat this often enough we will get also an element "without

`w`

".I'll try to give an other construction of the fields, so that there ...(more)

f1 has to be a R16 element, and A a R4 element. I build up a small, but ugly, work around. I take every A and put it in a List. Then, in the end, I return that list and convert each element to a Poly=PolynomialRing(R) element, where f1 is also an PolynomialRing(R) element. Then I do the multiplication over that PolynomialRing and do a "lazy reduction" in the end, by "Poly(R16(List[pos]))". From this position, I'm able to print via ".list()" any coefficient in Hex.