NTRU inverse polynomial algorithm based on circulant matrices using gauss-jordan elimination
Gaithuru Juliet Nyokabi, Mazleena Salleh, Ismail Mohamad · 2017
Inverses in the 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 study solves the problem of finding inverses using an elaborate algorithm which is extensible to polynomials with coefficients in varied fields, other than binary and ternary fields. An inverse algorithm based on circulant matrices using the Gauss-Jordan method of matrix inversion is proposed, showing the algorithm's comparative performance. In comparison to the inverse algorithm by Zhao and Su, the proposed inverse algorithm shows equivalent computational complexity of O(N2), but has faster inversion by a factor ranging from 12:1 to 37:1 though it is slower than the classical NTRU inverse algorithm.