Bad Qubits — Learn Quantum by Doing

Multiple choice

Shor's algorithm does not factor N directly. Instead it reduces factoring to which problem, solved on the quantum computer, where given a with gcd(a, N) = 1 one seeks the smallest positive r with a^r = 1 (mod N)?

Searching an unsorted list of size N with Grover's algorithm
Computing the greatest common divisor gcd(a, N) by Euclid's algorithm
Order-finding (period-finding): the smallest r with a^r = 1 (mod N)
Sorting the residues a^x mod N into increasing order