# 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! Susan

edit retag close merge delete

Sort by » oldest newest most voted

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

more

Alternative: aa.lift().map_coefficients(lambda c: c.lift_centered(), ZZ).