Taking gcd with respect to one variable

asked 8 years ago

vishb
93 ●3 ●3 ●10

updated 8 years ago

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$

Comments

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

vishb ( 8 years ago )

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 ( 8 years ago )

add a comment

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 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

Comments

@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 ( 8 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.

Taking gcd with respect to one variable

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Taking gcd with respect to one variable savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Taking gcd with respect to one variable