NTRUEncrypt - Choose the initial random polynomial I'm trying to implement NTRUEncrypt but encounter some problems. I've finished all the basic functions that are needed for the scheme base on this Document, but I can't find an algorithm to check the validity of the initial polynomial f.

If f is not qualified (inverse mod p or inverse mod q doesn't exist) then the function to calculate the inverse modulo would end up in an infinite loop.

I've found some documentation about ntru con the ntru's website but there are too many of them and I don't have the time to go through them all. If anyone can help me with the algorithm or point out the document that I should read, that'd be helpful.
So long the GCD of f(1) with p and with q is 1, f will have an inverse with high probability. (f(1) = f evaluated at 1, i.e. the sum of the coefficients of f).

If you take f to be binary with df 1s, then take df to be relatively prime to p and q.

If you take f to be trinary and it has df 1s and df-1 -1s, then f(1) = 1 and this will satisfy the GCD requirement identically.

If you take f to be of form 1 + pF, f(1) is 1 mod p and satisfies that requirement identically. For the GCD requirement mod q, either pick F to be trinary with equal +1s and -1s (so f(1) = 1) or pick F to be binary such that 1 + p*F(1) is relatively prime to q.

"High probability" above means that the probability of not having an inverse goes down rapidly as both q and N increase. I've posted toy examples on Stack Overflow (http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key) and when I generated them I came up with invertible keys on the first attempt for N = 11, q = 29.