<p>Square roots modulo <span class="math-container">$2^n$</span> can be computed in (uniform) <span class="math-container">$\mathrm{TC}^0$</span>. More generally, just like in <a href="https://cstheory.stackexchange.com/questions/52308/on-parallel-complexity-of-modular-inverse/52820#52820">On parallel complexity of modular inverse</a>, given <span class="math-container">$X$</span> and <span class="math-container">$M$</span> in binary and <span class="math-container">$b$</span> in unary such that <span class="math-container">$M$</span> is <span class="math-container">$b$</span>-smooth, you can compute in <span class="math-container">$\mathrm{TC}^0$</span> a square root <span class="math-container">$Y^2\equiv X\pmod M$</span> if it exists.</p>
<p>The general set-up is the same as in the linked answer for inverses (factorize <span class="math-container">$M$</span>, compute square roots modulo each prime power factor, combine them using the Chinese remainder theorem). The only difference is in the computation of <span class="math-container">$Y=\sqrt X$</span> modulo <span class="math-container">$p^n$</span> when a prime <span class="math-container">$p$</span> and <span class="math-container">$n$</span> are given in unary, which is done as follows:</p>
<ul>
<li><p>If <span class="math-container">$X\equiv0\pmod{p^n}$</span>, take <span class="math-container">$Y=0$</span>.</p>
</li>
<li><p>Otherwise, write <span class="math-container">$X=p^kX'$</span> with <span class="math-container">$k&lt;n$</span> and <span class="math-container">$X'\not\equiv0\pmod p$</span>. If <span class="math-container">$k$</span> is odd, no square root exists. Otherwise, we can take <span class="math-container">$Y=p^{k/2}Y'$</span>, where <span class="math-container">$Y'^2\equiv X'\pmod{p^{n-k}}$</span>. Hence we may assume without loss of generality that <span class="math-container">$X\not\equiv0\pmod p$</span>.</p>
</li>
<li><p>For <span class="math-container">$p$</span> odd: if <span class="math-container">$X$</span> has no square root modulo <span class="math-container">$p$</span>, it has no modulo <span class="math-container">$p^n$</span>. Otherwise, find <span class="math-container">$y$</span> such that <span class="math-container">$y^2\equiv X\pmod p$</span> by brute-force selection. Then <span class="math-container">$y^{-2}X\equiv1\pmod p$</span>, thus using <span class="math-container">$y^{-1},4^{-1}\bmod{p^n}$</span> (that we can compute as in the linked answer), we can compute <span class="math-container">$Z\equiv0\pmod p$</span> such that <span class="math-container">$X\equiv y^2(1-4Z)\pmod{p^n}$</span>.</p>
<p>For <span class="math-container">$p=2$</span>: the cases <span class="math-container">$n=1,2$</span> are left to the reader. If <span class="math-container">$n\ge3$</span>, there exists no square root unless <span class="math-container">$X\equiv1\pmod8$</span>; putting <span class="math-container">$y=1$</span> and <span class="math-container">$Z=(1-X)/4$</span>, we again have <span class="math-container">$X\equiv y^2(1-4Z)\pmod{p^n}$</span> and <span class="math-container">$Z\equiv0\pmod p$</span>.</p>
</li>
<li><p>It remains to compute <span class="math-container">$\sqrt{1-4Z}$</span> modulo <span class="math-container">$p^n$</span> for <span class="math-container">$Z\equiv0\pmod p$</span>: we do this by evaluating the sum
<span class="math-container">$$1-2\sum_{k=0}^{n-2}C_kZ^{k+1},$$</span>
where <span class="math-container">$C_k=\frac{(2k)!}{k!(k+1)!}$</span> are the Catalan numbers. This can be done in <span class="math-container">$\mathrm{TC}^0$</span> using iterated sums and products.</p>
</li>
</ul>
<p>The reason the last step works is that for <span class="math-container">$Z\equiv0\pmod p$</span>, the infinite series
<span class="math-container">$$1-2\sum_{k=0}^\infty C_kZ^{k+1}$$</span>
converges in the ring <span class="math-container">$\mathbb Z_p$</span> of <span class="math-container">$p$</span>-adic integers, and since the square of the corresponding formal power series in <span class="math-container">$\mathbb Z[[T]]\subseteq\mathbb Z_p[[T]]$</span> is <span class="math-container">$1-4T$</span>, it computes a square root of <span class="math-container">$1-4Z$</span> in <span class="math-container">$\mathbb Z_p$</span>. Reducing this series modulo <span class="math-container">$p^n$</span>, all the <span class="math-container">$Z^{k+1}$</span> terms with <span class="math-container">$k\ge n-1$</span> vanish, and the remaining finite sum computes a square root modulo <span class="math-container">$p^n$</span>.</p>

