An Improvement and a New Design of Algorithms for Seeking the Inverse of an NTRU Polynomial

摘要

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 A* 1. 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.