ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 05 Mar 2017 13:18:12 -0600inverse of a polynomial modulo another polynomialhttp://ask.sagemath.org/question/8756/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!
Tue, 28 Feb 2012 04:47:08 -0600http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/Comment by Simon King for <p>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,</p>
<pre><code>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;
</code></pre>
<p>now i need to calculate (alpha)^(-1) modulo gamma</p>
<p>Any help? Better ways to do the same thing?</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20204#post-id-20204Burcin, xgcd doesn't work. It fails with a type error, "cannot coerce nonconstant polynomial".Tue, 28 Feb 2012 11:11:20 -0600http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20204#post-id-20204Comment by Francis Clarke for <p>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,</p>
<pre><code>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;
</code></pre>
<p>now i need to calculate (alpha)^(-1) modulo gamma</p>
<p>Any help? Better ways to do the same thing?</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20200#post-id-20200If you define R over the fraction field of F, or simply over GF(2), then alpha^-1 yields the answer.Tue, 28 Feb 2012 20:27:44 -0600http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20200#post-id-20200Comment by burcin for <p>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,</p>
<pre><code>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;
</code></pre>
<p>now i need to calculate (alpha)^(-1) modulo gamma</p>
<p>Any help? Better ways to do the same thing?</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20205#post-id-20205You should look up the extended gcd algorithm. This is implemented by the xgcd() function in Sage.Tue, 28 Feb 2012 05:56:29 -0600http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?comment=20205#post-id-20205Answer by dan_fulea for <p>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,</p>
<pre><code>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;
</code></pre>
<p>now i need to calculate (alpha)^(-1) modulo gamma</p>
<p>Any help? Better ways to do the same thing?</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?answer=36840#post-id-36840 sage: F.<b> = GF(2)[]
sage: S.<x> = GF( 2**4, modulus = b^4 + b + 1 )
sage: 1/(x^3+1)
x
Sun, 05 Mar 2017 13:18:12 -0600http://ask.sagemath.org/question/8756/inverse-of-a-polynomial-modulo-another-polynomial/?answer=36840#post-id-36840