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$
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
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
@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.
Asked: 2016-06-10 14:17:30 +0200
Seen: 441 times
Last updated: Jun 10 '16
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
One can choose 'a' to be any quadratic residue modulo p
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: