= Uniform coprime state for a semiprime
{title2=$|\xi_N\rangle=\varphi(N)^{-1/2}\sum_{1\leq k<N,\ \gcd(k,N)=1}|k\rangle$}
For a <semiprime> $N=pq$ with distinct known primes, this <quantum state> is uniform over the reduced residue classes. With $n$ binary digits in $N$, its fraction among all $2^n$ computational labels is $a=(p-1)(q-1)/2^n\geq1/4$. An <ancilla qubit> whose one probability is $1/(4a)$ dilutes the joint good probability to exactly $1/4$. A reversible range-and-<greatest common divisor> predicate marks the good labels with <ancilla qubit> one, and a single <exact amplitude amplification> iteration produces $|\xi_N\rangle|1\rangle$. Known prime factors provide the cardinality; the membership test itself needs only $N$. Polynomial gate complexity presumes ideal one-qubit rotations at the specified amplitudes.
Back to article page
