Computing the inverse of a generic element in a finite field extension

edit

You can extract the inverse from the following code:

sage: p = 2**64 - 2**32 + 1
sage: p
18446744069414584321
sage: F.<x> = GF(p^3, modulus=X^3 - X - 1)
sage: y, z = [root for root in (X^3 - X - 1).roots(ring=F, multiplicities=False) if root != x]
sage: R.<a,b,c> = PolynomialRing(F)
sage: e = a + b*x + c*x^2
sage: f = a + b*y + c*y^2
sage: g = a + b*z + c*z^2
sage: e*f*g
a^3 - a*b^2 + b^3 + 2*a^2*c + 18446744069414584318*a*b*c + a*c^2 - b*c^2 + c^3

Here, the number $efg$ is in the field $F\cong\Bbb F_q$, $q=p^3$, if the elements $a,b,c$ are also there. So multiplying $e$ with $fg$ delivers the above element. So the inverse of $e$ is: $$ \frac 1e= \frac {fg} {a^3 + b^3 + c^3 - ab^2 -bc^2 + ac^2 + 2a^2c -3\;abc} \ . $$ Of course, we have "ugly" expressions for $f,g$ in the numerator, which involve $y,z$ and their squares:

sage: y
6700183068485440219*x^2 + 8396469466686423992*x + 7831040667286096068
sage: z
11746561000929144102*x^2 + 10050274602728160328*x + 10615703402128488253

sage: y^2
10050274602728160328*x^2 + 3915520333643048034*x + 11746561000929144103
sage: z^2
8396469466686423992*x^2 + 14531223735771536287*x + 6700183068485440220

(There are alternative solutions, but this works for me in a simplest manner.)