CC BY-SA 4.0
2023-07-07T19:51:38.200Z
"For p odd: if X has no square root modulo p".. this checking is not in NC.. correct?
Turbo
CC BY-SA 4.0
2023-07-07T20:53:17.653Z
$p$ is logarithmically small, that’s the whole point of the smoothness assumption. You try all $y<p$ in parallel, and see if any of them is a square root of $X$ modulo $p$ in $\mathrm{AC}^0$.
Emil Jeřábek
CC BY-SA 4.0
2023-07-07T11:01:32.413Z
2023-07-07T11:01:32.413Z
Emil Jeřábek
<p>Assume modulus is prime. Is modular square roots then in <span class="math-container">$NC$</span>?</p>
<p>If not then, are there special primes or prime powers or numbers related to these (such as <span class="math-container">$2^k\pm i$</span> where <span class="math-container">$i\in\{-1,0,+1\}$</span>) where it is in <span class="math-container">$NC$</span>?</p>

CC BY-SA 4.0
2023-07-06T20:12:04.977Z
Well you can compute square roots modulo $2^n$ by Hensel’s lifting; this is in NC as $O(\log n)$ iterations are enough. More generally, you can do it modulo a $b$-smooth modulus with $b$ a parameter given in unary, just as in https://cstheory.stackexchange.com/a/52820 (compute the prime factorization of the modulus, compute square roots modulo each prime by brute force selection, lift them to square roots modulo the prime power factors using Hensel’s lifting, and combine these by the Chinese remainder theorem).
Emil Jeřábek
CC BY-SA 4.0
2023-07-06T20:13:44.903Z
@EmilJeřábek The procedure in the link was for inverse. Can you describe the computations for roots? Do you expect it to be in $TC^0$?
Turbo
CC BY-SA 4.0
2023-07-06T20:15:26.497Z
I just described it.
Emil Jeřábek
CC BY-SA 4.0
2023-07-06T20:22:43.437Z
It might actually be in $\mathrm{TC}^0$, using a power series instead of Hensel’s lifting. The usual power series for $\sqrt{1+x}$ with Catalan number coefficients converges in the $p$-adics when $x$ is a multiple of $p$ (or of $8$, in case of $p=2$). So then the computation is virtually identical to https://cstheory.stackexchange.com/a/52820 , only using the $\sqrt{1+x}$ series in place of the series $(1+x)^{-1}=\sum_i(-x)^i$.
Emil Jeřábek
CC BY-SA 4.0
2023-07-07T01:17:00.667Z
@EmilJeřábek I thought Hensel lifting goes digit by digit and so needs O(n) iterations?
Turbo
CC BY-SA 4.0
2023-07-07T09:28:27.303Z
No, Hensel’s lifting (for polynomial roots) is essentially Newton’s iteration in the $p$-adic ring, and thus it doubles the precision when done properly. See https://en.wikipedia.org/wiki/Hensel%27s_lemma#Quadratic_lifting (in a rather more complicated setup where it is used for polynomial factoring). In the special case of square roots: if $x^2\equiv a\pmod{p^k}$, where $a\not\equiv0\pmod p$ and $p$ is an odd prime, then $y=2^{-1}(x+ax^{-1})\pmod{p^{2k}}$ satisfies $y^2\equiv a\pmod{p^{2k}}$. With a bit more care, one can get away with inverses modulo $p^k$ rather than $p^{2k}$: ...
Emil Jeřábek
CC BY-SA 4.0
2023-07-07T09:36:06.283Z
... let $w=(2x)^{-1}\pmod{p^k}$ and $y=x-(x^2-a)w$ (not modulo anything); then again $y^2\equiv a\pmod{p^{2k}}$. The even case is a bit more messy: if $a$ is odd and $x^2\equiv a\pmod{2^{k+2}}$, then $z=x+ax^{-1}\pmod{2^{2k+4}}$ is even, and $y=z/2$ satisfies $y^2\equiv a\pmod{2^{2k+2}}$. The more sophisticated version with inverses mod $2^k$ is: let $w=x^{-1}\pmod{2^k}$ and $y=x-\frac{x^2-a}2w$ (not modulo), using the fact that $x^2-a$ is even. Then $y^2\equiv a\pmod{2^{2k+2}}$.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><dc.parallel-comp><nt.number-theory><comp-number-theory>
Is modular square roots modulo primes in $NC$?
Turbo
# Is modular square roots modulo primes in $NC$?

