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.Tue, 21 Jan 2020 22:33:20 +0100center lift of a polynomial?https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/Hello! I am trying to code up the NTRU example in Hoffstein, Pipher and Silverman. Anyone know if the "center lift" of a polynomial is implemented in Sage? I am working the quotient ring:
Z_7[x] / x^5 - 1
I have a(x) = 5 + 3x - 6x^2 + 2x^3 + 4x^4
The center lift takes this a polynomial with coefficients in the range of - 7/2 < coeff <= 7/2.
Thus a(x) -> -2 + 3x + x^2 + 2x^3 - 3x^4
But what I get is:
N = 5
q = 7
P.<x> = GF(q)[]
Q = QuotientRing(P, x^N - 1)
a = 5 + 3*x - 6*x^2 + 2*x^3 + 4*x^4
aa = Q(a)
aa.lift()
4*x^4 + 2*x^3 + x^2 + 3*x + 5
Any thoughts? I guess I could write my own function to do the center lifting...
Thanks!
SusanTue, 21 Jan 2020 01:55:52 +0100https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/Answer by vdelecroix for <p>Hello! I am trying to code up the NTRU example in Hoffstein, Pipher and Silverman. Anyone know if the "center lift" of a polynomial is implemented in Sage? I am working the quotient ring:</p>
<p>Z_7[x] / x^5 - 1</p>
<p>I have a(x) = 5 + 3x - 6x^2 + 2x^3 + 4x^4</p>
<p>The center lift takes this a polynomial with coefficients in the range of - 7/2 < coeff <= 7/2.</p>
<p>Thus a(x) -> -2 + 3x + x^2 + 2x^3 - 3x^4 </p>
<p>But what I get is:</p>
<pre><code>N = 5
q = 7
P.<x> = GF(q)[]
Q = QuotientRing(P, x^N - 1)
a = 5 + 3*x - 6*x^2 + 2*x^3 + 4*x^4
aa = Q(a)
aa.lift()
4*x^4 + 2*x^3 + x^2 + 3*x + 5
</code></pre>
<p>Any thoughts? I guess I could write my own function to do the center lifting...</p>
<p>Thanks!
Susan</p>
https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/?answer=49630#post-id-49630Be careful that your lifted polynomial is **not** a polynomial in ZZ but in GF(q). You can check with
sage: aa.lift().parent()
Univariate Polynomial Ring in x over Finite Field of size 7
What you actually want is the "centered lift of this lift". A one line solution is
sage: ZZ['x']([coeff.lift_centered() for coeff in aa.lift()])
-3*x^4 + 2*x^3 + x^2 + 3*x - 2
Not very elegant but it does the job.Tue, 21 Jan 2020 22:23:54 +0100https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/?answer=49630#post-id-49630Comment by rburing for <p>Be careful that your lifted polynomial is <strong>not</strong> a polynomial in ZZ but in GF(q). You can check with</p>
<pre><code>sage: aa.lift().parent()
Univariate Polynomial Ring in x over Finite Field of size 7
</code></pre>
<p>What you actually want is the "centered lift of this lift". A one line solution is</p>
<pre><code>sage: ZZ['x']([coeff.lift_centered() for coeff in aa.lift()])
-3*x^4 + 2*x^3 + x^2 + 3*x - 2
</code></pre>
<p>Not very elegant but it does the job.</p>
https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/?comment=49633#post-id-49633Alternative: `aa.lift().map_coefficients(lambda c: c.lift_centered(), ZZ)`.Tue, 21 Jan 2020 22:33:20 +0100https://ask.sagemath.org/question/49613/center-lift-of-a-polynomial/?comment=49633#post-id-49633