Inverse of a polynomial which has coefficients in GF(2**64)

asked 2021-02-26 15:47:52 +0200

dtoprakhisar gravatar image

updated 2021-03-01 10:44:28 +0200

I am trying to find the inverse of this polynomial: (x^10+1)X^{2^{63}} + (x^5+1)x.

The polynomial has coefficients in GF(2**64) with modulus x^64 + x^4 + x^3 + x + 1

I can't really use the following:

sage: F.<b> = GF(2)[]
sage: S.<x> = GF(2**64, modulus = b^64 + b^4 + b^3 +b+1)
sage: 1/(x^10+1)*X +x     xxxxxxxxxx

X is a variable which takes polynomial values in GF(2**64).

edit retag flag offensive close merge delete


In what form you want to obtain the inverse? In principle, knowing that $X^{2^{64}}=X$, one can conclude that the inverse is a polynomial in $X$ of degree up to $2^{64}-1$, but it's impractical to construct such a polynomial explicitly.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-02-26 18:25:51 +0200 )edit

By inverse do you mean composition inverse?

In that case the inverse of a*X + b should be (1/a)*X + (-b/a), right?

slelievre gravatar imageslelievre ( 2021-02-27 01:41:51 +0200 )edit

Sorry! I updated my question

dtoprakhisar gravatar imagedtoprakhisar ( 2021-03-01 10:44:44 +0200 )edit

The update does not answer my question above.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-02 16:53:50 +0200 )edit

Please use a proper format for the data involved. If the code uses $b$ to generate the field $S$, which is thus $S=\Bbb F_2(b)$, then use $b$ also in the first expression. Please explain mathematically in which structure you want the inverse. This inverse cannot be in the multiplicative inverse in the polynomial ring, so which is the operation considered to get this inverse? There are a lot more questions raised by your (not really clear) question. Is it important to know which values can take that $X$? What for?

dan_fulea gravatar imagedan_fulea ( 2021-03-05 15:02:38 +0200 )edit