<p>Inverses modulo <span class="math-container">$2^n$</span> (for <span class="math-container">$n$</span> given in unary) can be computed in NC—more precisely, uniform <span class="math-container">$\mathrm{TC}^0$</span>—by lifting (trivially computable) inverses modulo <span class="math-container">$2$</span>: given the inverse <span class="math-container">$Y$</span> of <span class="math-container">$X$</span> modulo <span class="math-container">$M_0$</span> (here <span class="math-container">$2$</span>), you can compute the inverse of <span class="math-container">$X$</span> modulo <span class="math-container">$M=M_0^n$</span> in <span class="math-container">$\mathrm{TC}^0$</span> by writing <span class="math-container">$XY=1-M_0Z$</span> and using the fact <span class="math-container">$(1-M_0Z)^{-1}\equiv\sum_{i=0}^{n-1}(M_0Z)^i\pmod M$</span>.</p>
<p>More generally, given coprime <span class="math-container">$X$</span> and <span class="math-container">$M$</span> in binary and <span class="math-container">$b$</span> in unary, we can compute <span class="math-container">$X^{-1}$</span> modulo <span class="math-container">$M$</span> in uniform <span class="math-container">$\mathrm{TC}^0$</span> if <span class="math-container">$M$</span> is <span class="math-container">$b$</span>-smooth (i.e., all prime factors of <span class="math-container">$M$</span> are at most <span class="math-container">$b$</span>): for each prime <span class="math-container">$p\le b$</span> in parallel, compute the exponent <span class="math-container">$v_p(M)$</span> of <span class="math-container">$p$</span> in the prime factorization of <span class="math-container">$M$</span>, the inverse of <span class="math-container">$X$</span> modulo <span class="math-container">$p$</span> by brute-force selection, and then the inverse <span class="math-container">$Y_p$</span> of <span class="math-container">$X$</span> modulo <span class="math-container">$M_p=p^{v_p(M)}$</span> using the lifting as above. Then combine the <span class="math-container">$Y_p$</span>’s to an inverse <span class="math-container">$Y$</span> of <span class="math-container">$X$</span> modulo <span class="math-container">$M$</span> using the Chinese remainder theorem: <span class="math-container">$Y=\sum_pY_pZ_p\prod_{q\ne p}M_q$</span>, where <span class="math-container">$Z_p$</span> is the inverse of <span class="math-container">$\prod_{q\ne p}M_q$</span> modulo <span class="math-container">$M_p$</span>. The sums and products can be computed in <span class="math-container">$\mathrm{TC}^0$</span>, and <span class="math-container">$Z_p$</span> can be computed in <span class="math-container">$\mathrm{TC}^0$</span> in the same way as <span class="math-container">$Y_p$</span>.</p>

CC BY-SA 4.0
2023-05-08T23:11:25.930Z
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$?
Turbo
CC BY-SA 4.0
2023-05-09T06:19:14.367Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2023-05-08T21:17:53.403Z
2023-05-09T08:47:31.487Z
2023-05-09T08:47:31.487Z
Emil Jeřábek
<p>Modular inverse is not known to be in <span class="math-container">$NC$</span> either.</p>
<p>How about the cases where the modulus is just <span class="math-container">$2^n +i$</span> where <span class="math-container">$i\in\{-1,0,1\}$</span>?</p>
<p>Are these cases in <span class="math-container">$NC$</span>?</p>
<p>Are there any non-trivial classes of moduli where the problem is in <span class="math-container">$NC$</span>?</p>

<ds.algorithms><parallel>
On parallel complexity of modular inverse
Turbo
# On parallel complexity of modular inverse

(Asked by: username_0 on 2022-12-25)

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

**Tags:** ds.algorithms, parallel

---

## 1 answers

### Answer by username_1 on 2023-05-08. Score: 4 | Accepted 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$.

> **Comments:**
> **username_0**: 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$?  
> **username_1**: 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$.  

---

