In the quadratic sieve algorithm, the idea is to find $a$ and $a$ such that $a^2 \equiv b^2 \bmod n$. We need that $a\not\equiv \pm b \bmod n$. However, there the $c$ is not necessarily $1$. $\gcd(b \pm c,n)$ returns non-trivial factors.

However, in Shor's algorithm, we specifically need to find square roots of $1$ (in modulo $n$) i.e. we look for $a$ such that $a^2 \equiv 1 \bmod n$. That is, $b$ is specifically $1$. Why is this choice necessary?

Related: Math SE: Chinese Remainder Theorem: four square roots of 1 modulo N


1 Answer 1


The two problems are equivalent.

If you give me a pair $a, b$ such that $a^2 = b^2$ with $a \neq \pm b$ then $c = a b^{-1}$ satisfies $c \neq \pm 1$ and $c^2 = 1$.

If you give me a $c$ such that $c^2 = 1$ and $c \neq \pm 1$, and some target value $a$, then $b = a \cdot c$ satisfies $a^2 = b^2$ and $a \neq \pm b$.

You can derive a square root of 1 from an $a,b$ pair. You can derive an $a,b$ pair with desired $a$ from a square root of 1. They're reducible to each other.


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.