Newton iterative algorithm for polynomial modular inversion modulo xn±1 for some patterns of n

Abstract

This thesis presents an algorithm for computing the modular inverse of a polynomial in a ring of polynomials over a finite field $\mathbb{F}_q$ with a characteristic $p$. Given a polynomial $f$ and a natural number $r$, by applying the idea of the Newton iteration algorithm, the fast division algorithm used to find the inverse of $f$ under modulo $x^{p^r}-1$, $x^{p^r}+1$, $x^{2p^r}-1$ and $x^n-1$ where $n=2^r d$ for some $r,d\in\mathbb{N}$, is established. The cost analysis for these cases show that the algorithm has the computational complexity of $\mathcal{O}(n \log n)$ which is more efficient than the Half-GCD algorithm in terms of computational complexity for large $n$.