Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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

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 + 5

5

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

Thanks! Susan