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.Thu, 09 Jan 2014 11:12:05 -0600Extended Euclid with polynomialshttp://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/Suppose given polynomials $e,q,h,r$ in $R[x]$, $p \in R$ (R a ring), how can I use Sage to find $f$ in $R[x]$ so $f e = q h + r (\text{mod } p)$?
Similarly, given $f,g$ in $R[x]$ with $\text{gcd}(f,g)=1$, what function can I use to compute $s,t$ in $R[x]$ so $s f + g h = 1 (\text{mod } p)$ ?
Fri, 03 Jan 2014 12:31:55 -0600http://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/Answer by erinb for <p>Suppose given polynomials $e,q,h,r$ in $R[x]$, $p \in R$ (R a ring), how can I use Sage to find $f$ in $R[x]$ so $f e = q h + r (\text{mod } p)$?</p>
<p>Similarly, given $f,g$ in $R[x]$ with $\text{gcd}(f,g)=1$, what function can I use to compute $s,t$ in $R[x]$ so $s f + g h = 1 (\text{mod } p)$ ? </p>
http://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/?answer=15902#post-id-15902Thanks!
and is there a way to work around the use of the integermodring? I'm writing an algorithm in which I have to succesively compute different functions e.g.
s_j g_j + t_j h_j = 1 modulo p^2^j
s_j g_j + t_j h_j = 1 modulo p^2^(j+1)
Would it be best to redefine
R=PolynomialRing(IntegerModRing(p^2^j),'x') every time?Thu, 09 Jan 2014 11:12:05 -0600http://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/?answer=15902#post-id-15902Answer by wdoo for <p>Suppose given polynomials $e,q,h,r$ in $R[x]$, $p \in R$ (R a ring), how can I use Sage to find $f$ in $R[x]$ so $f e = q h + r (\text{mod } p)$?</p>
<p>Similarly, given $f,g$ in $R[x]$ with $\text{gcd}(f,g)=1$, what function can I use to compute $s,t$ in $R[x]$ so $s f + g h = 1 (\text{mod } p)$ ? </p>
http://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/?answer=15887#post-id-15887p=7
R=PolynomialRing(IntegerModRing(7),'x')
x=R.gen()
I'm not sure if f exist
Maybe
f=(q*h+r)//e
Or you want something like this?
q=f//g
r=f.mod(g)
As for the next question:
f=x^14 + 4*x^7 + 7
g=x^3+1
xgcd(f,g)
Fri, 03 Jan 2014 14:27:56 -0600http://ask.sagemath.org/question/10884/extended-euclid-with-polynomials/?answer=15887#post-id-15887