4
$\begingroup$

A nontrivial square root of $N$ is a number $x$ such that $x^2 = 1\pmod{N}$ where $x$ isn't $1$ or $-1$.

Shor's algorithm consists of finding such a number in order to find a nontrivial factor of $N$. However, I haven't seen any proof of when it actually exists. For example if $N=10$ no such $x$ exists $\pmod{10}$.

What is a necessary and sufficient condition for the existence of the nontrivial square root of a number $N$?

$\endgroup$
2
  • 1
    $\begingroup$ Look up quadratic reciprocity. Or note that 10 is even and maybe has a pretty easy factor to find. $\endgroup$ Nov 12, 2023 at 12:51
  • $\begingroup$ Right thanks. But then in general given an N to factor Shor's algorithm might always fail right? There is no guarantee that N has a nontrivial square root in the first place. $\endgroup$
    – Omeglac
    Nov 12, 2023 at 12:57

2 Answers 2

10
$\begingroup$

Every number with at least two odd factors has non-trivial square roots. You get the non-trivial square roots by breaking them down into $\pm 1$ square roots for each factor and applying the Chinese remainder theorem.

Suppose $N$ is a semiprime with odd factors $a$ and $b$. By the Chinese remainder theorem you can find a value $r < N$ such that $r \equiv +1 \pmod{a}$ and $r \equiv -1 \pmod{b}$. For example, $r=2 \cdot b \cdot \text{ModularInverse}(b, a) - 1$.

Note $r^2 \bmod a = +1 = r^2 \bmod b$ and so $r^2 \bmod N = +1$. Therefore $r$ is a square root. It's a non-trivial square root because $r$ can't be $+1$ since that would violate $r \equiv -1 \pmod{b}$ and $r$ can't be $-1 \pmod{N}$ since that would violate $r \equiv +1 \pmod{a}$.

$\endgroup$
5
$\begingroup$

I like to think of Shor's algorithm as having a couple of trivial "gotchya's" - situations that, if true, cause the quantum part of the algorithm to output junk or otherwise fail. But, either the gotchya is easily tested and can be used to classically find a factor, or else the probability that the gotchya occurs is vanishingly small and the algorithm could be rerun with another random seed $a$.

  • A first one is that $N$, the number to be factored, needs to be odd. But if $N$ is not odd then we know that $2$ is a nontrivial factor!

  • A second one is that $N$ is not a prime power $p^s$. We have classical algorithms to check that $N$ is not such a prime power, and if it is, then we know that $p$ is a nontrivial factor.

  • A third one is that the test seed, $a$, need not share a common factor with $N$. Even Euclid's algorithm can be used to determine $\gcd(a,N)$, but if we happen to land on such an $a$ we could use that $a$ to classically factor $N$.

  • Still further, if we use the quantum algorithm and find that $a^r\equiv 1\bmod N$ but that $r$ is odd, then we can't calculate $\gcd(N,a^{r/2}+1)$. If this happens we can pick another $a$, but it can be shown that this only happens about half of the time and so it doesn't take long to find an $a$ having an odd $r$.

  • Lastly I guess $r$ could be found to be $1$ or $N$ itself, in which case we rerun with another $a$.

Someone described Shor's factoring algorithm as a whole bunch of classical number theory, with just a little quantum mechanics. The classical number theory is not super-difficult and only goes up to, say, Hardy and Wright, but I always forget a lot of the number-theoretical details as, to me, that small amount of quantum mechanics is where the sexy stuff happens.

It's also true that Shor first discovered his quantum algorithm for discrete logarithms over primes $p$ when $p-1$ is a smooth number - that algorithm is almost a direct port of Simon's algorithm over to a larger group and doesn't include much in the way of fancy-pants number theory.

$\endgroup$

Your Answer

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

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