NTRU inverse polynomial algorithm based on the LU decomposition method of matrix inversion
Juliet N. Gaithuru, Mazleena Salleh, Ismail Mohamad · 2017
Inverses in NthDegree Truncated Polynomial Ring (NTRU) are computed using an adaptation of the Almost Inverse Algorithm, defined in the field of polynomials with binary and ternary coefficients. This research seeks to solve the problem of finding modular polynomial inverses in NTRU for polynomials in a convolution ring and whose coefficients lie in other fields beyond binary and ternary fields. An inverse polynomial algorithm is proposed, which uses LU decomposition to find an inverse matrix inverse. The proposed algorithm is then compared with other NTRU inverse algorithms in terms of the speed of inversion, computational complexity and parameter selection. The algorithm allows for the use of a non-prime modulus, has a higher probability of finding a modular polynomial inverse for the NTRU key generation process and is ideally applicable to modular polynomial inversion for NTRU polynomials with coefficients in varied fields.