Ask Your Question

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

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

## 1 Answer

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

## Your Answer

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

Add Answer

## Stats

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

Seen: 602 times

Last updated: Apr 12 '16