center lift of a polynomial?

asked 2020-01-21 01:55:52 +0100

updated 2020-01-21 22:20:02 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

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 flag offensive close merge delete

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2020-01-21 22:23:54 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

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.

edit flag offensive delete link

Comments

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

rburing ( 2020-01-21 22:33:20 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-01-21 01:55:52 +0100

Seen: 1,272 times

Last updated: Jan 21 '20

center lift of a polynomial? edit