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?
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
Asked: 2016-04-05 15:21:12 +0200
Seen: 725 times
Last updated: Apr 12 '16
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
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" `.