Understanding the Hidden Subgroup Problem specific to Integer Factorization

Question

I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden subgroup problem on cryptography? but it doesn't cover the specifics I am having trouble putting together.

To define the HSP:

Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow X$ separates cosets of $H$ if for all $g_1, g_2 \in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$.

Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \Rightarrow X$ a function such that there exists a subgroup $H \leq G$ for which $f$ separates cosets of $H$. The function $f$ is given via an oracle. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

What I can't figure out is how to reduce the integer factorization problem to an HSP problem, and then why the (abelian) HSP problem is not solvable in polynomial time without a quantum computer using e.g. Shor's algorithm.

Answer 1

Let $\mathbb{Z}, +$ be the group integers, $\mathbb{Z}/n\mathbb{Z}, \times$ the multiplicative group of integers modulo $n$, and $\varphi(n)$ its order. Then $\varphi(n)\mathbb{Z}, +$, the additive group of multiples of $\varphi(n)$ is a subgroup of $\mathbb{Z}$. The function $f : \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z} : x \mapsto a^x \mod n$ for fixed $a \in \mathbb{Z}/n\mathbb{Z}$ satisfies the description of the HSP oracle for the subgroup $H=\varphi(n)\mathbb{Z}$ of $\mathbb{Z}$ because

$\phantom{\Leftrightarrow} \forall \, x, y \in \mathbb{Z} \, . \, f(x) = f(y) \\ \Leftrightarrow x = y \mod \varphi(n) \\ \Leftrightarrow x = y + k\varphi(n) \quad \mathit{for \, some} \quad k \in \mathbb{Z} \\ \Leftrightarrow x = y + H$

Consequently, the formulation of the factorization problem is to find a generator of the group $\varphi(n)\mathbb{Z} \subset \mathbb{Z}$ given access to the function $f$ that computes exponentiation modulo $n$. Once you have this generator, $\varphi(n)$, computing the factorization of $n$ is easy using some straightforward (classical) number theory.