# Multiplication of elements of tower fields

Let

p=13
R = GF(p)

_.<v> = PolynomialRing(R)
R4.<v> = R.extension(v^4 - 2, 'v')
_.<w> = PolynomialRing(R4)
R16.<w> = R4.extension(w^4-v, 'w')


I need to compute

f1 = R16(1)
for i in range(34):
A=R4.random_element() #in my case, this is not random, its derived by an function
f1 = f1^2*A #this is not the whole code, but it displayes the problem


This element stays allways in R4. But the result i expect, is an element of R16.

So: How can I tell sage to use the R16 multiplication instead? I need a full degree 15 polynomial. If it is possible, in one variable (w, since w^4=v).

Furthermore: How can I tell Sage to print any coefficient in Hex?

edit retag close merge delete

The element f1 is defined and stays all time during the loop in R16. For instance:

sage: f1 = R16(1)
sage: A = R4.random_element()
sage: A.parent()
Finite Field in v of size 13^4
sage: f1 = f1^2 * A
sage: f1
6*v^3 + 4*v^2 + 10*v + 6
sage: f1.parent()
Univariate Quotient Polynomial Ring in w over Finite Field in v of size 13^4 with modulus w^4 + 12*v


A random element in R16 is also like:

sage: R16.random_element()
(v^3 + 3*v^2 + 2*v + 1)*w^3 + (3*v^2 + 3*v + 10)*w^2 + (8*v^3 + v^2 + 7*v + 5)*w + 5*v^3 + 9*v^2 + v + 12


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.

Sort by » oldest newest most voted

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!

more