Timeline for Finding the square root modulo n, when the factors of n are known
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 27, 2012 at 15:21 | vote | accept | Craig Feinstein | ||
| Feb 24, 2011 at 11:05 | comment | added | Emil Jeřábek | @David: Efficient algorithms for square roots are only known for $n$ prime (or prime power). The case of composite $n$ is unlikely to be NP-complete (as it is in NP $\cap$ coNP), but it is probabilistic polynomial-time Turing-equivalent to factoring, hence it is assumed to have no efficient algorithm. | |
| Feb 9, 2011 at 23:48 | answer | added | Craig Feinstein | timeline score: 1 | |
| Feb 9, 2011 at 22:56 | comment | added | Gerry Myerson | So I guess what they are saying is that if you have integers $a_i$ and $b_i$, $i=1,\dots,t$, and you want to know whether $x\equiv a_i{\rm\ or\ }b_i\pmod{m_i}$, $i=1,\dots,t$ has a solution with $x$ in some given range (say, $0\le x\le\gamma$), no one knows a better way than using the Chinese Remainder Theorem $2^t$ times, once for each choice between an $a_i$ and a $b_i$. | |
| Feb 9, 2011 at 22:41 | comment | added | David Hansen | @Craig: It's that pesky specification "$0\leq x \leq \gamma$" which is inducing NP-completeness. | |
| Feb 9, 2011 at 22:39 | comment | added | David Hansen | Finding square roots mod $n$ is NOT NP-complete. There exist a host of efficient algorithms for finding $r$th roots (Cipolla, Tonelli, Adleman-Manders-Miller). | |
| Feb 9, 2011 at 22:37 | comment | added | Craig Feinstein | The name of the paper by Manders and Adelman is "NP-complete decision problems for quadratic polynomials". It says "The problem of accepting the set of quadratic congruences (in a standard encoding) $x^2= \alpha$ mod $\beta$ with solutions satisfying $0\leq x \leq \gamma$, $\alpha,\beta,\gamma \in \omega$ is NP-complete, even if the prime factorization of $\beta$ and all solutions to the congruence modulo all prime powers occurring in this factorization are given gratis." | |
| Feb 9, 2011 at 22:35 | comment | added | felix | Clearly, the CRT argument shows that if the factorization of $n$ is known, the running time to compute a square root modulo $n$ depends on the size of the largest prime divisor of $n$. Since $n$ can be prime, the complexity of finding square roots modulo $n$ with known factorization of $n$ is asymptotically the same as for finding square roots modulo primes. So if you can show (or if the paper you mention shows this) that finding square roots in $\IF_p$ is NP complete, then so is your problem of finding square roots with known factorization of the modulus. | |
| Feb 9, 2011 at 22:29 | comment | added | Peter Shor | There's nothing wrong with this general strategy. You can use the Chinese remainder theorem. What is the paper by Manders and Adelman, and is that really what it says? I vaguely remember a result that I believe says the problem of finding a square root of $\alpha$ modulo $n$ where the square root is between $0$ and $m$ is NP-complete. | |
| Feb 9, 2011 at 22:15 | history | asked | Craig Feinstein | CC BY-SA 2.5 |