Ask Your Question

Finite field q power computations

asked 2016-03-29 07:19:40 -0500

Belphegor gravatar image

updated 2016-06-04 04:57:27 -0500

FrédéricC gravatar image

Hey there, i'm trying to make a fast computation algorithm using shift operations. I'm having a field GF(q) and a field GF(q^m) for some integer m and i have an element x \in GF(q^m). I want to represent x in a normal basis of the vectorspace GF(q^m) over GF(q), so that I can use shift operations for computing x^q^k fast. Are there any way of doing this ?

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted

answered 2016-03-30 10:30:45 -0500

B r u n o gravatar image

updated 2016-03-30 10:38:08 -0500

When you have an element of x of GF(q^m), x.polynomial() gives you the polynomial (over GF(q)) that represents x, and then you can have its coefficients using .coefficients():

sage: R.<a> = GF(17^22)
sage: x = R.random_element()
sage: x.polynomial().coefficients()
[10, 15, 5, 16, 2, 1, 5, 9, 12, 10, 12, 3, 16, 9, 1, 16, 7, 7, 2, 10, 3, 4]
edit flag offensive delete link more

answered 2016-04-04 11:56:36 -0500

Belphegor gravatar image

Thanks, but I need it representet in its normal basis? Not its polynomial basis such that I can make shift operations. That is: x in GF(q^m) Represent GF(q^m) over GF(q) in its normal basis like {a, a^q, ..., a^q^(m-1)} Represent x in form of the basis {a, a^q, ..., a^q^(m-1)}, say (v_1, v_2, ... v_m) make shift (v_m, v_1, ... v_m-1) use it to compute further stuff.. Also i might as if Sage has such an operation?

edit flag offensive delete link more


I think what i'm searching for is a = GF(q^m).element.primitive() V = VectorSpace(GF(q),1) S = V.subspace([V([a]),V([a^q])]) now I just need to represent x,y in GF(q^m) in form the vector space S? and then transforme (x,y,1) into a point on an elliptic curve defined over GF(q^m), any ideas?

Belphegor gravatar imageBelphegor ( 2016-04-04 12:12:18 -0500 )edit

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: 2016-03-29 07:19:40 -0500

Seen: 113 times

Last updated: Apr 04 '16