On parallel complexity of modular inverse

Question

Modular inverse is not known to be in $NC$ either.

How about the cases where the modulus is just $2^n +i$ where $i\in\{-1,0,1\}$?

Are these cases in $NC$?

Are there any non-trivial classes of moduli where the problem is in $NC$?

Answer 1

Inverses modulo $2^n$ (for $n$ given in unary) can be computed in NC—more precisely, uniform $\mathrm{TC}^0$—by lifting (trivially computable) inverses modulo $2$: given the inverse $Y$ of $X$ modulo $M_0$ (here $2$), you can compute the inverse of $X$ modulo $M=M_0^n$ in $\mathrm{TC}^0$ by writing $XY=1-M_0Z$ and using the fact $(1-M_0Z)^{-1}\equiv\sum_{i=0}^{n-1}(M_0Z)^i\pmod M$.

More generally, given coprime $X$ and $M$ in binary and $b$ in unary, we can compute $X^{-1}$ modulo $M$ in uniform $\mathrm{TC}^0$ if $M$ is $b$-smooth (i.e., all prime factors of $M$ are at most $b$): for each prime $p\le b$ in parallel, compute the exponent $v_p(M)$ of $p$ in the prime factorization of $M$, the inverse of $X$ modulo $p$ by brute-force selection, and then the inverse $Y_p$ of $X$ modulo $M_p=p^{v_p(M)}$ using the lifting as above. Then combine the $Y_p$’s to an inverse $Y$ of $X$ modulo $M$ using the Chinese remainder theorem: $Y=\sum_pY_pZ_p\prod_{q\ne p}M_q$, where $Z_p$ is the inverse of $\prod_{q\ne p}M_q$ modulo $M_p$. The sums and products can be computed in $\mathrm{TC}^0$, and $Z_p$ can be computed in $\mathrm{TC}^0$ in the same way as $Y_p$.