Ask Your Question
0

inverse of a polynomial modulo another polynomial

asked 2012-02-28 11:47:08 +0100

anonymous user

Anonymous

updated 2012-02-28 12:07:01 +0100

DSM gravatar image

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 flag offensive close merge delete

Comments

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

burcin gravatar imageburcin ( 2012-02-28 12:56:29 +0100 )edit

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

Simon King gravatar imageSimon King ( 2012-02-28 18:11:20 +0100 )edit
1

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

Francis Clarke gravatar imageFrancis Clarke ( 2012-02-29 03:27:44 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2017-03-05 20:18:12 +0100

dan_fulea gravatar image
sage: F.<b> = GF(2)[]
sage: S.<x> = GF( 2**4, modulus = b^4 + b + 1 )
sage: 1/(x^3+1)
x
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2012-02-28 11:47:08 +0100

Seen: 5,034 times

Last updated: Mar 05 '17