ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 23 Aug 2013 20:56:22 +0200Convolution Polynomial Ringhttps://ask.sagemath.org/question/10465/convolution-polynomial-ring/How to define polynomial ring like Z[x]/(x^10-1) & Z_5[x]/(x^10-1) in Sage?
Following does not give gcd. I want to implement NTRU public key cryptosystem
in Sage. Hence I need this.
N=7
p=3
R2.<b> = PolynomialRing(GF(p))
S.<x> = R2.quotient(b^N - 1)
f=x^6-x^4+x^3+x^2-1
g=x^6+x^4-x^2-x
print gcd(f,g),xgcd(f,g)
Traceback (click to the left of this block for traceback)
...
TypeError: unable to find gcd*emphasized text*Fri, 23 Aug 2013 12:46:15 +0200https://ask.sagemath.org/question/10465/convolution-polynomial-ring/Answer by Luca for <p>How to define polynomial ring like Z[x]/(x^10-1) & Z_5[x]/(x^10-1) in Sage? </p>
<p>Following does not give gcd. I want to implement NTRU public key cryptosystem
in Sage. Hence I need this. </p>
<p>N=7</p>
<p>p=3</p>
<p>R2.<b> = PolynomialRing(GF(p))</b></p><b>
<p>S.<x> = R2.quotient(b^N - 1)</p>
<p>f=x^6-x^4+x^3+x^2-1</p>
<p>g=x^6+x^4-x^2-x </p>
<p>print gcd(f,g),xgcd(f,g)</p>
<p>Traceback (click to the left of this block for traceback)</p>
<p>...</p>
<p>TypeError: unable to find gcd<em>emphasized text</em></p>
</b> https://ask.sagemath.org/question/10465/convolution-polynomial-ring/?answer=15370#post-id-15370Your ring `S` is not an Euclidean domain, hence sage does not know what you mean by gcd. `R2` is an Euclidean domain. You can lift elements of `S` to elements of `R2` using the `lift()` method, e.g.:
sage: xgcd(f.lift(), g.lift())
(1, b^5 + 2*b^3 + 2*b^2 + 2, 2*b^5)
Fri, 23 Aug 2013 20:56:22 +0200https://ask.sagemath.org/question/10465/convolution-polynomial-ring/?answer=15370#post-id-15370