Ask Your Question

Taking gcd with respect to one variable

asked 2016-06-10 07:17:30 -0600

vishb gravatar image

updated 2016-06-10 09:14:14 -0600

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 flag offensive close merge delete


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

vishb gravatar imagevishb ( 2016-06-10 10:17:16 -0600 )edit

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
B r u n o gravatar imageB r u n o ( 2016-06-22 12:13:37 -0600 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2016-06-10 09:32:03 -0600

tmonteil gravatar image

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()[0][0]
sage: y
sage: y.parent()
Finite Field of size 7
sage: P(y)
sage: Q = (x-y)^2-a
sage: R = x^((q-1)/2)-1
sage: gcd(Q, R)
x + 6
edit flag offensive delete link 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.

vishb gravatar imagevishb ( 2016-06-10 10:34:48 -0600 )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: 2016-06-10 07:17:30 -0600

Seen: 49 times

Last updated: Jun 10 '16