01_shors_algorithm.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shor's algorithm\n",
    "\n",
    "Let $N=pq$ where p and q are prime numbers.  Shor's algorithm is described as below:\n",
    "\n",
    "1. Pick a number $a$ that is coprime with $N$.\n",
    "2. Find the order $r$ of function $a^r \\mod N$.  That is the smallest $r$ such that $a^r \\equiv 1 \\mod N$.\n",
    "3. If $r$ is even and $a^{r/2} \\not\\equiv -1 \\mod N$, find the greatest common divisors below which are the factors of $N$.  Otherwise, choose another $a$ and start over from step 1.\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\gcd(a^{r/2} + 1, N) \\\\\n",
    "\\gcd(a^{r/2} - 1, N)\n",
    "\\end{align*}\n",
    "$$\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}