Academy K

Period Finding and Factoring

HardConceptualShor's algorithmperiod findingnumber theory

Related module: Fourier transform, phase estimation and factoring

Problem statement

Shor's factoring algorithm reduces factoring to period finding. For N=pqN = pq (product of two primes), we pick random a<Na < N with gcd⁡(a,N)=1\gcd(a, N) = 1 and find the period rr such that ar≡1(modN)a^r \equiv 1 \pmod{N}.

  1. If rr is even and ar/2≢−1(modN)a^{r/2} \not\equiv -1 \pmod{N}, how do we extract a factor of NN?
  2. What is the probability that a random aa yields a usable period?
  3. For N=15N = 15 and a=7a = 7, find rr and the factors.

Hints

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.