Revision history [back]

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 + 3x - 6x^2 + 2x^3 + 4x^4 aa = Q(a) aa.lift() 4x^4 + 2x^3 + x^2 + 3*x + 5

​Any thoughts? I guess I could write my own function to do the center lifting...

Thanks! Susan

 2 None vdelecroix 7357 ●17 ●81 ●163 http://www.labri.fr/pe...

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 + 3x 3*x - 6x^2 6*x^2 + 2x^3 2*x^3 + 4x^4
4*x^4
aa = Q(a)
aa.lift()
4x^4 4*x^4 + 2x^3 2*x^3 + x^2 + 3*x + 55


​Any thoughts? I guess I could write my own function to do the center lifting...

Thanks! Susan