Problem Detail: 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$. I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $left.mathbb{Z}middle/nmathbb{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. I formalized this to Input: $n=pqinmathbb{Z}$ with primes $p$ and $q$. Output: $p$ or $q$
- Take a random number $r$ between $1$ and $n-1$
- If $rmid n$ then return $r$ (we were lucky)
- $s:= r^2pmod{n}$
- $t:=sqrt{s}pmod{n}$ (using the oracle)
- If $tequiv pm rpmod{n}$ then goto step 1.
- Return $gcd(t-r,n)$
One can show that $t notequiv pm rpmod{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$. 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:
- 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 ;-).
- Are there any more details I have consider?
- Has every square of a square exactly $4$ square roots modulo $n$?
Asked By : born
Answered By : Yuval Filmus
- 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.
- Try to prove that your algorithm works, and see if anything is missing.
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9106
