Ask Your Question

Extended Euclid with polynomials

asked 2014-01-03 19:31:55 +0200

erinb gravatar image

updated 2014-01-03 21:19:49 +0200

calc314 gravatar image

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)$ ?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2014-01-03 21:27:56 +0200

wdoo gravatar image

p=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



edit flag offensive delete link more

answered 2014-01-09 18:12:05 +0200

erinb gravatar image

updated 2014-01-09 18:12:26 +0200


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?

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


Asked: 2014-01-03 19:31:55 +0200

Seen: 1,297 times

Last updated: Jan 09 '14