# Represent field element in normal basis

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 + b*NB

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

edit retag close merge delete

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" .

Sort by » oldest newest most voted

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 + b*NB == P
True
`
more