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 (product of two primes), we pick random with and find the period such that .
- If is even and , how do we extract a factor of ?
- What is the probability that a random yields a usable period?
- For and , find and the factors.
Hints
Learn the foundations
The Quantum Computing track covers this topic and more in depth.