Why do we search for square roots of 1 in Shor's algorithm unlike the quadratic sieve?

Question

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

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.