(Asked by: username_0 on 2023-01-01)

Assume modulus is prime. Is modular square roots then in $NC$?

If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it is in $NC$?

**Tags:** cc.complexity-theory, complexity-classes, dc.parallel-comp, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: Well you can compute square roots modulo $2^n$ by Hensel’s lifting; this is in NC as $O(\log n)$ iterations are enough. More generally, you can do it modulo a $b$-smooth modulus with $b$ a parameter given in unary, just as in https://cstheory.stackexchange.com/a/52820 (compute the prime factorization of the modulus, compute square roots modulo each prime by brute force selection, lift them to square roots modulo the prime power factors using Hensel’s lifting, and combine these by the Chinese remainder theorem).  
> **username_0**: @EmilJeřábek The procedure in the link was for inverse. Can you describe the computations for roots? Do you expect it to be in $TC^0$?  
> **username_1**: I just described it.  
> **username_1**: It might actually be in $\mathrm{TC}^0$, using a power series instead of Hensel’s lifting. The usual power series for $\sqrt{1+x}$ with Catalan number coefficients converges in the $p$-adics when $x$ is a multiple of $p$ (or of $8$, in case of $p=2$). So then the computation is virtually identical to https://cstheory.stackexchange.com/a/52820 , only using the $\sqrt{1+x}$ series in place of the series $(1+x)^{-1}=\sum_i(-x)^i$.  
> **username_0**: @EmilJeřábek I thought Hensel lifting goes digit by digit and so needs O(n) iterations?  
> **username_1**: No, Hensel’s lifting (for polynomial roots) is essentially Newton’s iteration in the $p$-adic ring, and thus it doubles the precision when done properly. See https://en.wikipedia.org/wiki/Hensel%27s_lemma#Quadratic_lifting (in a rather more complicated setup where it is used for polynomial factoring). In the special case of square roots: if $x^2\equiv a\pmod{p^k}$, where $a\not\equiv0\pmod p$ and $p$ is an odd prime, then $y=2^{-1}(x+ax^{-1})\pmod{p^{2k}}$ satisfies $y^2\equiv a\pmod{p^{2k}}$. With a bit more care, one can get away with inverses modulo $p^k$ rather than $p^{2k}$: ...  
> **username_1**: ... let $w=(2x)^{-1}\pmod{p^k}$ and $y=x-(x^2-a)w$ (not modulo anything); then again $y^2\equiv a\pmod{p^{2k}}$. The even case is a bit more messy: if $a$ is odd and $x^2\equiv a\pmod{2^{k+2}}$, then $z=x+ax^{-1}\pmod{2^{2k+4}}$ is even, and $y=z/2$ satisfies $y^2\equiv a\pmod{2^{2k+2}}$. The more sophisticated version with inverses mod $2^k$ is: let $w=x^{-1}\pmod{2^k}$ and $y=x-\frac{x^2-a}2w$ (not modulo), using the fact that $x^2-a$ is even. Then $y^2\equiv a\pmod{2^{2k+2}}$.  

