3
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ 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 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). $\endgroup$ Jul 6, 2023 at 20:12
  • $\begingroup$ @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$? $\endgroup$
    – Turbo
    Jul 6, 2023 at 20:13
  • 1
    $\begingroup$ 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 cstheory.stackexchange.com/a/52820 , only using the $\sqrt{1+x}$ series in place of the series $(1+x)^{-1}=\sum_i(-x)^i$. $\endgroup$ Jul 6, 2023 at 20:22
  • 1
    $\begingroup$ 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 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}$: ... $\endgroup$ Jul 7, 2023 at 9:28
  • 1
    $\begingroup$ ... 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}}$. $\endgroup$ Jul 7, 2023 at 9:36

1 Answer 1

1
$\begingroup$

Square roots modulo $2^n$ can be computed in (uniform) $\mathrm{TC}^0$. More generally, just like in On parallel complexity of modular inverse, 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<n$ 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$.

$\endgroup$
2
  • $\begingroup$ "For p odd: if X has no square root modulo p".. this checking is not in NC.. correct? $\endgroup$
    – Turbo
    Jul 7, 2023 at 19:51
  • 1
    $\begingroup$ $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$. $\endgroup$ Jul 7, 2023 at 20:53

Your Answer

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