Ask Your Question

# inverse of a polynomial modulo another polynomial

Hi, I'm trying to implement the Baby Step Giant Step algorithm in the group of units of prime fields. I would like to generate the field provided one generator polynomial. But I need to calculate p^(-1) (where p is a polynomial), but can't find a function to do so. This is what I'm doing,

F.<a> = GF(2)[];
R.<b> = PolynomialRing(F)
S.<x> = R.quotient(b^4+b+1)

m = sqrt(S.modulus().degree());
gamma = S.modulus();
alpha = x^3+1;

now i need to calculate (alpha)^(-1) modulo gamma

Any help? Better ways to do the same thing?

Thanks!

edit retag close merge delete

## Comments

You should look up the extended gcd algorithm. This is implemented by the xgcd() function in Sage.

( 2012-02-28 05:56:29 -0500 )edit

Burcin, xgcd doesn't work. It fails with a type error, "cannot coerce nonconstant polynomial".

( 2012-02-28 11:11:20 -0500 )edit
1

If you define R over the fraction field of F, or simply over GF(2), then alpha^-1 yields the answer.

( 2012-02-28 20:27:44 -0500 )edit

## 1 answer

Sort by ยป oldest newest most voted
sage: F.<b> = GF(2)[]
sage: S.<x> = GF( 2**4, modulus = b^4 + b + 1 )
sage: 1/(x^3+1)
x
more

## Your Answer

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

Add Answer

## Stats

Asked: 2012-02-28 04:47:08 -0500

Seen: 2,306 times

Last updated: Mar 05 '17