---

## 1 answers

### Answer by username_1 on 2023-07-07. Score: 1 | Accepted answer

Square roots modulo $2^n$ can be computed in (uniform) $\mathrm{TC}^0$. More generally, just like in [On parallel complexity of modular inverse](https://cstheory.stackexchange.com/questions/52308/on-parallel-complexity-of-modular-inverse/52820#52820), given $X$ and $M$ in binary and $b$ in unary such that $M$ is $b$-smooth, you can compute in $\mathrm{TC}^0$ a square root $Y^2\equiv X\pmod M$ if it exists.

The general set-up is the same as in the linked answer for inverses (factorize $M$, compute square roots modulo each prime power factor, combine them using the Chinese remainder theorem). The only difference is in the computation of $Y=\sqrt X$ modulo $p^n$ when a prime $p$ and $n$ are given in unary, which is done as follows:

* If $X\equiv0\pmod{p^n}$, take $Y=0$.
* Otherwise, write $X=p^kX'$ with $k and $X'\not\equiv0\pmod p$. If $k$ is odd, no square root exists. Otherwise, we can take $Y=p^{k/2}Y'$, where $Y'^2\equiv X'\pmod{p^{n-k}}$. Hence we may assume without loss of generality that $X\not\equiv0\pmod p$.
* For $p$ odd: if $X$ has no square root modulo $p$, it has no modulo $p^n$. Otherwise, find $y$ such that $y^2\equiv X\pmod p$ by brute-force selection. Then $y^{-2}X\equiv1\pmod p$, thus using $y^{-1},4^{-1}\bmod{p^n}$ (that we can compute as in the linked answer), we can compute $Z\equiv0\pmod p$ such that $X\equiv y^2(1-4Z)\pmod{p^n}$.

  For $p=2$: the cases $n=1,2$ are left to the reader. If $n\ge3$, there exists no square root unless $X\equiv1\pmod8$; putting $y=1$ and $Z=(1-X)/4$, we again have $X\equiv y^2(1-4Z)\pmod{p^n}$ and $Z\equiv0\pmod p$.
* It remains to compute $\sqrt{1-4Z}$ modulo $p^n$ for $Z\equiv0\pmod p$: we do this by evaluating the sum
  $$1-2\sum\_{k=0}^{n-2}C\_kZ^{k+1},$$
  where $C\_k=\frac{(2k)!}{k!(k+1)!}$ are the Catalan numbers. This can be done in $\mathrm{TC}^0$ using iterated sums and products.

The reason the last step works is that for $Z\equiv0\pmod p$, the infinite series
$$1-2\sum\_{k=0}^\infty C\_kZ^{k+1}$$
converges in the ring $\mathbb Z\_p$ of $p$-adic integers, and since the square of the corresponding formal power series in $\mathbb Z[[T]]\subseteq\mathbb Z\_p[[T]]$ is $1-4T$, it computes a square root of $1-4Z$ in $\mathbb Z\_p$. Reducing this series modulo $p^n$, all the $Z^{k+1}$ terms with $k\ge n-1$ vanish, and the remaining finite sum computes a square root modulo $p^n$.

> **Comments:**
> **username_0**: "For p odd: if X has no square root modulo p".. this checking is not in NC.. correct?  
> **username_1**: $p$ is logarithmically small, that’s the whole point of the smoothness assumption. You try all $y<p$ in parallel, and see if any of them is a square root of $X$ modulo $p$ in $\mathrm{AC}^0$.  

---

