Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-17T19:08:07Z https://cs.stackexchange.com/feeds/question/9106 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/9106 3 Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ born https://cs.stackexchange.com/users/2103 2013-01-23T09:39:28Z 2014-07-23T14:54:11Z <p>I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo $n$.</p> <p>I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $\left.\mathbb{Z}\middle/n\mathbb{Z}\right.$ and square it. If $r$ was a square, $r^2$ can have up to $4$ different square roots and the basic idea of the algorithm is that the oracle has some chance not to choose $\pm r$, but one of the other two roots. It will turn out that we then can determine a factor of $n$ using Euclidean's algorithm. </p> <p>I formalized this to</p> <p><strong>Input</strong>: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.</p> <p><strong>Output</strong>: $p$ or $q$</p> <ol> <li>Take a random number $r$ between $1$ and $n-1$</li> <li>If $r\mid n$ then return $r$ (we were lucky)</li> <li>$s:= r^2\pmod{n}$</li> <li>$t:=\sqrt{s}\pmod{n}$ (using the oracle)</li> <li>If $t\equiv \pm r\pmod{n}$ then goto step 1.</li> <li>Return $\gcd(t-r,n)$</li> </ol> <p>One can show that $t \not\equiv \pm r\pmod{n}$ implies that $\gcd(t-r,n)\neq 1,n$ and therefore get that the return value of the algorithm is a non-trivial factor of $n$. </p> <p>Inspired by my main question "How do I prove that the running time is polynomial in the bit-size of the input?" I have some follow up questions:</p> <ol> <li>Do I have to show that a lot of numbers between $1$ and $n-1$ are squares? There must be a well-known theorem or easy fact that shows this (well... not well-known to me ;-). </li> <li>Are there any more details I have consider? </li> <li>Has every square of a square exactly $4$ square roots modulo $n$? </li> </ol> https://cs.stackexchange.com/questions/9106/-/9114#9114 4 Answer by Yuval Filmus for Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ Yuval Filmus https://cs.stackexchange.com/users/683 2013-01-23T15:57:01Z 2013-01-23T15:57:01Z <ol> <li>Where in the analysis of the algorithm does the number of squares ("quadratic residues") come in? As to their number, you know that $a^2 \pmod{n}$ is always a square, and every number has up to $4$ square roots. That should help you show that there are a lot of squares.</li> <li>Try to prove that your algorithm works, and see if anything is missing.</li> <li>Suppose $n = pq$ ($p,q$ different primes) and $(x,n)=1$. Then if $x$ is a square, then $x$ has two square roots modulo $p$ and two square roots modulo $q$, and so four square roots in total by the Chinese remainder theorem. We know that a number $x$ such that $(x,p)=1$ has at most two square roots since the polynomial $t^2-x$ can have at most two roots modulo $p$. If it has one square root $y$ then $-y$ is another one.</li> </ol> https://cs.stackexchange.com/questions/9106/-/28665#28665 0 Answer by Cris for Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ Cris https://cs.stackexchange.com/users/20335 2014-07-23T14:54:11Z 2014-07-23T14:54:11Z <p>"2." Another detail to consider is that finding square roots modulo a large composite (your step 4) is proved to be as hard a factoring, and produces in any case a factorization of the large composite. See, for example, <a href="http://en.wikipedia.org/wiki/Rabin_cryptosystem" rel="nofollow">here</a> for an application of their equivalent difficulty, and <a href="http://cseweb.ucsd.edu/~bsy/rabin_func.html" rel="nofollow">here</a> for an explanation of how to factor the large composite if one <strong>can</strong> find square roots modulo the large composite.</p> <p>So it would seem you have found the algorithm correctly! And since all the steps, like computing (t-r,n), and aside from the magical oracle, are proven polynomial it seems you have constructed a proof as well!</p>