Inverse of a polynomial

[Santanu Sarkar]

How to calculate inverse of a polynomial f(x) modulo g(x) in the finite field GF(2^10)?

[Simon King]

Hi Santanu!

On 25 Aug., 18:03, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:

> How to calculate inverse of a polynomial f(x) modulo g(x) in the finite
> field GF(2^10)?

The usual way to compute modular inverses in a polynomial ring over a
field is the extended Euclidean algorithm, xgcd.

We start with a polynomial ring over GF(2^10):
sage: P.<x> = GF(2^10,'z')[]

Next, we get two random polynomials. They happen to be relatively
prime, hence, there *is* an inverse of the first polynomial modulo the
second polynomial:
sage: p = P.random_element()
sage: q = P.random_element()
sage: gcd(p,q)
1

Now, xgcd is a method of q, and I suggest that you read its
documentation.

sage: d, _, pinv = q.xgcd(p)
sage: d # test again that the gcd is one
1

Now, we verify that pinv really is the inverse of p modulo q:

sage: q.divides(1-p*pinv)
True

Best regards,
Simon

[Santanu Sarkar]

Dear Simon,

 Thanks a lot.

With regards,

Santanu 

--
To post to this group, send email to sage-s...@googlegroups.com
To unsubscribe from this group, send email to sage-support...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URL: http://www.sagemath.org

[john_perry_usm]

Should this be a feature of an element of a finite field? As you point
out, it doesn't seem too hard to implement, and would seem to be an
important feature.

john perry

[Maarten Derickx]

This is already implemented in the sage i'm running (4.7.2.alpha2)

sage:  P.<x> = GF(2^10,'z')[]

sage: p = P.random_element()

sage: q = P.random_element()

sage: p.inverse_mod(q)

(z^7 + z^6 + z^5 + z^4 + z^3 + z^2 + z)*x + z^2 + z