# inverse of a polynomial modulo another polynomial

Anonymous

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

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

( 2012-02-28 12:56:29 +0200 )edit

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

( 2012-02-28 18:11:20 +0200 )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-29 03:27:44 +0200 )edit

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