ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 22 Jun 2016 12:13:37 -0500Taking gcd with respect to one variablehttps://ask.sagemath.org/question/33734/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$Fri, 10 Jun 2016 07:17:30 -0500https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/Comment by B r u n o for <p>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).</p>
<p>I can't see any direct implementation of this in sage. Can any one suggest how to implement it.</p>
<p>Here Arithmetic is over $GF(p)$ and y is root of cyclotomic polynomial of degree r over $GF(p)$ and $q = p^r$</p>
https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33886#post-id-33886I 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 polynomialsWed, 22 Jun 2016 12:13:37 -0500https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33886#post-id-33886Comment by vishb for <p>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).</p>
<p>I can't see any direct implementation of this in sage. Can any one suggest how to implement it.</p>
<p>Here Arithmetic is over $GF(p)$ and y is root of cyclotomic polynomial of degree r over $GF(p)$ and $q = p^r$</p>
https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33740#post-id-33740One can choose 'a' to be any quadratic residue modulo pFri, 10 Jun 2016 10:17:16 -0500https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33740#post-id-33740Answer by tmonteil for <p>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).</p>
<p>I can't see any direct implementation of this in sage. Can any one suggest how to implement it.</p>
<p>Here Arithmetic is over $GF(p)$ and y is root of cyclotomic polynomial of degree r over $GF(p)$ and $q = p^r$</p>
https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?answer=33736#post-id-33736You 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
Fri, 10 Jun 2016 09:32:03 -0500https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?answer=33736#post-id-33736Comment by vishb for <p>You did not tell who is <code>a</code>, so let me chose something "random". Is the following satisfactory:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33741#post-id-33741@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.Fri, 10 Jun 2016 10:34:48 -0500https://ask.sagemath.org/question/33734/taking-gcd-with-respect-to-one-variable/?comment=33741#post-id-33741