Ask Your Question

Extended Euclidean Algorithm for Univariate Polynomials with Coefficients in a Finite Field

asked 2018-11-22 10:46:07 +0200

Jsevillamol gravatar image

updated 2018-11-22 10:48:25 +0200

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/", 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?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2018-11-22 14:26:40 +0200

rburing gravatar image

See Wikipedia - 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 =
return r0/lc, s0/lc, t0/lc
edit flag offensive delete link more



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

Jsevillamol gravatar imageJsevillamol ( 2018-11-25 18:40:42 +0200 )edit

EDIT: I found out I can use sage.rings.polynomial.polynomial_ring.is_PolynomialRing to selectively apply this solution

Jsevillamol gravatar imageJsevillamol ( 2018-11-25 18:58:22 +0200 )edit

Ah yes, I missed that. Nice find.

rburing gravatar imagerburing ( 2018-11-25 22:33:47 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2018-11-22 10:46:07 +0200

Seen: 3,124 times

Last updated: Nov 22 '18