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$?


1 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$.

  • $\begingroup$ So is computing inverse modulo $2^n$ in $TC^0$ up to $n=O((\log\log(T))^c)$ at any fixed $c>0$ where $T$ is a parameter such that $|X|<T$ holds? Or at least in $NC^1$ or in $L$? $\endgroup$
    – Turbo
    May 8 at 23:11
  • $\begingroup$ The input is $X$ and $M$ in binary (where $X$ is coprime to $M$), the output is $X^{-1}$ modulo $M$ in binary. This can be computed in $\mathrm{TC}^0$ under the promise that $M$ is a power of $2$, or more generally, that it is smooth, as stated in the answer. So the $n$ in $2^n$ is not bounded by any parameter of $X$; it works modulo any $2^n$ given as input in binary (or equivalently, for any $n$ given in unary). As far as determination of the size of the input is concerned, the main input is $M$ rather than $X$; you might as well assume $0\le X<M$. $\endgroup$ May 9 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.