On parallel complexity of modular inverse

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

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

• 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$? May 8 at 23:11
• 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$. May 9 at 6:19