How is GCD defined in polynomials with coefficients in finite fields? SageMath claims gcd(xy, x) = 1 in (GF(2^128)/p(x))[y]

446 Views Asked by At

I am trying to write an algorithm to compute the GCD between polynomials whose coefficients are in the finite field $GF(2^{128})$ modulo $p(x)=x^{128}+x^7+x^2+x+1$. Let's say the polynomials have variable $y$ and we represent the coefficients as polynomials with variable $x$, e.g., ((x^80)*y^2)*(x^90)*y = (x^49 + x^44 + x^43 + x^42)*y^3.

My intuition is that $gcd(xy, x) = x$, but SageMath instead gives $1$. Is my intuition wrong, or is my code wrong? $gcd(xy, y)$ gives $y$ as expected.

K = GF(2**128, name='x', modulus=x^128+x^7+x^2+x+1)
x = K.gen()
S = PolynomialRing(K, 'y')
y = S.gen()
assert gcd(x*y, x) == 1
1

There are 1 best solutions below

0
On

To summarize the answers in the comments, gcd of polynomials is defined as the greatest common divisor $g$ of $a$ and $b$ where $deg(g) \geq deg(h)$ where $h$ is any other common divisor of $a$ and $b$. Since $deg(x) = deg(1) = 0$, both are acceptable gcds.

In the context of the algorithms I was attempting to implement (https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Distinct-degree_factorization), it turns out that they wanted the monic gcd, where the degree of the leading coefficient is 1, and which should also be unique. This implies the answer to my original question as a special case.