Ask Your Question
2

Multiplication of elements of tower fields

asked 7 years ago

Shalec gravatar image

updated 7 years ago

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?

Preview: (hide)

Comments

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 ( 7 years ago )

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 ( 7 years ago )

1 Answer

Sort by » oldest newest most voted
0

answered 7 years ago

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!

Preview: (hide)
link

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

Stats

Asked: 7 years ago

Seen: 530 times

Last updated: Nov 29 '17