Ask Your Question
1

Represent field element in normal basis

asked 2016-04-05 15:21:12 +0100

Belphegor gravatar image

Hi there

I'm having a normal basis, which is a basis of Fpn over Fp where (n=2) NB = [zeta, zeta*p] and a point P = E2.change_ring(Fpn).random_element() I would like to find a,b in Fp such that P = aNB[0] + b*NB[1]

Naive solutions result is memory overflow, and the Solve() function can't give me solutions with a,b in Fp. Any ideas?

edit retag flag offensive close merge delete

Comments

To display blocks of code, either indent them with 4 spaces, or select the corresponding lines and click the "code" button (the icon with '101 010'). Can you edit your question to do that?

To display inline code, surround it within "backticks" or "backquotes" `.

slelievre gravatar imageslelievre ( 2016-04-05 15:49:21 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2016-04-12 13:06:59 +0100

B r u n o gravatar image

If I understand your problem correctly, this is simply linear algebra. Let me denote by $F$ the field $GF(p)$ (for $p=123457$ for instance), and $K = GF(p^2)$, with variable $z$:

sage: p = 123457
sage: F = GF(p)
sage: K.<z> = F.extension(2) # or: K.<z> = GF(p^2)
sage: P = K.random_element()
sage: zeta = z+3 # happens to be a generator of a normal basis
sage: NB = [zeta, zeta^p]
sage: P = K.random_element()

OK, now I have defined all the objects. Next, I turn the problem into linear algebra:

sage: v = vector(P.polynomial().coefficients())
sage: v
(62425, 47898)
sage: M = matrix([n.polynomial().coefficients() for n in NB]).transpose()
sage: M
[     3      2]
[     1 123456]
sage: a, b = M.solve_right(v)
sage: a*NB[0] + b*NB[1] == P
True
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

Stats

Asked: 2016-04-05 15:21:12 +0100

Seen: 832 times

Last updated: Apr 12 '16