# Taking gcd with respect to one variable

I want to compute $$gcd_{X}((X-y)^2 -a , X^{\frac{q-1}{2}}-1)$$ with respect to X(taking y as a field constant).

I can't see any direct implementation of this in sage. Can any one suggest how to implement it.

Here Arithmetic is over $GF(p)$ and y is root of cyclotomic polynomial of degree r over $GF(p)$ and $q = p^r$

edit retag close merge delete

One can choose 'a' to be any quadratic residue modulo p

1

I tested what I think should be the standard way of doing this computation in Sage. Unfortunately, an implementation is lacking, and it does not work:

sage: p = 7; r = 3; q = p^r
sage: K = GF(p)
sage: R.<Y> = K[]
sage: F.<y> = PolynomialQuotientRing(R, R(cyclotomic_polynomial(r)))
sage: S.<X> = F[]
sage: gcd((X-y)^2 - 2, X^((q-1)//2)-1)
Traceback (most recent call last):
...
NotImplementedError: Univariate Quotient Polynomial Ring in y over Finite Field of size 7 with modulus Y^2 + Y + 1 does not provide a gcd implementation for univariate polynomials


Sort by » oldest newest most voted

You did not tell who is a, so let me chose something "random". Is the following satisfactory:

sage: p = 7
sage: r = 3
sage: q = p^r
sage: F = GF(p)
sage: a = F(2)

sage: R.<x> = PolynomialRing(F)
sage: P = R(cyclotomic_polynomial(r))
sage: P
x^2 + x + 1
sage: P.parent()
Univariate Polynomial Ring in x over Finite Field of size 7
sage: y = P.roots()
sage: y
4
sage: y.parent()
Finite Field of size 7
sage: P(y)
0
sage: Q = (x-y)^2-a
sage: R = x^((q-1)/2)-1
sage: gcd(Q, R)
x + 6

more

@tmonteil In your example Cyclotomic polynomial factors (here it splits that is has roots in GF(p) ), but what if it is irreducible (which it would be when ord_r(p)=r-1, take r=5 in your example). In that case your algorithms gives "No roots". I am interested in the cases when y doesn't lie in GF(p) but in some extension of it.