Ask Your Question

Multiplication of elements of tower fields

asked 2017-11-29 09:31:10 +0200

Shalec gravatar image

updated 2017-11-29 09:38:09 +0200


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 flag offensive 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)

dan_fulea gravatar imagedan_fulea ( 2017-11-29 10:00:55 +0200 )edit

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.

Shalec gravatar imageShalec ( 2017-11-29 10:25:56 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2017-11-29 14:58:57 +0200

dan_fulea gravatar image

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!

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-11-29 09:31:10 +0200

Seen: 414 times

Last updated: Nov 29 '17