Shor's Algorithm

• factoring integers in polynomial time

• Period Finding f(x) = a^x mod N where a and N are positive integers(a < N)

Qiskit Implementation

• Provide circuits for U => simply repeat the circuit x times => U^x

Modular Exponentiation

• Use algorithm known as repeated squaring to calculate exponential

Factoring from Period Finding

• general factoring algorithm will first check if there is a shortcut to factoring the integer