ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 12 Apr 2016 13:06:59 +0200Represent field element in normal basishttps://ask.sagemath.org/question/33004/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 = a*NB[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?Tue, 05 Apr 2016 15:21:12 +0200https://ask.sagemath.org/question/33004/represent-field-element-in-normal-basis/Comment by slelievre for <p>Hi there</p>
<p>I'm having a normal basis, which is a basis of Fpn over Fp where (n=2)
NB = [zeta, zeta<em>*p]
and a point
P = E2.change_ring(Fpn).random_element()
I would like to find a,b in Fp such that
P = a</em>NB[0] + b*NB[1]</p>
<p>Naive solutions result is memory overflow, and the Solve() function can't give me solutions with a,b in Fp. Any ideas?</p>
https://ask.sagemath.org/question/33004/represent-field-element-in-normal-basis/?comment=33005#post-id-33005To 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" `.Tue, 05 Apr 2016 15:49:21 +0200https://ask.sagemath.org/question/33004/represent-field-element-in-normal-basis/?comment=33005#post-id-33005Answer by B r u n o for <p>Hi there</p>
<p>I'm having a normal basis, which is a basis of Fpn over Fp where (n=2)
NB = [zeta, zeta<em>*p]
and a point
P = E2.change_ring(Fpn).random_element()
I would like to find a,b in Fp such that
P = a</em>NB[0] + b*NB[1]</p>
<p>Naive solutions result is memory overflow, and the Solve() function can't give me solutions with a,b in Fp. Any ideas?</p>
https://ask.sagemath.org/question/33004/represent-field-element-in-normal-basis/?answer=33077#post-id-33077 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
TrueTue, 12 Apr 2016 13:06:59 +0200https://ask.sagemath.org/question/33004/represent-field-element-in-normal-basis/?answer=33077#post-id-33077