Ask Your Question

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

asked 2022-05-25 18:28:14 +0200

Wimet gravatar image

updated 2022-10-06 16:15:04 +0200

FrédéricC gravatar image

I am working in the following field extension:

p = 2**64-2**32+1
P.<X,A,B,C> = PolynomialRing(GF(p))
GF.<x,a,b,c> = P.quotient_ring(X^3-X-1)

My objective is to take a generic element of this field p(x) = a + b*x + c*x^2 and compute its inverse, where its coefficients are a function of a,b,c.

However, if I try to directly do it:

q = x^2
qinv = 1 / q

I get a singular error. I get an error (ArithmeticError: Division failed. The numerator is not a multiple of the denominator.) if I change the prime to, say, 5. If I do not use the variables to express the generic coefficients of p(x), then clearly it works, but I do not get the desired result.

Is there any way I can achieve what I need?

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2022-05-26 18:18:21 +0200

dan_fulea gravatar image

You can extract the inverse from the following code:

sage: p = 2**64 - 2**32 + 1
sage: p
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.)

edit flag offensive delete link more


Thank you very much! I think that there is a missing line of code that defines the "X". Something like:

P.<X> = PolynomialRing(GF(p))

Follow-up question: Is there any way I can compute the inverse of the denominator of $1/e$? I want to know if it is possible to obtain an expression that avoids computing inverses of elements in $\mathbb{F}_p$; so $1/e = fg * (\text{something}^{-1})$, instead of $1/e = fg / (\text{something})$, where $\text{something}$ is the denominator that you obtained through $efg$.

Wimet gravatar imageWimet ( 2022-05-26 20:06:53 +0200 )edit

answered 2022-05-27 15:01:31 +0200

Max Alekseyev gravatar image

This looks like a simplest solution:

p = 2**64-2**32+1
P.<a,b,c> = PolynomialRing(GF(p))
Q.<X> = PolynomialRing(P.fraction_field())
R.<x> = Q.quotient_ring(X^3-X-1)

print( 1 / (a + b*x + c*x^2) )
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2022-05-25 18:28:14 +0200

Seen: 522 times

Last updated: May 27 '22