Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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/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.

I formalized this to

Input: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.

Output: $p$ or $q$

  1. Take a random number $r$ between $1$ and $n-1$
  2. If $r\mid n$ then return $r$ (we were lucky)
  3. $s:= r^2\pmod{n}$
  4. $t:=\sqrt{s}\pmod{n}$ (using the oracle)
  5. If $t\equiv \pm r\pmod{n}$ then goto step 1.
  6. Return $\gcd(t-r,n)$

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

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:

  1. 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 ;-).
  2. Are there any more details I have consider?
  3. Has every square of a square exactly $4$ square roots modulo $n$?
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted
  1. 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.
  2. Try to prove that your algorithm works, and see if anything is missing.
  3. 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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.