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

asked 2 years ago

Wimet
13 ●1 ●1 ●3

updated 2 years ago

FrédéricC

5426 ●4 ●44 ●121

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?

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2 years ago

dan_fulea
5650 ●5 ●44 ●97

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.)

link

Comments

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 ( 2 years ago )

add a comment

answered 2 years ago

Max Alekseyev

6932 ●9 ●52 ●162

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) )

link

add a comment

Your Answer

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

Add Answer

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

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

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

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

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