1

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

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112

1 Answers1

2

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.

Craig Gidney
  • 44,299
  • 1
  • 41
  • 116