investigate junk data for N=11, p=3, q=32

[hasufell]

Some encrypted polynomials don't recover properly with the following setup. Could be related to poly_starmultiply().

N = 11, p = 3, q = 32
f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10
g = -1 + x^2 + x^3 + x^5 - x^8 - x^10

random polynomial for encryption:
-1 + x^2 + x^3 + x^4 - x^5 - x^7

polynomial to encrypt:
1 - x - x^2 + x^3 + x^4 - x^5 - x^6 + x^7 - x^8 - x^9 + x^10

encrypted polynomial:
16 + 10 * x + 25 * x^2 + 24 * x^3 + 16 * x^4 + 15 * x^5 + 29 * x^6 + 8 * x^7 + 25 * x^8 + 4 * x^9 + 19 * x^10

decrypted polynomial (malformed!):
-x^2 - x^4 - x^5 - x^7 + x^8 - x^9 - x^10

[hasufell]

This seems to only happen if the polynomial f for the private key is of degree N - 1. If it is less, then it does not happen.

[hasufell]

The problem is the following:
Random polynomials for encryption need to hold the following condition in order for the probability of unrecoverable messages to be less than e.g. 2^-80:
q > (6 * d + 1) * p
where d is the amount of -1 and 1 in the random polynomial.

This suggests that the wikipedia article needs a fix.

Reference to the condition above is here: http://www.math.uni-hamburg.de/home/kuehn/moldenhauer-bsc-NTRUKryptosystem-final.pdf

[hasufell]

http://teal.gmu.edu/courses/ECE646/project/reports_2001/dsouza.pdf

[hasufell]

best we can do is to provide checks for the parameters