How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field?

Escolopendra
33 ●1 ●1 ●6

Hi, as the title says I`m trying to define a function that finds the gcd of two polynomial without using the pre-established function gcd. I've tried everything I thought it would work:

First, I tried to use the Euclidan Algorithm, for that you need to divide the polynomials. Knowing so, I tried to find the degrees of the different polynomials to divide in consequence of the degrees (which gave me error). Then I tried it without the degree part and it didn't work at all since % couldn't be used as a divisor of polynomials.

def GCD(field, f, g):
  R.<x> = PolynomialRing(field, 'x')
  x.parent() 
  a = f.degree()
  b = g.degree()
  if a>b:
    while g != 0: 
        r = g
        g = f%g
  else:
    while f != 0:
        r = g
        f = g%f
  return r

Shortly after I tried to factor both of the polynomial and make the función return the part that repeated. But I rapidly saw my hopes decay when I realized I have not a single clue in how to do so (even though I've done some research I couldn't find the answer).

def mcd(field, f, g): 
  R.<x> = PolynomialRing(field) 
  a = f.factor()
  b = g.factor()

And this was the last code I wrote before asking for some enlightening:

def MCD(Field,PolynomialA, PolinomialB):
  R.<x> = PolynomialRing(Field, 'x')
  a = PolynomialA
  b = PolynomialB
  c = 1
  while c != 0:
    c = a%b 
    a = b
    b = c
  return a

add a comment

answered 3 years ago

rburing

10964 ●4 ●80 ●219 https://www.rburing.nl/

It seems that you try to use the following idea: $\gcd(f,g) = f$ if $g=0$ and otherwise it equals $\gcd(g, f \mbox{ mod } g)$ . So while $g \neq 0$ you should set $(f, g) := (g, f \mbox{ mod } g)$ , and at the end return $f$ . To express this without assignment of a tuple (even though that is possible in SageMath/Python) you can use a temporary variable, say $r$ : first put $r:=g$ and then $g:=f \mbox{ mod } g$ and then $f:=r$ . In code it becomes:

def mygcd(f,g):
    while g != 0:
        r = g
        g = f % g
        f = r
    return f/f.lc()

You almost had this, just somehow not using the temporary variable correctly. I also changed the last line to return a monic polynomial (this is a convention, e.g. followed by SageMath's own gcd).

The function works when passed elements of a polynomial ring such as R.<x> = PolynomialRing(QQ).

Comments

Thank you very much it works perfectly.

Escolopendra ( 3 years ago )

add a comment

Your Answer

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

How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field?

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field? savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field?