Implementing NTRU (truncated polynomials)

[kirtsar]

I've tried to implement something in the spirit on NTRU. In this cryptosystem we are interested in the rings of the form Zq[X]/(X^N - 1).

1. The first thing that is strange to me is that it is impossible to construct Z[X] / (X^N - 1), only QQ is allowed.

2. Given Z[X] / (X^N - 1), it seems impossible to take it "modulo q", which means take any f in this ring and reduce its coefficients modulo q. Instead one have to start with Zq[X], and then take the factor ring Zq[X]/(X^N - 1)

3. Given element f of Rq = Zq[X] / (X^N - 1), it seems impossible to obtains its inverse in Rq due to the fact that q may not be prime.

For example, take

q = 16
Zq = ResidueRing(ZZ, q)
ZX, x = Zq["X"]
Rq = ResidueRing(ZX, x^5 - 1)
f1 = Rq(3x^4 + 10x^3 + 7x^2 - 1)
f2 = Rq(5x^4 + 3x^3 + 13x^2 + 8x + 14)
@show f1 * f2     # equals 1
inv(f1)           # impossible