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, 25 Nov 2018 15:33:47 -0600Extended Euclidean Algorithm for Univariate Polynomials with Coefficients in a Finite Fieldhttp://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/Consider the following snippet, intended to compute the extended euclidean algorithm for polynomials in $F_q[x]$.
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
GFX.<x> = GF(5)[x]
g = x^3 + 2*x^2 - x - 2
h = x - 2
r,s,t = extended_euclides(f,g)
print("The GCD of {} and {} is {}".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == gcd(g,h), "The gcd should be {}!".format(gcd(g,h))
assert r == s*g + t*h, "The cofactors are wrong!"
Executing this snippet produces the following output:
The GCD of x^3 + 2*x^2 + 4*x + 3 and x + 3 is 3*x + 1
Its Bézout coefficients are 2*x + 4 and 3*x^2 + 4
Error in lines 45-45
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError: The gcd should be 1!
That is, my code disagrees with sagemath's `gcd` function, and I think sagemath's result is correct; `g(2)!=0`, so `g` and `h` should not have common factors.
Why is mine wrong?Thu, 22 Nov 2018 03:46:07 -0600http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/Answer by rburing for <p>Consider the following snippet, intended to compute the extended euclidean algorithm for polynomials in $F_q[x]$.</p>
<pre><code>def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
GFX.<x> = GF(5)[x]
g = x^3 + 2*x^2 - x - 2
h = x - 2
r,s,t = extended_euclides(f,g)
print("The GCD of {} and {} is {}".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == gcd(g,h), "The gcd should be {}!".format(gcd(g,h))
assert r == s*g + t*h, "The cofactors are wrong!"
</code></pre>
<p>Executing this snippet produces the following output:</p>
<pre><code>The GCD of x^3 + 2*x^2 + 4*x + 3 and x + 3 is 3*x + 1
Its Bézout coefficients are 2*x + 4 and 3*x^2 + 4
Error in lines 45-45
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError: The gcd should be 1!
</code></pre>
<p>That is, my code disagrees with sagemath's <code>gcd</code> function, and I think sagemath's result is correct; <code>g(2)!=0</code>, so <code>g</code> and <code>h</code> should not have common factors. </p>
<p>Why is mine wrong?</p>
http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?answer=44382#post-id-44382See [Wikipedia - Polynomial extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm):
> A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a non zero constant. There are several ways to define the greatest common divisor unambiguously.
> In mathematics, it is common to require that the greatest common divisor be a monic polynomial. To get this, it suffices to divide every element of the output by the leading coefficient of $r_k$. This allows that, if a and b are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any non-zero constant.
So e.g. at the end you can do
lc = r0.lc()
return r0/lc, s0/lc, t0/lcThu, 22 Nov 2018 07:26:40 -0600http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?answer=44382#post-id-44382Comment by rburing for <p>See <a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm">Wikipedia - Polynomial extended Euclidean algorithm</a>:</p>
<blockquote>
<p>A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a non zero constant. There are several ways to define the greatest common divisor unambiguously.
In mathematics, it is common to require that the greatest common divisor be a monic polynomial. To get this, it suffices to divide every element of the output by the leading coefficient of $r_k$. This allows that, if a and b are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any non-zero constant.</p>
</blockquote>
<p>So e.g. at the end you can do</p>
<pre><code>lc = r0.lc()
return r0/lc, s0/lc, t0/lc
</code></pre>
http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44433#post-id-44433Ah yes, I missed that. Nice find.Sun, 25 Nov 2018 15:33:47 -0600http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44433#post-id-44433Comment by Jsevillamol for <p>See <a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm">Wikipedia - Polynomial extended Euclidean algorithm</a>:</p>
<blockquote>
<p>A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a non zero constant. There are several ways to define the greatest common divisor unambiguously.
In mathematics, it is common to require that the greatest common divisor be a monic polynomial. To get this, it suffices to divide every element of the output by the leading coefficient of $r_k$. This allows that, if a and b are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any non-zero constant.</p>
</blockquote>
<p>So e.g. at the end you can do</p>
<pre><code>lc = r0.lc()
return r0/lc, s0/lc, t0/lc
</code></pre>
http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44432#post-id-44432EDIT: I found out I can use `sage.rings.polynomial.polynomial_ring.is_PolynomialRing` to selectively apply this solutionSun, 25 Nov 2018 11:58:22 -0600http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44432#post-id-44432Comment by Jsevillamol for <p>See <a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm">Wikipedia - Polynomial extended Euclidean algorithm</a>:</p>
<blockquote>
<p>A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a non zero constant. There are several ways to define the greatest common divisor unambiguously.
In mathematics, it is common to require that the greatest common divisor be a monic polynomial. To get this, it suffices to divide every element of the output by the leading coefficient of $r_k$. This allows that, if a and b are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any non-zero constant.</p>
</blockquote>
<p>So e.g. at the end you can do</p>
<pre><code>lc = r0.lc()
return r0/lc, s0/lc, t0/lc
</code></pre>
http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44430#post-id-44430Any ideas on how to implement this without breaking the code for other types of euclidean domains which are not polynomial rings (eg integers and gaussians)?Sun, 25 Nov 2018 11:40:42 -0600http://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/?comment=44430#post-id-44430