The　NTRU　public　key　cryptosystem　is　constructed　over　a　polynomial　ring.　NTRU　is　involved　in　operations　of　polynomials　of　degree　N　-　1　having　integer　coefficients,　including　addition,　convolution,　modular　inverse　etc.　The　modular　inverse　operation　plays　an　important　role　in　NTRU　key　generation.　In　this　paper,　an　existent　algorithm　for　seeking　the　modular　inverse　of　an　NTRU　polynomial　is　improved,　which　makes　we　can　judge　by　gcd(det(A),　w)　=　1　whether　an　NTRU　polynomial　modulo　a　prime　or　2r　with　r　＞　1　has　the　inverse　or　not,　where　det(A)　is　the　determinant　of　an　N-cyclic　matrix　corresponding　to　the　coefficients　of　an　NTRU　polynomial,　and　w　is　a　modulus.　Besides,　a　new　algorithm　is　designed　which　is　based　on　a　congruence　equation　containing　N　variables.　Firstly,　we　compute　the　product　of　(det(A))-1　and　A1*.　Then,　the　inverse　of　an　NTRU　polynomial　equals　the　product　modulo　w.　The　advantage　of　the　new　algorithm　is　that　the　modulus　w　can　be　any　positive　integer　greater　than　1.　The　paper　analyzes　the　time　complexity　of　the　improved　algorithm　and　the　new　algorithm.　©　2011　IEEE.