Revision history [back]

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