{ "cells": [ { "cell_type": "markdown", "metadata": { "tags": [ "remove_cell" ] }, "source": [ "# Shor's Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Shor’s algorithm is famous for factoring integers in polynomial time. Since the best-known classical algorithm requires superpolynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers.\n", "\n", "In this chapter we will focus on the quantum part of Shor’s algorithm, which actually solves the problem of _period finding_. Since a factoring problem can be turned into a period finding problem in polynomial time, an efficient period finding algorithm can be used to factor integers efficiently too. For now its enough to show that if we can compute the period of $a^x\\bmod N$ efficiently, then we can also efficiently factor. Since period finding is a worthy problem in its own right, we will first solve this, then discuss how this can be used to factor in section 5." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "tags": [ "thebelab-init" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Imports Successful\n" ] } ], "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "from qiskit import QuantumCircuit, Aer, execute\n", "from qiskit.visualization import plot_histogram\n", "from math import gcd\n", "from numpy.random import randint\n", "import pandas as pd\n", "from fractions import Fraction\n", "print(\"Imports Successful\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. The Problem: Period Finding\n", "\n", "Let’s look at the periodic function:\n", "\n", "$$f(x) = a^x \\bmod{N}$$\n", "\n", "
\n", " Reminder: Modulo & Modular Arithmetic (Click here to expand)\n", "\n", "The modulo operation (abbreviated to 'mod') simply means to find the remainder when dividing one number by another. For example:\n", "\n", "$$17 \\bmod 5 = 2$$\n", "\n", "Since $17 \\div 5 = 3$ with remainder $2$. (i.e. $17 = (3\\times 5) + 2$). In Python, the modulo operation is denoted through the % symbol.\n", "\n", "This behaviour is used in modular arithmetic, where numbers 'wrap round' after reaching a certain value (the modulus). Using modular arithmetic, we could write:\n", "\n", "$$17 = 2 \\pmod 5$$\n", "\n", "Note that here the $\\pmod 5$ applies to the entire equation (since it is in parenthesis), unlike the equation above where it only applied to the left-hand side of the equation.\n", "
\n", "\n", "where $a$ and $N$ are positive integers, $a$ is less than $N$, and they have no common factors. The period, or order ($r$), is the smallest (non-zero) integer such that:\n", "\n", "$$a^r \\bmod N = 1$$ \n", "\n", "We can see an example of this function plotted on the graph below. Note that the lines between points are to help see the periodicity and do not represent the intermediate values between the x-markers." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n" ], "text/plain": [ "