{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>cs1001.py , Tel Aviv University, Spring 2020</center></h1>\n",
    "<img src=\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\" width=50/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recitation 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We continued with another recurssion question.\n",
    "We reviewed some properties of prime numbers and used them for primality testing. We reviewed the Diffie-Hellman protocol for finding a shared secret key and also tried to crack it. \n",
    "\n",
    "### Takeaways:\n",
    "<ol>\n",
    "    <li>The probabilistic function is_prime, that uses Fermat's primality test, can be used to detect primes quickly and efficiently, but has a (very small) probability of error. Its time complexity is $O(n^3)$, where $n$ is the number of bits of the input.</li>\n",
    "    <li>The DH protocol relies on two main principles: the following equality $(g^{a}\\mod p)^b \\mod p = g^{ab} \\mod p $ and the (believed) hardness of the discrete log problem (given $g,p$, and $x = g^{a} \\mod p$ finding $a$ is hard). Make sure you understand the details of the protocol.</li>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Code for printing several outputs in one cell (not part of the recitation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursion: another example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $N$-Queens\n",
    "\n",
    "The $N$ queens problem is to determine how many\n",
    "possibilities are there to legally place $N$ queens on an $N$-by-$N$ chess\n",
    "board. Legally means no queen threatens another queen.\n",
    "\n",
    "\n",
    "Solution:\n",
    "We build the solution incrementally, column by column.\n",
    "We maintain a partial solution (implemented as a list), which is initially empty.\n",
    "\n",
    "The function $legal(partial, i)$ is given:\n",
    "- a partial solution placing the first $len(partial)$ queens on the leftmost columns\n",
    "- a positive integer $0\\leq i<N$\n",
    "\n",
    "It returns True if it is legal to place a queen in the next column on row $i$, given the partial placement $partial$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def legal(partial, i):\n",
    "    ''' Can we place a queen in the next column in row i ? '''\n",
    "    \n",
    "    # any queens in the same row to the left ?\n",
    "    left = [j for j in partial if j==i] \n",
    "    # diagonal up - left\n",
    "    diag_up = [j for j in partial if j - partial.index(j) == i - len(partial)]\n",
    "    # diagonal down - left\n",
    "    diag_down = [j for j in partial if j + partial.index(j) == i + len(partial)]\n",
    "    \n",
    "    res = ( left == diag_up == diag_down == [])\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def queens (n, show = True):\n",
    "    ''' how many ways to place n queens on an nXn board ? '''\n",
    "    partial = [] # list representing partial placement of queens\n",
    "    return queens_rec (n, partial, show)\n",
    "\n",
    "def queens_rec (n, partial, show):\n",
    "    ''' Given a list representing partial placement of queens ,\n",
    "    can we legally extend it ? '''\n",
    "    if len(partial) == n: # all n queens are placed legally\n",
    "        return 1\n",
    "    else:\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            # try to place a queen in row i of the next column\n",
    "            if legal(partial, i):\n",
    "                cnt += queens_rec(n, partial + [i], show)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "0\n",
      "0\n",
      "724\n"
     ]
    }
   ],
   "source": [
    "print(queens(0))\n",
    "print(queens(1))\n",
    "print(queens(2))\n",
    "print(queens(3))\n",
    "print(queens(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some intuition: \n",
    "assume we can find a solution for placing $k<N$ queens, how do we expand the solution to $k+1$?\n",
    "queens_rec returns the number of possible legal placements for $N$ queens, where $k$ are already placed at the leftmost columns and there are $N-k$ queens left to place. \n",
    "The recursive idea: Legally place queen number $(k+1)$ and recursively solve the problem, when there is one less queen to place.\n",
    "\n",
    "Note that the complexity is $O(N!)$ (greater than $O(2^N)$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Primes and Diffie-Hellman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Fermat's little theorem\n",
    "Fermat's little theorem states that if $p$ is prime and $1 < a < p$, then $a^{p-1} (\\textrm{mod}\\ p) \\equiv 1$\n",
    "\n",
    "\n",
    "\n",
    "#### Compositeness witnesses\n",
    "A witness is a piece of evidence that can be produced in order to prove a claim. In our case, the problem we are tackling is deciding whether a given number $m$ is prime or composite. We now describe three types of witnesses for compositeness:\n",
    "\n",
    "* A clear witness for compositeness can be a (not necessarily prime) factor of $m$. That is, a number $1 < b < m$ such that $b ~|~ m$ ($b$ divides $m$). Since $b$ is a non-trivial factor of $m$, $m$ is clearly composite.\n",
    "* Another, less trivial witness of compositeness is a GCD witness, that is a number $1 < b < m$ such that $\\mathrm{gcd}(m,b) > 1$. Think, why is $b$ a witness of compositeness? Let $\\mathrm{gcd}(m,b) = r$, then by definition $r ~|~ m$. As $r \\leq b < m$ we get that $r$ is a factor of $m$ and thus $m$ is composite.\n",
    "* Fermat's primality test defines another set of witness of compositeness - a number $1 < a < m$ is a Fermat witness if $a^{m-1} (\\textrm{mod}\\ m) \\not\\equiv 1$\n",
    "\n",
    "Why go through all of this work? Our tactic would be to randomly draw a number $b \\in {1,\\ldots, m - 1}$ and hope that $b$ is some witness of compositeness. Clearly, we'd like our witness pool to be as large as possible. \n",
    "\n",
    "Now, if $m$ is a composite number, let $\\mathrm{FACT}_m, \\mathrm{GCD}_m, \\mathrm{FERM}_m$ be the set of prime factors, GCD witnesses and Fermat witnesses for $m$'s compositeness. It is not hard to show that $$\\mathrm{FACT}_m \\subseteq \\mathrm{GCD}_m \\subseteq \\mathrm{FERM}_m$$ \n",
    "\n",
    "But the real strength of Fermat's primality test comes from the fact that if $m$ is composite, then apart from very rare cases (where $n$ is a Carmichael number) it holds that $|\\mathrm{FERM}_m| \\geq m/2$. That is - a random number is a Fermat witness w.p. at least $1/2$.\n",
    "\n",
    "A side note (for reference only) - Carmichael numbers are exactly the composite numbers $m$ where $\\mathrm{GCD}_m = \\mathrm{FERM}_m$\n",
    "\n",
    "#### Every factor of a composite number is a Fermat's witness\n",
    "Let $m$ be a composite number and write $m = ab$ for some $a,b>1$. We claim that $a$ is a Fermat witness. To see this, assume towards contradiction that $a^{m-1} (\\textrm{mod}\\ m) \\equiv 1$, i.e. $a^{m-1} = c\\cdot m + 1= c \\cdot a \\cdot b + 1$ for some $c \\geq 1$.\n",
    "\n",
    "Rearrange the above to get $a(a^{m-2} - c\\cdot b) = 1$. However, $a > 1$ and $(a^{m-2} - c\\cdot b) \\in \\mathbb{Z}$, a contradiction.\n",
    "\n",
    "\n",
    "#### Primality test using Fermat's witness\n",
    "\n",
    "We can use Fermat's little theorem in order test whether a given number $m$ is prime. That is, we can test whether we find a Fermat's witness $a\\in\\mathrm{FERM}_m$ for compositeness. Note that if the number has $n$ bits than testing all possible $a$-s will require $O(2^n)$ iterations (a lot!).\n",
    "\n",
    "Instead, we will try 100 random $a$-s in the range and see if one works as a Fermat's witness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def is_prime(m, show_witness=False):\n",
    "\n",
    "    \"\"\" probabilistic test for m's compositeness \"\"\"''\n",
    "\n",
    "    for i in range(0, 100):\n",
    "        a = random.randint(1, m - 1) # a is a random integer in [1..m-1]\n",
    "        if pow(a, m - 1, m) != 1:\n",
    "            if show_witness:  # caller wishes to see a witness\n",
    "                print(m, \"is composite\", \"\\n\", a, \"is a witness, i=\", i + 1)\n",
    "            return False\n",
    "\n",
    "    return True\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For $a,b,c$ of at most $n$ bits each, time complexity of modpower is $O(n^3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def modpower(a, b, c):\n",
    "    \"\"\" computes a**b modulo c, using iterated squaring \"\"\"\n",
    "    result = 1\n",
    "    while b > 0: # while b is nonzero\n",
    "        if b % 2 == 1: # b is odd\n",
    "            result = (result * a) % c\n",
    "        a = (a*a) % c\n",
    "        b = b // 2\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Runtime analysis:\n",
    "\n",
    "* The main loop runs over $b$, dividing $b \\to b/2$ at each iteration, so it runs $O(n)$ times.\n",
    "* In each iteration we do: \n",
    "    * One operation of $b%2$ in $O(1)$ time\n",
    "    * One operation of $b/2$ in $O(1)$ time\n",
    "    * At most two multiplication and two modulu operations\n",
    "    * Multiplication of two $n$ bit numbers runs in time $O(n^2)$\n",
    "    * Modulu can be implemented by addition, division and multiplication: $a \\textrm{ mod } b = a - (a // b) b$ and division runs in time $O(n^2)$ same as multiplication\n",
    "    * Finally, the modulu operation keeps all numbers at most $n$ bits, thus the running time does not increase with each iteration\n",
    "* In total - $O(n^3)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The probability of error:\n",
    "First, notice that if the function says that an imput number $m$ is not prime, then it is true. \n",
    "The function can make a mistake only is the case where a number $m$ is not prime, and is excidentally categorized by the function as prime. This can happen if all $100$ $a$'s that the function tried were not witnesses. \n",
    "\n",
    "A quick computation shows that if $m$ is **not** a Charmichael number then at least $\\frac{1}{2}$ of all possible $a$s are witnesses, so in almost all cases the probability for error is $(\\frac{1}{2})^{100}$ (this is extremely low).\n",
    "\n",
    "#### Failing over Carmichael numbers\n",
    "In the rare case where we get a Carmichael number as input we have no guarantee on the performance of the test. In the following example we test whether the Carmichael number $N$ (which is composite) is prime or not using our test.\n",
    "\n",
    "The number $N$ comes courtesy of [Wikipedia](https://en.wikipedia.org/wiki/Carmichael_number#Overview)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# p is a large prime:\n",
    "p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883\n",
    "\n",
    "# N is a Carmichael number (and is obviously composite):\n",
    "N = p*(313*(p-1)+1)*(353*(p-1) + 1)\n",
    "\n",
    "is_prime(N)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing the prime number theorem: For a large n, a number of n bits is prime with a prob. of O(1/n)\n",
    "We decide on the size of the sample (to avoid testing all possible $2^{n-1}$ numbers of $n$ bits) and test whether each number we sample is prime. Then we divide the number of primes with the size of the sample."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prob_prime(n, sample):\n",
    "    cnt = 0\n",
    "    for i in range(sample):\n",
    "        m = random.randint(2**(n-1), 2**n - 1)\n",
    "        cnt += is_prime(m)\n",
    "    return cnt / sample\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "0.5011"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob_prime(2, 10**4)\n",
    "prob_prime(3, 10**4)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0133"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob_prime(100, 10**4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0063"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob_prime(200, 10**4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diffie Hellman from lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"DH.PNG\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The protocol as code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DH_exchange(p):\n",
    "    \"\"\" generates a shared DH key \"\"\"\n",
    "    g = random.randint(1, p - 1)\n",
    "    a = random.randint(1, p - 1)# Alice's  secret\n",
    "    b = random.randint(1, p - 1)# Bob's  secret\n",
    "    x = pow(g, a, p)\n",
    "    y = pow(g, b, p)\n",
    "    key_A = pow(y, a, p)\n",
    "    key_B = pow(x, b, p)\n",
    "    #the next line is different from lecture\n",
    "    return g, a, b, x, y, key_A #key_A=key_B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Find a prime number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_prime(n):\n",
    "    \"\"\" find random n-bit long prime \"\"\"\n",
    "    while(True):\n",
    "        candidate = random.randrange(2**(n-1), 2**n)\n",
    "        if is_prime(candidate):\n",
    "            return candidate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Demostration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "971\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(226, 96, 658, 536, 69, 793)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "p = find_prime(10)\n",
    "print(p)\n",
    "g, a, b, x, y, key = DH_exchange(p)\n",
    "g, a, b, x, y, key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "536\n",
      "793\n"
     ]
    }
   ],
   "source": [
    "print(pow(g, a, p))\n",
    "print(pow(x, b, p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Crack the Diffie Hellman code\n",
    "There is no known way to find $a$ efficiently, so we try the naive one: iterating over all $a$-s and cheking whether the equation $g^a \\mod p = x$ holds for them. \n",
    "\n",
    "If we found $a'$ that satisfies the condition but is not the original $a$, does it matter?\n",
    "\n",
    "The time complexity of crack_DH is $O(2^nn^3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crack_DH(p, g, x):\n",
    "    ''' find secret \"a\" that satisfies g**a%p == x\n",
    "        Not feasible for large p '''\n",
    "    for a in range(1, p - 1):\n",
    "        if a % 100000 == 0:\n",
    "            print(a) #just to estimate running time\n",
    "        if pow(g, a, p) == x:\n",
    "            return a\n",
    "    return None #should never get here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "617\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "617"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g, a, b, x, y, key = DH_exchange(p)\n",
    "print(a)\n",
    "crack_DH(p, g, x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Trying to crack the protocol with a 100 bit prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "888958161829799043985061475553\n",
      "867441475552671949999208459311 553248002741623339226706792959 414752428718086349833513855252 225642142325534266491072467972 646307605600255401720101354566 203280842942198745051972342627\n",
      "100000\n",
      "200000\n",
      "300000\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-30-6b3d13779c00>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0my\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m \u001b[0mcrack_DH\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-24-9a63fe3af2e8>\u001b[0m in \u001b[0;36mcrack_DH\u001b[1;34m(p, g, x)\u001b[0m\n\u001b[0;32m      3\u001b[0m         Not feasible for large p '''\n\u001b[0;32m      4\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0ma\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m-\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m \u001b[1;33m%\u001b[0m \u001b[1;36m100000\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      6\u001b[0m             \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m#just to estimate running time\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      7\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mpow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "import random\n",
    "p = find_prime(100)\n",
    "print(p)\n",
    "g, a, b, x, y, key = DH_exchange(p)\n",
    "print(g, a, b, x, y, key)\n",
    "\n",
    "crack_DH(p, g, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analyzing the nubmer of years it will take to crack the protocol if $a$ is found at the end (assuming iterating over 100000 $a$s takes a second)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "553248002741623339226706792959"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.75433790823701e+17"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a//100000/60/60/24/365\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}