Shor.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Quantum-Vedas/Quantum-Algorithms/blob/main/Shor.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "kw423rRxRuZx"
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "import numpy as np\n",
        "\n",
        "from qiskit import *\n",
        "from qiskit.providers.ibmq import least_busy\n",
        "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute\n",
        "from qiskit.quantum_info import Statevector\n",
        "from qiskit.circuit.library import QFT\n",
        "from qiskit.visualization import plot_state_qsphere\n",
        "from qiskit.quantum_info import Operator\n",
        "from qiskit.tools.monitor import job_monitor\n",
        "\n",
        "from qiskit.tools.visualization import plot_histogram\n",
        "from IPython.display import display, Math, Latex\n",
        "import math"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XjAql941RuZ1"
      },
      "source": [
        "# An encryption problem"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "btVIZd84RuZ3"
      },
      "source": [
        "A pretty well-known problem in computer science is the problem of encryptying messages, i.e, given a message $m$, a sender $A$ and a receiver $B$, we want to send the message $m$ encrypted, so that only $B$ will be able to decrypt the information sended from $A$. We can ilustrate this situation by a simple example: Lets suppose Alice wants to send her secret chocolate cake recipe to Bob, but the message will be stolen if the used information channel is unsafe, and her archenemy, Eve, will finally find out Alice's delicious secret chocolate cake recipe. And we know that both Alice and Bob have lots of padlocks, but they don't share any of its keys. Hence from that we got our main problem.\n",
        "\n",
        "$$\n",
        "\\text{How Alice could send the secret recipe to Bob, without being eavesdropped on?}\n",
        "$$\n",
        "# The Caesar's Cipher\n",
        "\n",
        "Throughout history this problem achieved huge relevance, once to be able to send secret messages to someone is a kind of communication superpower. A simple example of information cryptography enconding is The Caesar's Cipher, using it we can encode a message by shifting its characters by a constant private key $k$ in the roman alphabet\n",
        "$$\n",
        "    \\Sigma = \\text{ABCDEFGHIJKLMNOPQRSTUVWXYZ}\n",
        "$$\n",
        "\n",
        "Then, given a message $x =$ CHOCOLATE CAKE, and a encryption function with a factor private key $\\text{k} = 4$\n",
        "\n",
        "$$\n",
        "    E_k(x) = (x + \\text{k}) \\text{ mod } 26\n",
        "$$\n",
        "We get an encrypted message $y =$ GLSGSPEXI GEOI."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "RvXa9ZZgRuZ4"
      },
      "outputs": [],
      "source": [
        "def encryptCipher(x, k):\n",
        "    encryptedStr = \"\"\n",
        "    \n",
        "    for ch in x:\n",
        "        newCh = ch\n",
        "        if (ord(ch) >= ord(\"A\") and ord(ch) <= ord(\"Z\")):\n",
        "            newCh = chr((ord(ch) - ord(\"A\") + k)%26 + ord(\"A\"))   \n",
        "            \n",
        "        encryptedStr = encryptedStr + newCh     \n",
        "\n",
        "    return encryptedStr"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PdeYzgedRuZ5"
      },
      "source": [
        "And to decrypt the message, we need just to have or find out the factor $\\text{k}$ and to apply a decryption function\n",
        "\n",
        "$$\n",
        "    D_k(x) = (x - \\text{k}) \\text{ mod } 26\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "TOrs0V3FRuZ5"
      },
      "outputs": [],
      "source": [
        "def decryptCipher(x, k):\n",
        "    decryptedStr = \"\"\n",
        "    \n",
        "    for ch in x:\n",
        "        newCh = ch\n",
        "        if (ord(ch) >= ord(\"A\") and ord(ch) <= ord(\"Z\")):\n",
        "            newCh = chr((ord(ch) - ord(\"A\") - k + 26)%26 + ord(\"A\"))\n",
        "        decryptedStr = decryptedStr + newCh\n",
        "    \n",
        "    return decryptedStr"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "RZ8qRyR-RuZ6",
        "outputId": "fafaccf5-7754-4d0d-e895-7b216723aac8"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Initial message: CHOCOLATE CAKE\n",
            "Encrypted Message: GLSGSPEXI GEOI\n",
            "\n",
            "Message successfully decrypted: CHOCOLATE CAKE\n"
          ]
        }
      ],
      "source": [
        "x = \"CHOCOLATE CAKE\"\n",
        "k = 4\n",
        "\n",
        "y = encryptCipher(x, k)\n",
        "d = decryptCipher(y, k)\n",
        "\n",
        "print(f'Initial message: {x}\\nEncrypted Message: {y}\\n')\n",
        "\n",
        "if (x == d):\n",
        "    print(f\"Message successfully decrypted: {d}\")\n",
        "else:\n",
        "    print(\"Decryption Failed\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LW9_cW_TRuZ8"
      },
      "source": [
        "It's easy to see why this is not a safe encryption method, since we can easily bruteforce the initial message by testing all 26 possible private $\\text{k}$ keys. Therefore, Alice would most likely like want to use a more safe encryption algorithm to avoid any eavesdropping from her archenemy. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "307GPcRcRuZ8"
      },
      "source": [
        "# The RSA Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a4h0uKslRuZ9"
      },
      "source": [
        "An idea that could be better for Alice's and Bob's problem is developed based on public-key distribution cryptography. Alice will receive a public key from Bob, encrypt her message using it, then send it to Bob, that will decrypt the message sended by Alice with his private key. \n",
        "\n",
        "This looks a lot like with the RSA encryption protocol, heavily used to securely transmit messages over the internet. Developed by Ron Rivest, Adi Shamir e Leonard Adleman, the RSA algorithm is based on the public-key distribution cryptography model, where we have an encryption key, which is public, and a decryption key, which is private.\n",
        "\n",
        "In this cryptography protocol our user will get the public-key by the multiplication of two large prime numbers $p$ and $q$, and the private-key will also be generated by other particular use of these prime numbers. Our user can easily distribute the public key $N = pq$, while mantaining securely the individual values of $p$ and $q$, since to factor a number into two prime factors is a pretty difficult problem for classical computers.\n",
        "\n",
        "The key generator implementation can be easily described by the following steps  \n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "1.&\\quad\\text{ Randomly pick two large prime numbers } p \\text{ and } q \\text{, and take their product } n = pq.\\\\\n",
        "2.&\\quad\\text{ Compute Euler's Totient function } \\phi(n) = (p - 1)(q - 1) \\text{, and pick a number } e \\text{ so that, } 1 \\leq e \\leq \\phi(n) \\text{ and gcd}(e, \\phi(n)) = 1.\\\\\n",
        "3.&\\quad\\text{ Calculate the modular inverse } d \\text{ of } e \\text{ modulo } \\phi(n) \\text{ i.e, } de \\equiv 1 \\text{ mod }\\phi(n) \\text{. In other words } d \\text{ is the multiplicative inverse of } e \\text{ in } \\phi(N).\\\\\n",
        "4.&\\quad\\text{ Distribute the public-key } (n, e) \\text{ and keep the secret private-key } (p, q, d).\\\\\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Hence, to encrypt a message $m$, where $m < n$, to transmit a ciphertext $c$, we just take by fast exponentiation\n",
        "\n",
        "$$\n",
        "    c = m^e\\text{ mod } n\n",
        "$$\n",
        "\n",
        "And likewise, the message receiver computes $m = c^d \\text{ mod } n$, retrieving the original $m$ message."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "tksKKCbyRuZ-"
      },
      "outputs": [],
      "source": [
        "def fastExp(a, b, n):\n",
        "    ans = 1\n",
        "    #computes a^b in O(log b)\n",
        "    while b > 0:\n",
        "        if (b & 1):\n",
        "            ans = (ans * a)%n\n",
        "        a = (a*a)%n\n",
        "        b = b >> 1\n",
        "        \n",
        "    return ans"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "RRmJSUk5RuZ_"
      },
      "outputs": [],
      "source": [
        "def encryptRSA(m, n, e):\n",
        "    c = fastExp(m, e, n)\n",
        "    return c"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "I_D9LdAfRuZ_"
      },
      "outputs": [],
      "source": [
        "def decryptRSA(c, d, n):\n",
        "    m =  fastExp(c, d, n)\n",
        "    return m"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0BxPY25nRuaA"
      },
      "source": [
        "As an example, lets consider the first word of our message $x =$ \"CAKE\", and arbitrary prime numbers $p, q$ and $e$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Yj3oy1DzRuaA"
      },
      "outputs": [],
      "source": [
        "#set 'p', 'q', e and 'n'\n",
        "#CAKE = 67 65 75 69 10 \n",
        "m = 6765756910\n",
        "p = 42643801; q = 59604644783353249; e = 2097593\n",
        "n = p*q\n",
        "\n",
        "#computes 'phi(n)'\n",
        "phi_n = (p-1)*(q-1)\n",
        "\n",
        "#computes multiplicative inverse 'd' of 'e mod phi(n)' (python is strange)\n",
        "d = pow(e, -1, phi_n)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "PGlVtG15RuaA"
      },
      "outputs": [],
      "source": [
        "c = encryptRSA(m, n, e)\n",
        "y = decryptRSA(c, d, n)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "QcRoEC3xRuaB",
        "outputId": "bbbe94f3-b5c2-4d21-9484-b4c5b863a03d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Initial message: 6765756910\n",
            "Encrypted ciphertext message: 587708175265402063982608\n",
            "\n",
            "Message successfully decrypted: 6765756910\n"
          ]
        }
      ],
      "source": [
        "print(f'Initial message: {m}\\nEncrypted ciphertext message: {c}\\n')\n",
        "\n",
        "if m == y:\n",
        "    print(f\"Message successfully decrypted: {y}\")\n",
        "else:\n",
        "     print(\"Decryption Failed\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ep0tdzZqRuaB"
      },
      "source": [
        "Now that we understood how the RSA protocol works, Alice and Bob are wondering if this might be a good choice for Alice's recipe encryption. And the answer (until now) is YES. As most simple as it might seen, the problem of factoring a number into two primes $p$, $q$ or finding the $d$ factor for a given $c$ ciphertext, i.e, breaking the encryption by finding out the private-key, is a pretty difficult problem for computers to solve. \n",
        "\n",
        "This fact comes from the notion that in practice the prime numbers used to encode messages like this are of the order of $10^100$. Therefore algorithms of complexity $O\\big(\\sqrt{N}\\big)$ such as Euler's Totient function algorithm, would take an exponential time to run.\n",
        "\n",
        "Since, let $N$ be a positive integer and $k = \\log_2 N$. A complexity of $O\\big(\\sqrt{N}\\big)$ will be equivalent to $O\\big(\\sqrt{2^k}\\big)$, which is an exponential running time algorithm in terms of the input length for pratical purposes.\n",
        "\n",
        "But what would happen if we had a Quantum Computer? Is Alice's recipe still safe? *Yes*? Are you Shor about that?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Sb6x5JOMRuaB"
      },
      "source": [
        "# Modular Arithmetic and Periodic Functions\n",
        "\n",
        "Let $N$ be the integer, such that $N = pq$, and $f : \\mathbb{Z} \\rightarrow \\mathbb{Z}_N$ be a modular periodic function defined as\n",
        "\n",
        "$$\n",
        "    f(x) = a^{x} \\text{ mod } N\n",
        "$$\n",
        "\n",
        "Then, we aim to find the periodicity of this function defined by the smallest positive integer $r$ so that $a^r \\equiv 1 \\text{ mod } N$.\n",
        "\n",
        "We can ilustrate our problem by the following example with $N = 15$ and $a = 13$.\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    x &= 0 \\quad 1 \\quad \\text{          }\\text{ }2 \\quad 3 \\quad 4 \\text{ }\\text{ }\\quad 5 \\text{ }\\quad 6 \\quad 7 \\quad 8 \\\\\n",
        "    x &\\equiv \\underbrace{1 \\quad 13 \\quad 4 \\quad 7 \\quad 1}_\\text{Period $r = 4$} \\quad 13 \\quad 4 \\quad 7 \\quad 1 \\quad (\\text{mod } 15) \\\\\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Which give us a period $r = 4$. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "CrAHm44nRuaC",
        "outputId": "bffe0382-b833-4cb5-a208-fbcc933f4564"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Text(4, 1, '')"
            ]
          },
          "execution_count": 12,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEGCAYAAABo25JHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAABZzklEQVR4nO2dd3hU1daH3z3pvZBGEkjoEDqEXkSKgAXsn73LvV4rKipeRVGsqNfee7l2RAWlKCAdCSSElkCoSSCkkV5nZn9/JOEGSJlyzpxJ5rzPk4fkzJl9FnvmnLXLWr8lpJTo6Ojo6LguBq0N0NHR0dHRFt0R6Ojo6Lg4uiPQ0dHRcXF0R6Cjo6Pj4uiOQEdHR8fFcdfaAGsJCwuT8fHxWpuho6Oj06bYtm1bvpQyvKnX2pwjiI+PJykpSWszdHR0dNoUQogjzb2mLw3p6OjouDi6I9DR0dFxcXRHoKOjo+Pi6I5AR0dHx8XRHYGOjo6Oi9PmooacicXJ2Sxcns6xokqig32YM7UXFw+O0dqsdoHet+qh9616tNW+1R2BjSxOzmbuop1U1poAyC6qZO6inQBt4oN3ZvS+VQ+9b9WjLfetvjRkIwuXp5/6wBuorDWxcHm6Rha1H/S+VQ+9b9WjLfet7ghs5FhRpVXHdSxH71v10PtWPdpy3+qOwEaig32sOq5jOXrfqofet+rRlvtWdwQ2MmdqL3w83E475uPhxpypvTSyqP2g96166H2rHm25b/XNYhtp2PyZ88MOak2S6GBvHpra2+k3hdoCDX349JI9FJTXENOGoi+cnYY+fGFZGseLq4gI8OLR8/vofasADX343O97OVFSTZCPO/Nn9GsTfSvaWs3ixMRE6Uyic1sOFnDTJ1sZ1yOM929I1NqcdoeUkrJqIwHeHlqb0m4wmyU5JXVOwN1NXxRQkqpaE70fX0ZsiA+f3DSMHpEBWpt0CiHENillkw8pfUZgJyO6dmDO1F54nzEl1LGPaqOJQ/nlPLN0L0UVtfx691itTWo35JVVM/r5VTxxUQJTEiKJDfHV2qR2g8kseXhab0Z16+BUTqA19OGAHZRW1bLlYAGXJ8ZyzYjOWpvTrjicX8G0V9cR5OPBdSP1vlUSH083nr2kP0tTj3PxWxu1Nqdd4eflzh0TutElzI+dWcVam2Mx+ozADnYfK+Gq9zfz1W0jSIwPQSDwdNd9qxJEBXrz1jVDGBoXQlSQt9bmtCsCvT24ZkRnukf4k11UgZQSIYTWZrULyqqNGAR8tP4Qb67az96np+Hl7vyrBfpTyw76dAzki1uHU2sy0+fxZWw6WKC1Se2GIF8PLhjQkchALwrLayitqtXapHZDbmkVx4srGRYfwiWDY3UnoCCfbTxMwrzlnJcQyQc3JCJoG32rOwI7CPLxYFyPcAbGBnPXxB7EtIF44bbCofxy0nJKyDpZyZCnV/LbzuNam9Ru+GDtQSYsXIOUcDi/nNySKq1NajeM7R7GYxf0oV9MEJP6RLaZFQJ9acgOdmQWYTSbGRoXyv1TemptTrvi7dUZrN2fx4aHJ/LYBX0YGheitUnthpmDYugXE0SNycyEl9Ywe3JP7p3cQ2uz2gUDOwUzsFMwUkpSs4rx83Kne4S/1ma1ih4+age3f57E0YIKls8eT63JTGF5DZGB+nq2Euw7UUpuSTVje4RpbUq75pcdx+gbHUi3cOd/WLUFMgsr6ODvia+nO0OeXsnUvlE8d2l/rc0CWg4f1R2BHWQWVlBcWUu/mCDu+TqZlMwi1j50rtZmtTtKq2rJLqqkd1Sg1qa0C3ZmFRMd7E0Hfy+tTWl3DH16JefVP/w3HywgOsiHzh2cIzy3JUfQNhawnJROob70iwkC4MrETtynT68VY016LjnFdWvXr/+5n5lvbsBsbluDFmfEbJZc8vYGPlx/CICCsmrW78+nrQ0InZV5FyVw2ZC6TOKRXTs4jRNoDYc5AiHEx0KIXCHErkbHFgoh0oQQqUKIn4QQwY6yx15qTWYWJ2eTWVgBwNgeYVw6JFZjq9oHpVW13PTJVn5OyQbgksGxvHH1YMz6w8puJPDBjYlcUi97sDjlGNd9tIWTFXpUlhLMHBRDYnwoALklVSxJPUbVGdLUzogjZwSfAtPOOLYS6CelHADsA+Y60B67yCmu4r5vU9h4IB+oG2llFlZQUFatsWVtH28PNxb9azQXDYwGICE6kPP6RulyCArgZhCc2yuCnvVZr9P6RfHNrJH4eTl/rLuzU1xRS0ZuGbUmMwBbD5/krv8mcyCvTGPLWsdhd5aUci1QeMaxFVJKY/2fm4E2M6SOCvLmj/vP4byEKABKqmoZ9+JqFm3P1tiyto+Hm4EhnUNOyfeazZLdx4o5UlCusWVtn5ziKrYdOUm1sW6UGhPsw8iuHdpE0pOzs2ZfLpNf+YsjBfWrBN3D+O2ecW0iasiZhli3AL839YIQYpYQIkkIkZSXl+dgs5rGw81A9wh/Qvw8AQj29WTh5QOY2CdCY8vaPhm5ZaxOyz01sgK4/J1NfLbxiIZWtQ+W787hsnc2UlplPHVsy8ECdmQWaWdUOyExPpTXrhpEbEjdACbI14OE6MA24WSdwhEIIf4NGIGvmnpdSvm+lDJRSpkYHh7uWOOaIfnoSX5KzjptA/OKxE56GJ4CLEk9xi2fbaVhS8BgELx3/VBuHB2nrWHtgGn9ovjkpmGE+nqeOvbwj6m8v/aghla1D2KCfZg5KOY0Acq/9uWxKu2EhlZZhuYJZUKIm4ALgUmyDYUu/JxyjB+3ZXHJ4P+tZhWW13Agr4xh9ZtFOrZxw6h4zu0VcVpW5viezjEAaOtEBnqflevy5jVDCNNDSe1mz7ES/L3cT4sUemdNBjVGMxN7R2poWes4NI9ACBEPLJFS9qv/exrwCnCOlNKiNR9nySOoqDGSX1pz2of+5qr9vLRiH3uemoqvp+Y+tl2RW1LF9qMnmdQnEg9909hmNmbk08Hfi15RbUciua0w4831hPh68tktw08dyy6qJNDb3SnqaThFHoEQ4mtgE9BLCJElhLgVeBMIAFYKIVKEEO86yh578fV0PytG+MIB0Xx56wjcDfqDyh6WpB47S8L3r315/PPL7WSddP5C4M7MI4t28vaajNOOnSip4rutmRTrIaR2MX9G37NyiWKCfZzCCbSGw4atUsqrmzj8kaOurzSfbjjEgE7BDOn8Pw2c+DA/4sP8NLSqffDoop1cMjiG/rFBp45N7B3Br3eNJTpYl/Cwhw9vTMTNcLoi5v4TZTz0YyqdQn0Z1a2DRpa1fQZ3PlsPK6+0mp9TsjkvIcqpk8v09QsbqDWZmb9kD3dP7HGaIwDYergQP093EqJ1OQRbWT57PG5nSCN38PfSJREUoGcTVbOGxoXw15wJunquHZRW1ZKSWcSAmGCCfP83AyiurGXB0r2EB3g5tSPQ1zBswMPNwK4np3L7uC5nvXbXf7fzUX36vo5tdAzyIaIJ8b61+/LYkJGvgUXtg9zSukzXk+U1px338XQjroOfnrBnB+k5pVz/0d+kZBWddrxLmB/Jj09h5iDnLmCvf/I24ufV9AbQe9cn8uBUXZLaVg7nl/PVliMUVdSc9drLK9J5Z80BDaxqH+zILOau/yZztF4WpTF/7j3B4mQ9GdJWencM5Lt/jGJQp+DTjrsZxKlcI2dGXxqygV3Zxazdn8d1I+MIPMMZnPlF0LGOrYcL+fdPuxjXPZxg39NvoNevHkyQj/NvvDkrY7uHsey+ccR3OHsf67ukTA7mlXPxYOceuTor/l7uDO/SdNj4yj0nyMgt444J3RxsleXoMwIbSDpcyIvL0mkq8januIoft2VRXm08+0WdVrlkcAyb5k5sclM4roPfWc5Bx3J8PN3oHRV4WsJTA89fOoCl94zTwKr2QfLRk2w60HSp2vX78/hs42HHGmQlej0CGymvNuLr6XZWvdcVu3OY9cU2fr5zDAP12YGinCip4redx5nWL4qOQfrGprWsTs9FSun0yU1tkX9+sY2MvDL+uP+cs16rNprwdDNoXhu6pTwCfWnIRvy8mu66Ud06sOqBc+gU6rwRAs7Mou1Z+Hq6Ma1fx7Neyy2pZv6ve4gO9tEdgQ2899cBjKamHUFheQ2fbzrM1L5R9OmoR7xZyxMzEiiubDoPoy1oDemOwAbeX3uAqCAfZtTLJDcmwNujTSSQOCsfrT9ExyDvJh1B744BJD02mQ5tYPPNGXnv+sRmlyyNZjOv/bmf6CAf3RHYQMeg5gcn5dVGXl6xj3N7hzOuh3NKpeiOwAZ+2JZF/5jgJh0B1EVg1BjNTO9/9sNMp2V+vnMMFc0U8vBwM+iaOHYQ5OPR7GZ7uL8Xe5+a1uT+gU7LGE1mFiVnMzw+tMmEUm8PN37cnkV0sLfuCNoTK2afg7GRRPKZfLrxMEUVtbojsAF3NwOBLcSzr9idw7GiSm4ac3YOh07zlFUb+XrLUSb1iaBrEwq5QgjdCdhIbmk1D/2QyrOX9G/SEbgZBCnzpmi+R9ASetSQjbSUfPPKlYP4/p+jHGhN+yC3pIqXlqdzsIWKTiv3nODjDYcdZ1Q74WhBBc/8tpe0nNJmz1mxO4dnlu5xoFXtg8hAb9Y9dC4XtDDwc2YnALojsJoDeWU8vnhXi9WywgO89NGVDRwtrODtNRmnitY3xVMz+/HXnAmOM6qd0KdjADueOI9zezVfOGnXsRKWph5vcbarczZuBkGnUN/TpCXOZFXaCe74cttp9UucCd0RWEn2yUp+2XGM8urmC1LnlVbz1uqMNlGr1JlIjA9l34LpzSbmQF0svLOPrpwRIQRBPh74eDY/QJk9uQcb507SpSasZPvRk3y3NRNTCw/5grK6WiXNRRZpjf6JW8n4nuHseOK8FkXlKmqMLFyezq7s4mbP0WkadzdDiw+i4spanv1tL38fKmz2HJ2zWZ2ey8etaGDpDtY2fks9zpO/7sbQQvddkdiJFbPPcVq5Cd0RqECnEF92z5/q9EJTzsai7Vmtagl5uRv4fNNh0nNKHGRV+2DF7hw+XNdyOcpak5lHfkxlSeoxB1nVPpgzrRd/3H9Om3aketSQlby/9gCVNWbuPaMARWMMBtFswplO82w6UEBaTmmLmizeHm7smT8NQ0vDL52zePaS/lQ2E5bbgIebgaQjJ/WaGlbi5e5GtAUS3vd/l0KfqEBuH9/VAVZZh/60spK046WUWqAjtGxXDnuOl3D/FF2J1FIWXjEQSyRPdCdgPUIIi8qnNiWRoNMyH647SP+YIEZ0bbmoT2mVkfIa59Qg05eGrOSV/xvEBzc0KddxGtuOFPLjtiyLHmw6/8OS6fWK3Tnc/22K+sa0E6SUPPvb3mZF0XRsx2yWvLAsjXX7W6+T8cENidw32TkHhrojUIlHpvdhwyMT2/S6oSOpqjXxwHc72Hig9RvqeHEVKZlFusKrhZRVG/ly8xF2H2s9eGF1ei7XfriZCicduTobBoNg9/xpTi0xbQm6I7CC/LJqbvtsK1sOtj6yOrMurE7LFFXUsulAfos5BA3cODqeVQ9O0PdhLCTA24Pd86dyswXZ2CaTpLzaRJFeyN5iPN0NFn0Xtxws4KI31reYg6QV+p1kBaVVRrJOVlJlbD3hprLGxIKle5jYO4JJfXTZ39aICvJm49xJWpvRbhFC4GbB2GRyQiSTE/Tvq6XszCrmz7QT3DQ6vtVaGX5e7oT4eVJtwfPD0egzAivoEubHsvvGc07P1oWjvNwNrErL5VC+83n/to6Ukvu+SebLzUe0NqVNsH5/PvN/3a0vpalAanYRr/6xH0sShvvFBPH5LcPpGRmgvmFWojsClTAYBJvmTuK2cc4XKuaM/LrjGA98t8MieQMhBHll1U6bpels7M8t5YekLDzdLbvd7/8uhed/T1PZqvbBtSPi2LdgOiEtyEu0BfSlISv4dMMhth4+yVvXDtHalHZHTnEVO7OLLJY3+Oq2kSpb1H64eUwXi/YHGvByd8PLQqehg8UOFuDhH1Ipra7l7WuHqmiR9Tjs0xZCfCyEyBVC7Gp0LFQIsVIIsb/+3xBH2WML1UazVXHAf+w5wY0f/62LeFnA7eO7smK2HsPuDDx3aX9m6/kvFvHuXwf4cVuWxefHhfnSrQkZcK1xpNv/FJh2xrFHgD+llD2AP+v/dlr+cU43Pr15uMXnV9SaKCyvoUhfwlCc9fvzmfnWBnJLWo8ycnXm/7qb75IytTajXfL7zuNssCDkuYF/TejOA+f1UtEi23CYI5BSrgXOVAqbCXxW//tnwMWOsscRzBgYza93j9WralnAHV9u47utlj+svD0M+Hu5UV7TsmyCDmw/WsTBPMuDFpKPnmTiS2tIzSpSz6h2ws93jeXlKwZa/T5nSzTVeiEwUkp5vP73HKDJuDUhxCwhRJIQIikvL89x1jVCSsnMtzbwvT6yUhyzWZJXWk2ZFVEtifGhfHXbSLroujit8vOdY3hkem+Lzw/186RXVICeC2Mh1iSNHsgrI3HBSpbvPqGiRdajtSM4haxzkU26SSnl+1LKRCllYni4NjU/K2tNdPDztLrgzL3fJPP6n/tVsqp9YDAIfrhjNLeM1ctPOgNxHfx457qh9I0O0toUp+ZgXhmP/JhqVd2RiAAvJvWOJCLQuVYJtHYEJ4QQHQHq/83V2J5m8fV05+ObhnFRMwXrm0MfU6nH/d+l8OD3O7Q2w6lJPnqSf36xjaMFFVa/19mWL5yNnJIq/kzLpdKK5ckAbw9euHwAQzo7V1yM1o7gF+DG+t9vBH7W0BZVePWqwdwzqXnJap06fZtrPtjMCSs3fmOCfYixQP7XlSmurCUjrwyDlXf63EWpXPneJnWMaieM7hbG1n9Ppl+M9TOnaqNz7W05LI9ACPE1MAEIE0JkAU8AzwPfCSFuBY4AVzrKHmv5PimTTzce5r+3jyTIp20njzgbJpOk2mjGt4Uyik3hjNEXzsaEXhFMaKFOcXMMiA0mIsBbBYt0nl6yh192HGPrvydrbcopHOYIpJRXN/NSmxCYCfD2ICrQmwArhc62HCzgscW7ePvaIfRwwtRyZ0DXt3E+rh7eWWsTnJ73/jpASVUtc6ZavhEPMLZ7GCG+HpjN0mlqa2i9NNRmmNYvio9uGmb1Bxfs60l8mJ9FWiQ61rHnWAkjnv2Dtfu0iSRrCzz16x6e+32vTe+VUlKrJ0M2y5HCCjJyLd8obuDc3hHcNbGH0zgB0CUmVKdXVIBFhWxcmTu/2k5siA9zz+9j1fsiA70Y1yOc4Dau86ImlbUmTGbrHzjHiyuZ+NJfzJ/RlyuHdVLBsrbPs5f0t/m9VbUmjGaJv5NIqVtthRBiLDAc2CWlXKG8Sc7JxW9tYETXUOZOt+5hpdM6IX4eBNqw79LB34uXbEjmcSWeu9S2h1VEgDdXD+9Mtwjnk0No61QbTfR9Yjn3TOzRYu1zR9Lq0pAQ4u9Gv98OvAkEAE8IIZxaEkJJBncOpluYbTfFg9/v4KZP/m79RBdlwcX9ufPc7ja/X9dyUh43g2DeRQkMjXOuMEdn4WR5DTd8/DcbMiyXl2jAy92NR6b1ZmyPlmscOxJL9ggaD9VmAVOklPOB84BrVbHKCXniItunyAkdAxnUKVhZg3QAeHzxLia/8pfWZjglRwrKmfnWBosq6jWFlJKiihqFrWoflFUbKaqosXkP5fbxXRkaF6qwVbZjiSMwCCFChBAdACGlzAOQUpYDeqULC7hlbBenLVqtNSmZRZz70hqSj5606f2ju3XgsiGxClvVPqg1mQn0drc6G76BF5enM+LZPzHrkQ5n0SnUl1/uGmtTaC5AjdHMwbwyp0nas2SPIAjYRl2SrBRCdJRSHhdC+OMiibOr0k7w4PepfHXbCPp0DLSpDSklZqnXMj4TTzcDfaMDCWmlzF9zTO/fUWGL2g/dIwL44tYRNr9/Yu8IIgK8qDWb8TLY5kx0mubzTYdZsHQv2x+fQqifbd99JWnVEUgp45t5yQxcoqg1Tkq4vzfT+kUREWCbPsjh/HIuemM9z17a32qJivZOQnQgb15jX6GfGqMZk1niY2VCmk7LDIsPZVi88yxfOBOfbjjEuv35fHhjolWicw1M6BVBiK+nVUVt1MRmK6SUFdRlCrd7+scG8ewl/elgo5x0VJA3lw6JoVOor8KW6ZRU1dJn3jK9fnETvLgsjRs/ti9IoaiihoKyaoUsaj80rJbZ4gQAukf4c9nQWKcJH7XXHc1XxAonx2TnGqm3hxvzZ/bTN4yb4P7vUrj+oy02vz/Q24N7J/VgaLwe3XImYf5exIbYrsUkpWTUc6t4e80BBa1qH9wytgsf3TTMrjYyCys4lG95nQg1adUdCSFSm3uJZuoHtDdu+HgL7gYDn91ieXWypiirNjrNCMBZGBgbbHcRel3Ur2nslfUWQvDUzL5013MJVOGGj/8moWOgU9RAt+SpFAlMBc4M6xDARsUtckLO798Rg41TwAaeXrKHH7ZlseOJ8xSyqn1w4+h4u9swmswcL67Sl95U4IpEPav4TKSUXPTmeq4ZHsc1I2zXZHpyRl86OMFGMVjmCJYA/lLKlDNfEEKsUdogZ+TaEXF2tzGxdwRRgd6YzFKPHKqnIXTO1nXWBt5Zc4CXV+5jz1NT8fXUZ1xQJ2Ew/sXVPDi1F1fa8TCvqDFyILecPh0DcHdzjo1Nrak2mokJ9sHf277v2jk9tSmy1RStfrJSylullOubee0a5U1yLkxmSVWt/drhY7qHcfv4rroTaERuaTV95i3j55Rsu9qZnBDJi5cNUMiq9kF1rZkJvcKJDrKvXsPS1ONc9OZ6Mk9WKmRZ28fbw433rk9khp0RgCVVtWzIyKe0yr6lUSXQXXwr7M8tpffjy1i2K8futkqqavVMzUYYhOD6kXF0C7dvDbpPx0CuHNZJnw00IsjXgxcvH8jYHmF2tTOmexjvXjeEMH/nWMJoT+zILOLaD7ewM7tYa1N0R9AawT6ePHheT/p0tK+WQK3JzOCnVvLhukMKWdb2CQ/w4t8XJNhU4elMsosqyTppfTlGnZaJDvZhWr+OBHjrCq8N/Lgtiymv/MXJcvsGdQM7BfPf20fQX4Hvv73ojqAVooK8uWtiD+I6+NnVjoebgfkz+uoFWBpRYzQrlmJ/6dsbePWP/Yq01R54Z80Bhj/zhyIlEfedKGWXE4xanYUQPw+6hfsTYOceQaC3B6O7hTmFk9Xn0q1QXFGLl4fBZr2Wxlw30v5N5/bEwuVpfJeURcq8KXZvGC+4uD9RgXppxQZ6RvozrV8UXu72f2/nfL+DAG8PvrzNdrmK9sTE3pFM7K3MgG5nVjEnK2oYr/HGsSV5BPe39LqU8hXlzHE+Fizdw9r9eWx51P76opU1Jg7l10Vg2Pvgaw+M7hZGsK+nIn0xRZ9pncakPpFM6qNMnzw5oy9+ev6LKry5ej8H8sr54/5zNLXDkk+3YXG8FzAM+KX+74uAdi+yP2NQtGJ6Kz9sy+Txn3ez5dFJROqjV87tHcG5vW1TbzyTkqpa9hwrYWBssK45BIqGKQ/urGdtN2bmm+sZEhfCExf1tbutR6b3wd0JIgktCR+dX19/IBYYIqV8QEr5ADAUaPcVrsf1CFesVN85PSN465oh+uiqnuKKWsX2CDYfKOCq9zeTfqJUkfbaOiOe/ZNnlu5RpK3iylqW784hX9ccAmBUtzCbVYjPpEuYn1MkQlqzWRwJNN4mr8EFJCYO55crkkcA0LmDLxcM6KjLTABms2TogpW8tCJdkfYS40P54tbhdAu3b1O/PSCl5LqRnRnRRZkKWEcKyvnHF9tIOmxbzYj2xiPTe9uVpNeY0qpavk/K5GBemSLt2Yo1juBz4G8hxJNCiPnAFuBTVaxyEkqrapnw0ho+23hYsTYzcsvYp49aMZolj57fh3NtLOxxJqF+nozrEe4UERhaI4Tgvsk9FYtQ6xkZwM93jmF8T/tyEtoDSheSqaw1MeeHVNbuy1O0XWsR1vzHhBBDgHGABNZJKZMVMUKI2cBt9e3uBG6WUlY1dW5iYqJMSkpS4rKtUlljYunO4/SPCaJXlH15BA1MeeUv4sP8+OCGREXa0/kfu7KLKas2MrKr89SC1YIaoxkh6kKWdZRlTXoud/83ma9njVQk/0VKyeGCCmJDfFT/vIQQ26SUTT54rL2yibqCNA0/diOEiAHuARKllP0AN+AqJdq2Fx9PNy4fGquYEwBYcHE/Hjyvl2LttVVKq2opLK9RdIT1wrI0nlm6V7H22iq/7zpOz8d+V3S5YduRk/y645hi7bVVIgO9uWxorGLBHkIIuoT5ae60Lb66EOJe4CsgDIgAvhRC3K2QHe6AjxDCHfAFnOIbl1tSxaH8ckVrto7o2kFRx9JWWbQ9myFPr6TAzuzMxsy7MIG37Kx21h7oERHAPRN7EBWkXGTat1uP8tQSZTaf2zJ9Ogby5Iy+hNtYrbApth4u5MN1BxVrzxascUO3AiOklE9IKecBI4Hb7TVASpkNvAQcBY4DxVLKFfa2qwRf/53JxJfXYFTQERRX1LIq7QTFFdoLTWnJiK6hzLswgVAbaxU3RY/IADp30D4CQ2sSogOZPaWnotpLD5zXi+X3jVesvbZKjVGRhZDTWLcvjxeWpVFrUr5tS7HGEQjqloYaMKFA8XohRAgwE+gCRAN+QojrzjhnlhAiSQiRlJfnuE2VCwZE8dpVgxWtK5qWU8ItnyaxI6tIsTbbIr2jArllbBcMCsZQF1fW8lNyFpmFrq05VFheo/gDKzLQ2ymKrGvNrZ9t5cr3Nina5qxzurFr/lRNl4esufInwJb6qKEngc3ARwrYMBk4JKXMk1LWAouA0Y1PkFK+L6VMlFImhoc7LhW7e0SA3VKzZ9IvJogf7xjN0DjXTtI5nF+u+KyouKKW2d/uYNOBAkXbbWvc9Mnf3P65sgEVFTVGPtt4mJ1Zrq05NGNgNJcOjlG0TX8vd0WkQOzB4rmjlPIVIcRfwJj6QzcrFDV0FBgphPAFKoFJgGPCgloh+ehJOgb5KLrW6ufl7vJOAOrK9A3uHMxrVw1WrM2YEB/+uH+8UyToaMlt47rio4A2VmMMQvDEL7t58Lye9I/VXi1TK9So2GYyS95enUG/2CDFwqmtxapFRCnlNmCbkgZIKbcIIX4AtgNGIBl4X8lr2MoNH//NpYNjmD+zn6Ltbj96koKyGpfWx3n8wgSCfZWN+XczCLpH6BvxSs9ioa4YS9Jjk52mtKIWmMySihqj4rkqbgbBpxsPc/nQWM0cgcV5BEKIRODfQBx1DkQAUkrp0NJQjsojkFKy6UABHfy9FI/yueu/20nNKmbtQ+cq2q4O/H2okPQTpVzvokqvVbUm8suqiQz01jwksb2RkVvK5FfW8sbVg7lIYWdbYzQruhfZFC3lEVgzI/gKmENdwpd229sOQgjB6O7qZFLOPb8PHm7aC01pRXFlLVknK+gW7q+IvHdjVuzO4astR7l2eGdFN6LbCjuzi7ni3U18dstwxWvi/n2okDXpuTw0rbei7bYVAn08ePT83qoUklHbCbSGNVfPk1L+IqU8JKU80vCjmmUac6Kkio0Z+VTWKKMz1JiYYB8iAlxXffTvQ4Vc8Pp60nOUl9q4e2IPtj8+xSWdAEBcqC/PX9rf7op6TZGaVcTHGw5RXOmaoc8RAd7MGt+N+DDl9ay2HTnJQz/soKLGqHjblmCNI3hCCPGhEOJqIcSlDT+qWaYxa/flcc2HW8gtbVLpwi5Kq2r5cvMRl9UcGtgpiHevG0K3CPtqFTdFkK+HS8tQRwR6c9XwzqoMNK4fFcee+dMI8nFNPafC8hpKVCo0n1Ncxer0PHJLtFF4tWaP4EugN7Cb/y0NSSnlLSrZ1iSO2iMoLK8hLaeExLhQxadtRRU1DHpqJY9d0IfbxnVVtG1Xp9po4sN1hxjcOZjR3VxPJC2zsAKDQRAT7KO1Ke2OuYtSWbknl6TH7C9SdSZSStWLVSm1RzBMSukyIjmhfp6qPUiCfT3ZNHcikS66PLT7WDGebgZ6RCq/fOFhMPDmqgxuG9fFJR3Bs7/tZX9umWoVr15ank6PSH9mDlI2lr4tMHNQDEPjlClSdSZaVyy0xhFsFEIkSCldQnBkY0Y+fl7uDOwUrEr7HYNcd8T29JI9GE2SH+4Y3frJVmIwCLY/PsVll4duH99V1TX8FXtyKK8Jc0lHoLaq7YvL0gj08eCf53RT9TpNYY0jGAmkCCEOAdVoFD7qKJ5asofYEB8+vHGYKu1vPljA34cKuWdSD1Xad2aeuKgv1SpotjTgqk4AYIjKZSWX3zde89GrVmTklhId7KOohlNjDuSVEeqnnJidNVjzP5qmmhVOyHvXD8WkoNjcmWw9VMibqzOYNb6r4iGUzo5SZf6a4+9DhSxOyWb+jL4uFUtvNJlJziyie7g/ISolfrmqEyivNjL5lbU8NK0X/5rQXZVrvHe9djVKrJGYaLehok0R10Hdkoe3j+/Kv87trliBcUtYnJzNwuXpHCuqJDrYhzlTe3GxwroprVFZY2JDRj4DOwUrKuXbmCMF5SzblcPdE7s7bAnOGfo2t7SaK97dxLOX9OeaEeqUE08+epIP1x1SXIq5JZyhb90MgjeuHkzvdioh7zrDJSsoLK/hx21Z5JYoHzragLeHm8OdwNxFO8kuqkQC2UWVzF20k8XJ2Q6zAeBQfjm3fZ7E1sOFql3jsiGxbH98ikOdgDP0bYivZ10iWS/1hBkra0zsPlbssEL2ztK33h5uXDQwWpUAhwbSckq4/qMt7DlWoto1mqNVRyCEcK11C+o+kAe+30GGigWlpZS8tDydZbtyVLtGYxYuT6ey9vTkuMpaEwuXK1M83lK6hvux+M4xjFJx483RyWTO0rc+nm6c0zNc1dDR0d3DWDPnXNWX9xpwlr49UVLFvhOlqi4Xe7oZKK6spVyDpDJLZgTv1yuDIoRwicoUiXGhrH5wAoNUihiCurXWn5KzST56UrVrNOZYUaVVx9XC28ONQZ2CVVvDbuD539P4bONhVa/RgLP07YG8Mv4+VKh4gXUtcZa+/T4pk/P+s1bV4jFdw/355a6xDItXJ0S1JSzZI5gHfCSEMAIpwFpVLXICPN0NdFEhjfxM1j10rsNGr9HBPmQ3cfNEOzjxKCWziJPlNZzbW12VxV3ZxVQ6aGTlLH379ZajfLXlKHuemqrqdV5YlobJLHn0/D6qXgecp28vHBCtijaWs2DJjOBpIB2QwHfqmuMcrEnPZWnqcdWv48gljDlTe52lUe/j4cacqY7NEfxy8xEe/Wmn+te5bYTi8uHNcdPoeNzP+Cy16Nubx3bhs1uGqx7ZU1pVS6lKUgtncvOY+LOOadG38WF+TO/fUfXrvLIinX9+oajSv0VYMiN4SEqZL4TwA14DblPZJs35cvMRsouquGCAuh980uFCPt90hAWX9CNQYY3zM8krrWZq30jWZ+STX1ZDqJ8n8y5McHj0xdzpvSlUsGC9M2AwCKSURAZ6caKkmogALx49v4/D+zYm2Mch0hILLu6v+jUauG1cV6qMJr7afJSc4irNooaSDhcSFeRNbIi6RY98vdwJ9FEnT6ElLNYagrqNYyml8nKcVuAIraHKGhMlVbVEBqorAfHHnhM8+etuPrtlON3ClRdga8ysz5PwcDPw8pUD2XywgKFxIYoX2HAmdmUX89KKdOZdmEBXlfsW4HhxZV0m+vwV3DepJ/dOdnyi4PLdOXSP8Ff9u6QFUkp+Ss4mMtCbMSrJw7fE4KdWcMGAjg51gkpjt9aQEGI4dVnEW4UQCdQll6VJKX9T0E6nwcfTzSHZqZMTIpnsoCpl79+QSLXRhJe7GxM0qoIkpeSrLUcZFh+qeLGfMxGibhZUUqXuPoHZLDEYxKlQ1V/uHEuPSMc/iE1myb++2s4d53TjQZWXTQ7mlfHg9zuYM7U3o7qpF/31wdqD5JZWMXd6HwwGwX/+2MfgTiGaOIIPbkhs16qrloSPPgG8DrwjhHgOeBPwAx4RQvxbZfscTrXRxJur9msSy6sGZrOkrLruYdhQIDu7qJIvNx/BqGIERFOUVBp5bPEu1u3PU/1afaODWHrPOFUjv4wmM+e/vo7/bjl66lj/2CBNNhQFsOzecaolkjUmwNsDL3c3JOpGJx0rruRIQcWpvbTv/zGa//zfIFWv2RyJ8aGq5hA0kFdazaSX17Boe5bq12qMJTOCy4FBgBeQA8RKKUuEEC8BW4Bn1DPP8eSWVPPSin1EBnqTEK1+rPRzv+3F28ON2VN6qtL+6vRc7vsmhW/+MZK+0XWVlZIOF/LY4l0M7hx86pgjCPB25+9HJ2lejUkpSquM9IwMIDLwfxm2uSVVLErO5qKB0Q6VgjYYhEMeVADhAV58PWuk6td54qK+mBvF7UcFaaPWe6Kkir3HSxgWH4qfl7rr9yG+HvSMDFA9vPpMLLkjjVJKk5SyAjggpSwBkFJW0g5LVnYK9SXt6WmK1yRtjtzSalWzNGNDfJk5OJqejR4S5/aOYO2cc0lwUFJQAwaDICLQm2Bfx3zJX1yWxv3fpajWfoifJ69fPZhJff63vFdUWcvzv6eRcrRItes2xYG8Mn5OydaswpWSSCk5UZ/V3ziyrrSqlpeWp7PlYIFD7dmQkc9Nn2w9ZZOauLsZeOe6oQ4vYm+JI6hpSCgDhjYcFEIE0Q4dAdQlPTlqev+f/xvEM5eotwHVKyqABRf3P018LdDbg84dfB0uILYjs4gvNh2mqtYx8QYebga8VJp9HC2o4Hjx2fHt3cP92fbYZNUjzs7kr/Q87v0mhapax9yS/1m5j0vf3qBK25sOFjD6+VVszMg/7biXuxufbDhEalaxKtdtjkm9I/nhn6NUjxhqjKOTAi25S8bXzwaQUjb+lnkAN6pilYas3ZfHm6v2nzYlbav8tvN4kw8rqFseeuPP/Q6158+0XOb9stthGkuzp/TkuUvVUUl/cXkaF7y+npoz5LQNBkEHf8dLCV81vBMrZ48nxNcxG5oxwT70igpQ5YHVJcyPf4zvypC40yW1Pd0NbJ83hdvHO7aqX5CvB4nxylcqbI73/jrA4KdXOvQZ1Or/TErZ5LqFlDIf0E43VSU2ZOTz3tqDDkv2Ss8p5Yp3N7Ijs0jRdsuqjTzw3Q7eXn2gydf/PlzIW2syTm0kO4L7JvXg70cntwtp6Ien9ebFywY0+XDYmVXMwz+kUu7AvvX1dKdHZIDDZnlXDuvEc5cOUOV6HYN8eGha7yZn5Q0BD45k7b48klQUSTyT3h0DuXxIrKo1O87E3jtyviJWOBFzz++jSk3S5vD1dEMgqFE4gsffy50Vs8fzr3ObrnZ046h4dj45FX+VN78aYzAIh0kXQ1101LRX17Jsl/JZ4p1CfZsN/c0vq2b5nhyOFlYoft3m+Dkl+6ylFEeg9Izgp+Qsdh9rfunnUH45d361vcVzlObF5Wm8uTrDYdc7p2c4j12Y4NACS5aEj6Y287MTUCQIXggRLIT4QQiRJoTYK4QYpUS7tuLIUUenUF++++coVYSmOoX6NivF7Ofl7vCR+YfrDrImPddh1wv19SQm2EfRSI/yaiNzF+3kYAvKtON7hpP8+BSHKXRCnUrn99scF3JYUWNk1HN/8tH6Q4q1WWsy88zSND5ef7jZc7w9DKRkFpFb6hgZbKjLIZg/o6/Drgd1Drba6LjcXUvukEhgKnCmTKYANipkx2vAMinl5UIIT8BxuzJn8OxvexnZNZSJvR2T6KUGi5OzWbc/n6dm9m3xIfjt1qNkFlaqnoDUwFurM5g5KMZhCW0+nm58dJOypUZ3Hyvh55RsLh/avMSBI+tMNPD7vePO2q9QE19Pd87tHUHXcOXEGT3cDPz5wDktBhN0DPJhwyMTFbumJTi6vriUkuHP/slFA6KZd1GCQ65piSNYAvhLKVPOfEEIscZeA+qjj8YDNwFIKWsATcRojCYzi7Zn4efp7lBHsHB5GjuzS/j8luGKtJdXWs2h/DJ8W5la7souYc9xxyXObXtsiuJLYI5meJdQtjw6qdUltSWpx1icnM0HNyQ6ZN1eC7mQZ1WIdgvy8XCqDN6T5TUs253DhF7hDnMIQghuHhNPLwflhYBlm8W3SinXN/PaNQrY0AXIAz4RQiQLIT6sF7hzOO5uBpIem8I9k9SpSdocEQHeiiYf3T6+Kz/eMbrVB9D8GX358Y7Ril23NQwG4fCs2zdX7WfM86sUaathqh7g7dFq35ZXGykor1Fd4gIg62QF7/51oNkIMTVRahayNPU413+0hQILcmrW7c9j+mvryC1VP65/34lS5i7aSUauekWqmuJfE7qflp+iNs4QvuEODAHekVIOBsqBRxqfIISYJYRIEkIk5eWpL0/g6Pj6G0fH89ylyoyuGrTbLfk/OFIGOy2nhBeXpTnk5m1Mj8gApiREKlJQ5NZPk3jw+x0Wnft/wzrz07/GOGR0u/d4Kc//nkZBmWMn0p9sOESfecuorLF/LbvWZKbaaLYo2TDA24Mwf09KHeBkh8aFsOGRiSTGObZYjJSSwvIaVSuinXVBLX+AKOBwo7/HAUubO3/o0KFSLTYfyJePLkqVhWXVql1DTQ7mlcn4R5bI77Yetfg98xbvlC8vT1PRqjp+TsmW3R9dKo8WlKt+LTUwmczyzVX75Vebj2htSpOUVNbIWqPJoddMOlwoX16RLosraxx6XVfgx22ZMu7hJfJQXplibQJJspnnqlUzAiHExMb/KuSIcoBMIUTDjuUkYI9S7VtD5slKft+Vg5ubY2cEJ8trGPvCqtPEy2wh1NeTB6b0tKp4eVm1iXIFRnStMWNgNOlPTyc2xLEbb1A32LF3RmAwCO48t7tVom4vr0jn5k/+tuu6lhLg7YG7g6PAhsaFcP+UnnbX0kjPKbUpDNWW91jL6rRcfkp2rAAcwJDOITx2QR/8vR0T3m3tN+elM/5ViruBr4QQqdQJ3D2rcPsWcfnQWLY/PkX1IjFnEuTjwfAuocTY+ZAM8vXgrok9iAiwXJzr5SsH8viFjolMMBiEw5fdTGbJ0AV/8NoftmdRF5RVs35/vtUPnhBfTyIDvVV/YP24LYuv/7ZvEGErtSYzJXZUK8suquT819fx3tqDVr3vkw2HGPbMH6or6H6z9SjvrGk6KVNN4sP8uG1cV8IclKVuq7tR9G6WdRFJ7S5L2VIMBsErVw6yq43lu3MI8HJntAZa7Zbw3l8H8PF044ZR8Q69rptBcO2IzgzpHNL6yc3wzdZMFi5PZ82DE4i3opb1LWO72HxNa/hlxzEqa0xcPVx9CeozmbBwDaO6deClKwba9P4Ofp48f2l/q7+33SP8uXBANBW1JgJVnAm9ec0Qh+xFNEVxZS1l1UaHqNg6viaaE/P0kj3Ehvhw8xjH3MBnYjSZbZ7ev7U6A19PN6tvqFqTmSvf28R5CVHcMaHpLGQlWJ+RT4C3u8MdAcAD59mXJ3Hr2C70jQ60ygk0xmSWquYWfHbLcIcmHzXmrond7ZKH9vZw44rETla/b1yPcMb1sHwJ1FY83AyEOlgSuoEbPtpCgLcHX942QvVr6Y6gEftzy3Cw6N8p3l97gFdW7mPXk1Ntcgbf/WMUBTbUAvZwM9A1zJ8wf3W/7F/cqv6XuSWKK2oJ9HG3aWnK28P2qm7Xf7SFQB8P3rpmiE3vtxQtNHgAu2Yhy3Ydp6LGxMWDYmyKYJNSUlJlVC0yq8Zo5s3VGUzpE0n/WMfV7Wjgnkk9HCZ05wzho07D57cMd1gm35n0jwnmtrFdbUq4klLi7eFm8xTy5SsH2jQqayt8/fdRBj61wmpZAikls79NYXWa7bIY43uEM7KreuUciytqeeLnXex0sDRzAyazJLOwwqYZyQ/bsvls42Fs3TZ68PtULnlLHSlsqNOMemPVfvYc16ZvJ/WJdMisB6x3BA1ZFaVKG+LqjOrWgQen9sLX07pJ2vajJ5nx5gYOtKB9Ywlms/2RNc2RdbKC2d+mOFQorDFD40J49PzeeFo508ovqyE1q8iu3Ifbx3fl+pFxNr+/NXJL6yqiNeSPOJo/955g3IurSTtu/SPh/euH8uGNw2wOIJjeL4qbxsSrthkfHezDvgXTuXhw83IialJtNLEru5jiSts34y3FqjtDSjm+8b/tiT3HSrjl062k52jn40xmabV0cUW1CXc3QVSg7eu02UWVDHpqBb+kHLO5jZYoLK9h6+FCyqu1WcfuGRnArPHdrC7/Fx7gxcrZ53DZkFi7rl9jNKt2M/eIDGDnk1OZ2lcbbaxBnYJ5/tL+RFs5GzWZpd1qtJMTIrlhVLyqkWh1xY20WXZLzynlwjfWs+mA+hXZ9KWhesprjOQUV6GBXtgpRjz7Jy8sS7PqPWN7hPHTv8bYpbDZMdCbmYNiiA9TR+tvQGww6x+eyPAujs3ObEx5tZFcK0oNllTVYjSZMRiEXfH5JrMkccFK1YsAOTost4GIQG+uGt7Zqgf63uMljH9xNclHz9SxtJ7SqloyVZL7/mtfHq+s3Kd6iGpzdI/w5+1rhzAkLlj1a+mOoJ5h8aH8du84hxUAb4o7z+3GxN6Wb0qm5ZQo8iU1GARPX9yPoQ5Oo3ckl7y9gX8v3mXx+S8vT2fyK3/ZraXjZhDMntKTiX3UUVxdnJzNgiWa5F+e4kRJFftOWD6TNpkl3SP86WJjFFZjrv5gM3MX7bS7naZIOlzIJxsOaaImC3UKr+f372hVXpCtCGvX1+oF4aqklJrM8xMTE2VSUpIWl3Yqyqvr9OAvHBitmApkXmk1gT7uik+FP1x3kKOFFTw1s5+i7VrD7zuP4+/tbvHm2+r0XPafKGXWePVCapXg+d/TWJ2Wy/LZ2q3WXv/RFooqavn17rEOv/aqtBP4eLgzqps6G/Jqh/62xpGCco4XVykScCCE2CalbDJfq1VHIIQwAFcB1wLDgGrAC8gHlgLvSSkdVr5HLUfw3G97Ka02qiKtaylms+REaRXh/l6tLkeYzJJVabnEBPuQEG1/AZT1+/O57qMtfDNrpOJRLs/9tpf9uWV8rHBtgLaClJIjBRUEeLtrUs9YbbYeLkRKLFr6Sz56ku4R/prIZrdFHvphB6vT89j6b/urJrbkCCxZGloNdAPmAlFSyk5SyghgLLAZeEEIcZ3dVmqNUDhd2gZ+TT3GqOdWcTC/vNVz3QyCKQmRijgBgP4xQTx6fm86hSq/TzD3/D6aO4Fqo4m0nJJWazQbTWa+2nJE0VrOOSVVTHhpDb/sUGczXmuGxYda5ARqjGZu/3wbD/2Qqti1pZTsyi5mvxVLU5by1K97WLYrR/F2rWHW+K584oh7pzk1uoYfwEOJc5T6UVN9VGsyC8vlF5sOy7zSqhbP25CRJz9ad1BW1hgdZFnbZ9OBfBn38BL5V3pui+et3Zcr4x5eIpfvOq7o9b9PylRcedVsNst/fblN/r5TWVutpbLGKLccLJAniitbPTfl6Em5O7tYsWubzWY54Mnl8qHvdyjWppR1arOjn/tTvrwiXdF2tQR71EellLUAQojXRDOhCQ3n6NhHbIgv142Ma1Vo6o89uXyw7qDia5dVtSaSDhcqGpddVWvi/97bxMo9JxRr0xb6dAzk9asHt1pHeFyPcH69a6ziRUEuHxqr+GyrosZERm4ZBeWOq9/bFCdKqrjyvU2sSW+9VsjATsGKzWKhLlrq3euGcu/kHoq1CXUBFBsemcj9U3oq2q61VBtN/LHnhOqFcayJGioFfmmoHiaEmCqEUC+tz4HkllQx7dW1dmWQKkVdmcmWl4bmXZTAkrvHKl58/vttWVz+7iayTiqXnFRWbURKHFdgoxmCfDyYMTDaojDH/rFBijvZsmojq9JOKJpP4OflzvLZ47l2hHoJa5YQE+zDZ7cMZ1ILkVFbDxfy/O9pdimVNseobh2szmNoK0gJt32exNLU46pex+IniZTyMeBrYE29A7ifMyqJtVVqTGZiQ3zsisVXiju+3MbDPza/htoQLqrGpuOk3hF8eEMiHRTUHQrz9+K7f45iWr8oxdq0lczCCra3ELv+2OKdvLVanbiHtOMl3PJpElsOqp8c5Gjc3Qyc0zO8xe/k9iMn+XF7ltXZ3ZZQWWPilx3HyMhVbp/g70OFzPl+B/kWlM5UE28PN369ayw3j41X9ToWfypCiEnA7dSVkgwD7pFSrlPLMEcSG+LLhzcO0zThqYHZU3o2Ox3NL6tm9POrWLFbnQ2s6GAfJidEWi1z0VZ4YVkas79NafI1s1lSXGlUZcQK0C8miK9vH6modszy3TnM+jyJUpVstoaM3LIWv5f/OKcbf82ZoErN6lqzmXu/Seb3ncrdF8eLK1m3Px93LTNM6+kfG6R6jRRr7vh/A49LKdcLIfoD3woh7pdSKlMZXAeAMS3ISFfWmBgaF0K3CH/Vrn+koJy9x0sVG8F/teUIv6Qc46vbRji8gtaZ/GtC92ZF/QwGwRtXD1ZNt8bbw03xWPeyKiNHCyvwUeHhai3fbj3K55uOsPepaWcpiVbWmPDxdFNtgBHo7cHy+8bTVYEEtQZmDoph5iBtNIbOZN+JUrYcLOC6kXGqZZBbszQ0UUq5vv73ncB0YIEqVjmYV//Yx0wVVQytoarWxLYjJylsQlK6U6gv71w3lG7h6jmCb7Zmctd/t1NVq0y+oIfBgI+nm+ZOACAhOpBBnYLPOl5ZYzolLKemVMPRggo+Wn9IMcmCy4bGsuy+8U7RtzeN6cJv9447S0m0uLKWUc//qXoFtZ6RAU7RD2qwdl8ej/+8m5MV6s38Wu25FiKFjlNXX7jZc9oK0UE+JLQSTeIoDuWXc9k7G9mQkX/a8V3ZxXapYFrKdSPjWD57PF4K6aBfOawTn948XJG27KWq1sTqtFyOFpyuTfPDtkzGPL+KIwWt52/YQ3LmSZ5esocMO5VinZGYYB+6hfuf5UiNJjMXD4phgMp6/seLK3n1j31knVRGd+jJX3bz3l+OL1HZFFcM7UTSY5MJ8VVveciSu32VEOJuIcRpFSiEEJ7AKCHEZ8CNqljnIK4c1onnLtUuo7gxXcL8+OjGREafsYzw8I+p3Pqp+tIazd3Q7YGqWhM3f7qV5WesZY/vGc4D5/WiswrJdI2Z1CeSLY9OoneUMoOOO77cxrtO8rAymsz8nJJNalbRacc7+Hvx5Iy+9I1W1xGUVhl57c/97MouUaS97KJKq+tXqEWQrwdh/l6q3pOWLNrtB0zAT0KIjkAR4A24ASuAV6WUyapZ6GJ4e7g1GcP+5jVDKHRQvPi6/Xnkl1VzyWD75JcBZr61gQv6RzmFZk+wryc/3jGa7mcsrcV18OOf56hvn7+XO/4KR6Y5i7s2CMHDP6Zy7Yg4BsQGA7AjswhvDzd6Rakv5Ng93J/UJ85TTLrigxucq4T6138fJSrQm3OtEKW0BktmBMOklG9T953rTN1y0BApZZyU8va27gTMZknigj/4aP0hrU05RUZuGWvST89p6BLm5zB10O+Ssnhl5T672zGbJfEdfOng5zz6OkPjQghqNMX+YO1BVeQJmmPjgXxeXpGuSFvvXDeUfzjAgVmCwSBYdu945kz9X33o539PY9YXSZgdkENiMIh2rV/03l8H+Ck5W7X2LXEEfwohNgGRwA1ANKBNOSQVqDGZmd4vStGIA3v5ZMMh7qsPczyUX87cRankFKu/P9DAExclsHL2OXa3YzAIXrtqMJcNtX9moRTpOaV8l5QJ1FX3enllOiv3Oi7rOSWziE83Hra6AFFbID7M77Tw0LevHcLrVw22qR6xLSQfPcl93yTb3bdpOSVc9+EWzSrqNcXiO8fw2lWDVGvfEomJB4HrqFse6gI8DuwSQuwWQnyrmmUOwtvDjacv7qfalMsWZo3vyvf/GIWUkp3ZxSxJPY7BgQERYf5eqsR7OwMrdufw0A+pVNaYiAjwZtMjk1QtJXkmt4zpwo5559mdvLjpQAEXvbFedekBa0jLKeHNVftPRUWF+HkysIkoLbUoqqhl08ECu8t2VtaYKK8x4u7Im64Vgn09Vd0jsLgegRCip5RyX6O//YF+UsrNahnXFErLUEspnX5jtKrW5PAH80frDxHk48Hldozml6Ye54Vlafz39hHEhqi7EWspBWXV1JokkYHqbr6pzd+HCnlrdQYvXDaAqCD1C5dYwvdJmcz5IZVvZ43kg3UHeWR6H7qrmPNyJmazRAjtqrWpyf4TpXy/LYt/jO9qs6pASzLUFg9LGjuB+r/LqJOhVgQhhBuQBGRLKS9Uqt3W+HzTEV5ZuY+/5kwg2Fc5aQV7+CEpk2d+20tRRS3RwT7MmdrL4QW0f9t5nI5B3nY5glA/TwZ1CibESfoVYN3+fBYuTye7qBJvdwPPXNKPy4Z2cqgNX2w+QtbJCuZO72NzG8O7hDK8i3OE5TYgJXQM8ub/3t+MQdRpADnSEThqCUoLFm3P5v21B/lg7UFVngnOpCVwL7AXcGhAf8/IAC4eFK16CrelLE7O5rGfd1FVWze9zi6qPFWKz5HO4L+3j7C7Utmobh1UqxxlC4uTs5m7KJXK+r6tMpp5bPFu3AwGh/btgdwy0nMct0HtCBYnZ/PEL7uprE9ENEt4afk+Ovh5ObRvf0rOYtH2bD6/ZbjNM4PnfttLflkNL185UGHrbGNxcjafbKwLZpGo80xwikUwIUQscAHwoaOvPapbB+bP7Oc0o4mFy9NPOYEGKmtNLFyuTKSJpShdrtIZWLg8/ZQTaECLvn3iogS+njXSrjbu+TqZ+79LUcYgBajr29Oz0bXoW6NJYjRJuwoLebkb8PF0ikcj4JhngrPMCF4FHgKaDDgWQswCZgF07ty5qVNspsZoxlOhLFolONbMRldzx9Wi2mji8cW7GNM9zGbNlSve3UhcBz9eusI5RlbO0rdKrGF3DffDzYnWwp2lb69I7MQVifYt9d1/Xq/WT3IgjuhbzZ+AQogLgVwp5bbmzpFSvi+lTJRSJoaHK6feCDD5lb94WMHSefbSnK66o/XWvdzd2JldYlfY6oReESTGhSholX04S98CzF2UyovL0mx+/32Te3L3JGWLsdiDM/Vte8MRfau5IwDGADOEEIeBb4CJQogvHXXx60fGMbGFghqOZs7UXmepSfp4uJ2WqOMofr93nF0JS3ee252rhis7g7MHZ+pbKevWe9sLztS3z/22l+s/2mLTe/PLqpn08hrVpN5twRF9q/nSkJRyLjAXQAgxAXhQSnmdo65/+/iujrqURTRs/ixcns6xokrNoobspSGb1Fn2XsC5+vb5ywbY/N6M3DKuen8TC68YyLm9nGMQ40x9Gx3sQ7XRbFNoeK3JTK+oAIJ8nCN4BBzTtxbnETiCRo6g2fBRJfMIqo0mTGbZbgux2EvWyQru+yaFOyd2t/qBs/VwIdd+sIXPbx3OyK7OEznkbNjysDpaUME7f2Vw4+h4xQTsdNo/LeUROMPS0CmklGscmUOwdl8+CfOWn6WYqFNHneIhNq1hdPDz5Oax8YoXbG8v1BjNTH9tHW+vsV49tHMHX567dIDuBFqhxqhM3QdXwKkcgaPpGu7HQ9N6ERfqPDpDzoS3hxvf/3O0TfIbXcP9mTu9DzH6ZmGTeLobGNQpiNgQ6/vHmWbxzsr/vbeJ+761Xg/z1T/2Me3VtS7Xxy69JtIt3J9/TeiutRlOT8NNYc0SRmWNCW8PQ7tM91eK5y61bZ/g0Z92sf3ISZbPHq+wRe2Haf2i8LNhyTeugy+J8SEu9711aUeQW1qFv5e7vkfQApsPFnDnV9v5/NbhVhUXuf+7FA7ll7PsPv1h1RJGkxmTlFYl8I3sGkq0k+gLOSs3j+li0/suGRyrSB2OtoZLPwHv/TqFWpOZH+4YrbUpTkunUF/O7R2Bp5X1YC8aGE1JpXo1VtsDmYUVnPeftSy4uJ9VUt3OUlTd2amoMVJdaybEz3m0rpwVl3YEt4ztgtnF1gKtJSbYx6bM4PP7d1TBmvZFTLAP147obLUwm7NlwzsjRpOZxAV/cM3wzjx2YYJF75FSMuTplcwa3407JjhHwR9H4dLfpikJkUztG6W1GW2CkirLR/dmsyS/rNohlanaMgaD4LELE6zS7K+oMdLzsd+dqqKeM+LuZuDfF/Rhen/L7+8ak5lLh8TSu6P6pTWdDZd1BNVGExm5ZVSdIZSlczZfbD7CwPkrKKqosej8nJIqEhf8wTdbM1W2rO0jpSTrZAXVRsu+hyazZPbkngzuHKyuYe2Aa0fEWVXe1cvdjccvTHCaJD1H4rKO4EBuOZNf+YtVabmtn+ziJMaF8OB5vbB0Fc3X0435M/oyvIvz6Aw5K2v35zP2hdUkHy2y6PwAbw/undyDIZ31vm0Nk1mSllNCXmm1xee7WthoAy7rCDoGefPq/w3SR1YW0KdjIHee293iTbdgX09uHB1P9wjXm2Jby6DYYJ6a2ZcuFtbMrqgxWjx7cHVyS6uY9uo6lqYes+j8//59lIR5y8kvs8xxtCdc1hGE+Hly8eAYOgbpCU+W0LCUZgkFZdXkl1W77OjKGoJ8PbhhVDyRgZaFg368/hC9H1+mL2laQMcgH16/ejBT+1m2T9A7KoBrRnR2qop6jsJlHcHRggoO5jlP4W9n5+kle7jkrQ0WbQC/s+YA415Y7QCr2gelVbVsyMi3yHGO6taBh6f1dngN67bKjIHRFg/2hsWH8viFCbg5kVCio3BZR/D6qv1c+6FtUrWuyJWJnVh4xQCLwm0vGhjNM5f0c7nsTFtZnHKMaz/cQtbJ1guNDI0L5Z92SIO7GsWVtfy+8zjFFa1HvVXUGF12FutU6qOWoJT66J5jJeSWVjHBBSMEdJyLEyVV7D9RRmJ8SKsj/ZziKkL8PNplKVE1SDpcyOXvbuL964dyXiuh4hNfWsPATsH85/8GOcY4B9OS+qjLJpQlRAeSgK7eaA1HCsrJL6thaCtVx/YeLyE6yIcgX+fRdHdmIgO9Ld4jOP/1dZzfP4oFF/dX2ar2Qf/YIH7612gSolu/128eE0+Ui+4ZuuTSkJSS9fvzyS21vQyjKzLv5908umhni+eYzJIL31jPB+sOOsiq9kFGbhm/7mg5ukVKySPTe+sSE1bg5e7G4M4hFs2grh8Vz5SESAdY5Xy4pCMoqTRy3Udb+CXFsrAynTrmTO3F61cPbvEcKSVvXzuECwfqEhPW8MO2LO7/LqXFaCAhBFcmdmJYvOVJUjpwIK+Mt9dkYDQ1X5+gqtZEcUWty+4RuKQj8PY08O2skUyzMKxMp45+MUH0imo5N8DdzcDUvlF60RQruWl0PGvmnItXCxpCxZW1HCkob/GBpnM2u7KLeXFZOofyy5s9Z+OBfAY+tYLkzCLHGeZEuKQj8HJ3Y0TXDsSG6NWzrGV1Wi6bDhQ0+/qJkip2ZhVTqz+srCIqyJuYYJ8WI63+3HuCcxau4WhhhQMta/tMSYgkZd4UekQ2P4jpFu7PYxf0oauFiX3tDZd0BAfzyli/P18fWdnAs7/tbXH9f2nqcS56cz2lVUYHWtU++HPvCb5Lal6faVh8KAsvH0C0XvXNKnw93QluJUksroMft43r2up57RWXjBpanHKMN1btZ9+C6Vqb0uZ4/4ZEIgO9mn19Wr8oYkN8CNEjhqxmccoxdh8r5srETk2+3inUV68BbSN/7ctjY0Y+c8/v0+TrOcVV+Hi6EeTjmt9bl3QE143szPgeYXhYWWxFh1Y1caKDffQRq408PbMv/l7N35L7TpTi7+Wu968N7D5WzI/bs7h3co8mKxI++P0OyqqNLL5zjAbWaY/LJpTp2EZVrYkvNx+hX0wQI7t2OOv1LQcL6ODvZXWxFZ3WufCNdYT5e/HpzcO1NqXNUWM04+Emmt2DWbsvj1qTmUl92m/4aEsJZS45JF626zh7jpVobUabxNPNwGt/7GftvrwmX3/g+x28uWq/g61qP7y9JoNv/j7a5GvzLuzL3RO7O9ii9oGnu6HFjfjxPcPbtRNoDZdcGprzfSqXDY3lyRl9tTalzWEwCNY/MrHZtdR3rxvaYgikTsusScsjNtSHq4Z3Puu14V30/AF7+Gj9IbJPVjLvotNLV1YbTRzMKyeug2+Ty0augOb/ayFEJ+BzIBKQwPtSytfUup6UkqX3jMPDXRdEs5WWNtT6xQQ50JL2x39vH4F7E3tXpVW17D5WQkJ0IIHerrmhaS/Hiio5lH+24vCRggqmv7aON64ezEUDozWwTHucYehmBB6QUiYAI4E7hRCWVZu2ASEEnTv46nUI7CCnuIq5i3aSmlV02vG80mqW786xSOlRp2macgJQJ5J41fub2eGiCU9K8PiFCXzSxP5KZKA3b10zhMR41636prkjkFIel1Jur/+9FNgLqCamcqSgnO+SMimu1B9WtuLpbmBp6jEOF5ye2LT96En+8cU2Mk/qCU+2UlVr4p6vk/kpOeu0432iA/nqthEMiAnWxrB2TJCPBxcM6OjSg0PNHUFjhBDxwGBgyxnHZwkhkoQQSXl5TW9SWsqWg4U89EMqJbojsJlQP09S5p3HjDOm0WO7h7Hk7rF6xJAdeLkbOFJYwcny07+fgd4ejOkepiu62sn936bw7G97Tzt2KL+ctBzXDh7RfI+gASGEP/AjcJ+U8rRPRUr5PvA+1IWP2nOdmYOjGdm1gx6LbSeGJqo4+Xm563sEdiKE4OcmYtlTs4qoNZkZGqdvGNuDn5c7vp6nK5G+u+YAq9Nz+fvfkzWySnucwhEIITyocwJfSSkXqXktL3c3OnfQszPtJfnoSV5YlsbCyweeynZduy8PIWBcj3CNrWt/vLU6g0P55ayYfY7WprRpnr6431nHbh/fxWU3iRvQ3BGIuuDej4C9UspX1L7ezynZ+Hm6M9lFdceVwsvdjYoaE8WVtTQIIry5OgOk7gjsJbOwgju+2sbsyT1PxbY/dkGCvq+lIGazPDWr7R4RQPeIllV12zuaOwJgDHA9sFMIkVJ/7FEp5W9qXOzt1Qfo3MFXdwR2khAdyC93jT3t2DvXDqGipnk9fR3LCA/wItjH87QIok6hvjStQKRjDTVGM9NeXcslg2O4e1IPAFan59I7KsClN4s1dwRSyvWAw4L6f7l7DJX6w0oVOvh7cbbohI61eHu48eVtI079XWsysyT1GIlxobronJ14uhsY1yOMbvUBDaVVtdz8yVYemd6bf57TTWPrtMOpooYcgZe7W5uWmjWZTAwePJgLL7xQa1NYtD2LsS+soqrWRGlVLZ9tPMyRguaLf+hYh9ksMZslJ0qqmP3tDjYeyNfapHbB/Jn9OL9/XQU9bw83Fv1rtMvvEbiUI8gtqeL1P/c7xcPKZLJtVvLaa6/Rp0/TUrqOJjLQm8S4EEqrjBwpqOCJX3az93ip1ma1CzZk5DNw/grSckqJDPTmzwfO4bwEvaKeUlTVmqiqNeHhZmBI5xBiXDyK0KUcwcH8cl5ZuY/jxdoUrb/iiiv4xz/+wciRI3nuueesfn9WVhZLly7ltttuU8E66xnTPYxXrxpMeIAXfaMDSXpsMuN7hmltVrsgPsyPGYOi8fIw4OFmoFu4PyF+bXcm60wcLaig/5PLWZp6nAN5ZaxKO0GN0bWLVGm+R+BIRnbtQPqCaRhaUCFUk507d3LllVeyefPm046PGzeO0tKzR9IvvfQSkyf/L7b5vvvu48UXX2zyXC2pMZrxdDcQ5t98wRod64gJ9uGZS/oDkJJZxKH8MmYOjGkyf0PHOmJDfJg1viu9ogJYsuM4//ljH+kLpmltlqa4lCOAuj0CLaiqqqKwsJB58+ad9dq6detaff+SJUuIiIhg6NChrFmzRgULbePZ3/ayNPU4z1zSj8yTlVw/Mk5rk9oV+WXV/JySzXdbM7l4kGrKKy6FwSCYM7U3UOdwJ/QK1+y54Cy4lCP4KTmLgrIabhvX1eHX3r17NyNGjMDd/ewut2RGsGHDBn755Rd+++03qqqqKCkp4brrruPLL79U3faWGBYfip+nO4uTs9l6+KTuCBTkkw2HmP/rHjY+MpGbR3dpUU9fxzrMZsmhgnJign0Y2ClYa3M0x6UqlN37TTIZuWUsvWecwla1zqeffsr+/ft55pln7G5rzZo1vPTSSyxZskQBy5TBbJaUVhl1LRwFSc8pZX1GPpcPidX7VWFWp+dy8ydbuX5kHJcPjXUJZ9BShTKXmhG8dtVgTGZtHN/OnTsZPrx9lhg0mswUltcQEeittSntil5RAfSKCuCTDYcYEBuk6wwpyJDOIbx42QAe+jEVwCUcQUu4zIxgcXI2C5enc6yokuhgH+ZM7cXFg+vWXHNycvj000+5++678fNruTi7q2IymVi4cCFXXXUV8fHxp7026eU1HMgrR8BZfatjO4uTs3lhWRrHi6sI8HLn6Yv76f2qEI2fB5GB3jwyvXe771uXr1m8ODmbRxalkl1UiQSyiyqZu2gnn6xM5oEHHiAhIYHjx4/j6amH5zWHwWCgsrKSoUOHMmvWLA4fPgzU9e3Rwrr6A437dnFytnbGtgMWJ2czd9HOU6HOpdVGvV8VoqFvG54HOSVVLt+3LjEjGPP8KrKLKk87lvfz81Tu30y/hD4MGTJEnwlYSFVVFSkpKezatYtx48ZROfnRs/oW6qIxNjwyUQML2wdNfWdB71clcNW+dfk9gmNNfOgeHTpTdWQHNTU1hISE0L17dw0sa3tkZmZiNBrx8fGhX79+/NxE30LTfa5jOc31n96v9qP37dm4hCOIDvY5awQQPPYa+ky/kds7ZrFgwQK6du3K4sWL8ffXq2s1hdFo5KqrrmLTpk08/PDD3H777fj4+LC1mdGVXvjHPpr6zjYc17EPvW/PxiX2COZM7YWPx+kJIz4ebjx8fl9uueUW0tPTuffee/H21qNemsPNzY0bb7yRjIwM7rnnHnx86m6a5vp2ztReWpjZbtD7VT30vj0bl9gjgJajhnTsQ+9bddD7VT1csW9b2iNwGUego6Oj48q4fPiojo6Ojk7z6I5AR0dHx8XRHYGOjo6Oi6M7Ah0dHR0XR3cEOjo6Oi5Om4saEkLkAUfsaCIMaCtVwNuSrdC27NVtVY+2ZG9bshXsszdOShne1AttzhHYixAiqbkQKmejLdkKbcte3Vb1aEv2tiVbQT179aUhHR0dHRdHdwQ6Ojo6Lo4rOoL3tTbACtqSrdC27NVtVY+2ZG9bshVUstfl9gh0dHR0dE7HFWcEOjo6OjqN0B2Bjo6OjovjMo5ACDFNCJEuhMgQQjyitT0tIYToJIRYLYTYI4TYLYS4V2ubWkMI4SaESBZCLNHaltYQQgQLIX4QQqQJIfYKIUZpbVNzCCFm138HdgkhvhZCOFXRDCHEx0KIXCHErkbHQoUQK4UQ++v/DdHSxgaasXVh/fcgVQjxkxAiWEMTT6Mpexu99oAQQgohwpS4lks4AiGEG/AWMB1IAK4WQiRoa1WLGIEHpJQJwEjgTie3F+BeYK/WRljIa8AyKWVvYCBOarcQIga4B0iUUvYD3ICrtLXqLD4Fpp1x7BHgTyllD+DP+r+dgU8529aVQD8p5QBgHzDX0Ua1wKecbS9CiE7AecBRpS7kEo4AGA5kSCkPSilrgG+AmRrb1CxSyuNSyu31v5dS96By2qoZQohY4ALgQ61taQ0hRBAwHvgIQEpZI6Us0tSolnEHfIQQ7oAvcExje05DSrkWKDzj8Ezgs/rfPwMudqRNzdGUrVLKFVJKY/2fm4FYhxvWDM30LcB/gIcAxSJ9XMURxACZjf7OwokfrI0RQsQDg4EtGpvSEq9S98U0a2yHJXQB8oBP6peyPhRC+GltVFNIKbOBl6gb+R0HiqWUK7S1yiIipZTH63/PASK1NMYKbgF+19qIlhBCzASypZQ7lGzXVRxBm0QI4Q/8CNwnpSzR2p6mEEJcCORKKbdpbYuFuANDgHeklIOBcpxn6eI06tfWZ1LnvKIBPyHEddpaZR2yLj7d6WPUhRD/pm5J9iutbWkOIYQv8CgwT+m2XcURZAOdGv0dW3/MaRFCeFDnBL6SUi7S2p4WGAPMEEIcpm7JbaIQ4kttTWqRLCBLStkww/qBOsfgjEwGDkkp86SUtcAiYLTGNlnCCSFER4D6f3M1tqdFhBA3ARcC10rnTqzqRt2gYEf9/RYLbBdCRNnbsKs4gq1ADyFEFyGEJ3Ubbr9obFOzCCEEdWvYe6WUr2htT0tIKedKKWOllPHU9esqKaXTjlqllDlAphCiV/2hScAeDU1qiaPASCGEb/13YhJOurF9Br8AN9b/fiPws4a2tIgQYhp1y5ozpJQVWtvTElLKnVLKCCllfP39lgUMqf9O24VLOIL6zaC7gOXU3UjfSSl3a2tVi4wBrqdudJ1S/3O+1ka1I+4GvhJCpAKDgGe1Nadp6mctPwDbgZ3U3a9OJYkghPga2AT0EkJkCSFuBZ4Hpggh9lM3q3leSxsbaMbWN4EAYGX9ffaupkY2ohl71bmWc8+EdHR0dHTUxiVmBDo6Ojo6zaM7Ah0dHR0XR3cEOjo6Oi6O7gh0dHR0XBzdEejo6Oi4OLoj0NHR0XFxdEego6Oj4+LojkBHRwHq60dMqf99gRDiDa1t0tGxFHetDdDRaSc8ATwlhIigTi12hsb26OhYjJ5ZrKOjEEKIvwB/YEJ9HQkdnTaBvjSko6MAQoj+QEegRncCOm0N3RHo6NhJvdTyV9TVDiirV7TU0Wkz6I5AR8cO6ouFLKKuxvRe4Gnq9gt0dNoM+h6Bjo6Ojoujzwh0dHR0XBzdEejo6Oi4OLoj0NHR0XFxdEego6Oj4+LojkBHR0fHxdEdgY6Ojo6LozsCHR0dHRfn/wF1/izWfx+NOwAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "N = 15; a = 13\n",
        "\n",
        "x = [i for i in range(N)]\n",
        "y = list(map(lambda n: fastExp(a, n, N), x))\n",
        "\n",
        "r = 4\n",
        "             \n",
        "plt.plot(x, y, linestyle='dotted', marker='o')\n",
        "plt.xlabel(\"$x$\")\n",
        "plt.ylabel(\"$f(x) = 13^x$ mod $15$\")\n",
        "plt.annotate(text='$r=4$', xy=(r/3, 1.2))\n",
        "plt.annotate(text='', xy=(0,1), xytext=(r,1), arrowprops=dict(arrowstyle='<->'))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gjGFfF94RuaC"
      },
      "source": [
        "## Lagrange's Theorem\n",
        "\n",
        "Let $H$ be a subgroup of $G$ and elements $a, b \\in G$. Then\n",
        "$$\n",
        "\\begin{align*}\n",
        "    1. &\\quad  a \\in aH\\\\\n",
        "    2. &\\quad  aH = H \\text{ if and only if } a \\in H\\\\\n",
        "    3. &\\quad aH = bH \\text{ if and only if } a \\in bH\\\\\n",
        "    4. &\\quad aH = bH \\text{ or } aH \\cap bH = \\emptyset \n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "If $G$ is finite group and $H \\leqslant G$, then $|H|$ divides $|G|$. Moreover, the number of distinct left/right cosets of $H$ in $G$ is given by $|G|/|H|$.  \n",
        "\n",
        "\n",
        " Let $a_1 H, ..., a_d H$ be distinct left cosets of $H$ in $G$. Then, by Lemma 1, they are disjoint and\n",
        " \n",
        "$$\n",
        "    G = a_1H \\cup \\dots \\cup a_dH\n",
        "$$\n",
        "\n",
        "And moreover,\n",
        "$$\n",
        "\\begin{align*}\n",
        "    |G| &= |a_1H| + \\dots + |a_kH|\\\\\n",
        "        &= d|H|\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "## Fermat's Little Theorem\n",
        "\n",
        "An important result for the purposes of this notebook is Fermat's Little Theorem, which states the following\n",
        "\n",
        "$$\n",
        "    a^{p-1} \\equiv 1 \\text{ mod } p\n",
        "$$\n",
        "\n",
        "where $p$ is a prime and $0 \\leq a \\leq p - 1$.\n",
        "\n",
        "We can prove this by reconizing that $\\mathbb{Z}_p$ generates a group under multiplication modulo $p$, $G = \\{1, 2, ..., p - 1\\}$. Now let $d$ be the order of an element $a$, i.e, $d$ is the smallest positive integer such that $a^d \\equiv 1 \\text{ mod } p$, and it follows that the numbers $1, a, a^2, ..., a^{d - 1}$ are a subgroup of order $d$ of $G$.\n",
        "\n",
        "Then it follows by Lagrange's Theorem that $d | p - 1$, and $p - 1 = dm$ for some m integer $m \\geq 0$.\n",
        "\n",
        "$$\n",
        "    a^{p-1} \\equiv a^{dm} \\equiv (a^d)^m \\equiv 1^m \\equiv 1 \\text{ mod } p\n",
        "$$\n",
        "\n",
        "And our result holds.\n",
        "\n",
        "## Euler's Theorem\n",
        "\n",
        "Now we can prove a generalization of Fermat's Little Theorem which states that \n",
        "\n",
        "$$\n",
        "    a^{\\phi(n)} \\equiv 1 \\text{ mod } n\n",
        "$$\n",
        "\n",
        "where $n$ is a positive integer and $\\gcd(a, n) = 1$.\n",
        "\n",
        "Again, by reconizing that $\\mathbb{Z}_n$ with multiplicative inverses generates a group under multiplication modulo $n$, $G = \\{1, 2, ..., \\phi(n)\\}$. The subgroup generated by an element $a$ of order $d$ consisted by the elements $1, a, a^2, ..., a^{d-1}$, and since $a^d \\equiv 1 \\text{ mod } n$, by Lagrange's Theorem we have that $d | \\phi(n)$, and $\\phi(n) = dm$ for some m integer $m \\geq 0$.\n",
        "\n",
        "$$\n",
        "    a^{\\phi(n)} \\equiv a^{dm} \\equiv (a^d)^m \\equiv 1^m \\equiv 1 \\text { mod } n\n",
        "$$\n",
        "\n",
        "Hence our result holds."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fmeBYW17RuaC"
      },
      "source": [
        "# A (Qu)bit of Quantum Computation\n",
        "\n",
        "In Classical Computers, those that some of us have at home, works under fundamental information unit of $0$'s and $1$'s bits, physically represented by low and high voltages on chips transistors. \n",
        "\n",
        "Differently Quantum Computers works under a basic unit of quantum information call qubits, represented on the computational basis $|0\\rangle$ and $|1\\rangle$.\n",
        "\n",
        "$$\n",
        "|0\\rangle = \\begin{bmatrix}\n",
        "    1 \\\\\n",
        "    0 \n",
        "\\end{bmatrix}  \\quad\n",
        "|1\\rangle = \\begin{bmatrix}\n",
        "    0 \\\\\n",
        "    1 \n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "We can physically interpretate qubits as hydrogen molecules, where the ground state is represented as the state $|0\\rangle$ and the excited as the state $|1\\rangle$.\n",
        "\n",
        "A qubit can be mathematically represented as a linear combination\n",
        "\n",
        "$$\n",
        "    |\\psi\\rangle = \\alpha|0\\rangle + \\beta|1\\rangle\n",
        "$$\n",
        "\n",
        "with $\\alpha$, $\\beta \\in \\mathbb{C}$ and $|\\alpha|^2 + |\\beta|^2 = 1$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "FbE2QchgRuaD",
        "outputId": "3605954f-2fb1-4a95-da9c-887e5d35e589"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "State_0  |x> =  [1.+0.j 0.+0.j]\n",
            "State_1  |x> =  [0.+0.j 1.+0.j]\n"
          ]
        }
      ],
      "source": [
        "#define a 1 qubit state |0>\n",
        "sv_0 = Statevector.from_label('0')\n",
        "print('State_0  |x> = ', sv_0.data)\n",
        "\n",
        "#define a 1 qubit state |1>\n",
        "sv_1 = Statevector.from_label('1')\n",
        "print('State_1  |x> = ', sv_1.data)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KeB-7NPlRuaD"
      },
      "source": [
        "Quantum Mechanical Phenomena as superposition and entanglement can be used to create efficient problem solutions. And we do that by applying linear unitary transformations on quantum states.\n",
        "\n",
        "One of the most important gates in Quantum Computing is the Hadarmad Gate $H$, a recursevely constructed matrix of order $2^n$.\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "H_0 = \\begin{bmatrix}\n",
        "                       1\n",
        "                       \\end{bmatrix} \\qquad\n",
        "H_1 = \\frac{1}{\\sqrt{2}} \\begin{bmatrix}\n",
        "                       1 & 1\\\\\n",
        "                       1 & -1\n",
        "                       \\end{bmatrix} \\qquad \n",
        "H_n = \\frac{1}{\\sqrt{2^n}} \\begin{bmatrix}\n",
        "                       H_{n-1} & H_{n-1}\\\\\n",
        "                       H_{n-1} & -H_{n-1}\n",
        "                       \\end{bmatrix}\n",
        "\\end{align*}\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AOyBsizTRuaD"
      },
      "source": [
        "Which can be used to put a state $|\\psi\\rangle$ in superposition, i.e, to take a state from the computational basis to the $|+\\rangle$ and $|-\\rangle$ basis, where we have $\\frac{1}{2}$ probability of measuring $|1\\rangle$ and $\\frac{1}{2}$ of measuring $|0\\rangle$. And we define the operation of applying a Hadarmard gate into a quantum state as it follows. Here we're going to assume $H = H_1$\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "\\\\H|0\\rangle = \\frac{1}{\\sqrt{2}} \\begin{bmatrix}\n",
        "                                   1 & 1\\\\\n",
        "                                   1 & -1\n",
        "                                \\end{bmatrix} \n",
        "                                %\n",
        "             \\begin{bmatrix}\n",
        "             1 \\\\\n",
        "             0\n",
        "             \\end{bmatrix}\n",
        "             =\n",
        "             \\frac{|0\\rangle + |1\\rangle}{\\sqrt{2}}\n",
        "             =\n",
        "             |+\\rangle\n",
        "\\\\\\\\H|1\\rangle = \\frac{1}{\\sqrt{2}} \\begin{bmatrix}\n",
        "                                   1 & 1\\\\\n",
        "                                   1 & -1\n",
        "                                \\end{bmatrix} \n",
        "                                %\n",
        "             \\begin{bmatrix}\n",
        "             0 \\\\\n",
        "             1\n",
        "             \\end{bmatrix}\n",
        "             =\n",
        "             \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n",
        "             =\n",
        "             |-\\rangle\n",
        "\\end{align*}\\\\\n",
        "$$\n",
        "\n",
        "Which can be generally seen for an arbitrary state on n-qubits $|x\\rangle$ as\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "H|x\\rangle &= \\frac{1}{\\sqrt{2^n}}\\sum_{k \\in \\{0, 1\\}^n}(-1)^{\\langle x, k\\rangle}|k\\rangle\n",
        "\\end{align*}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2IIrcThPRuaE",
        "outputId": "0977386e-6698-4732-8f5c-63e28b917cce"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "State_0 H|x> =  [0.70710678+0.j 0.70710678+0.j]\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHMAAABOCAYAAAATpymVAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAACnUlEQVR4nO3csWsaYRzG8eeq4JDJpYqBelB0cpQOR0EH65ClcPkHXDt0cgkUFSR16tatZMiWpdGWgAS6KAcZgv0LpGCGQOhihx4WGrgOpQGJ0DNY3jdPnw/c8h7c/eSL53mIThRFEYTCA9MDyOYoJhHFJKKYRBSTiGISUUwiiklEMYkoJhHFJKKYRBSTiGISUUwiiklEMYkoJhHFJKKYRBSTiGISUUwiiklEMYkoJhHFJJI0PYAp/QlwOTdz7u004Jc3f9z/NublHPjy1fQUm6XLLBHFJKKYRBSTiGISUUwiiklEMYkoZkzv96s4/7Afe90EK2MOBgOUSiWkUikUi0UcHByg0WjAdV3To1nNusd5p6en2N3dRa1WQ6/XQxiG6HQ6WCwWSCQSpsezmnUx2+02XNfFcDhEMvl7PM/zUCgUkMvlDE9nN6tihmGIyWSCZrN5ExIA8vk8PM/DbDYzNxyA84+v8Xn4Zmnt54/veFSqGZpomVWfmfP5HFEUIZvN3tq3am0Vx3FibePxaO35njx/hRfvvi1tueLTtY8zHo9iz7kOq2Km02k4joOrq6tb+1atyTKrYm5tbaFcLuP4+BjX19c36xcXFzg7O4t1jCiKYm2VSvUfvYq/q1Sqsedch1UxAaDb7WI2m2FnZwcnJyc4OjpCvV5HJpMxPZr1HBv/orTf76PVamE6nSKfz2Nvbw9BEGA0Gm3sJujtJ3O/NHj8EHj5bPPHtepu9g/f9+H7/tJaEASGprk/rLvMyt0pJhErL7OrHB4emh7BenpnElFMIopJRDGJKCYRxSRyb76abNp2mu/cVj6blbvRZZaIYhJRTCKKSUQxiSgmEcUkophEFJOIYhJRTCKKSUQxiSgmEcUkophEFJOIYhL5Bdppyx+s9Ww/AAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 133.526x84.28 with 1 Axes>"
            ]
          },
          "execution_count": 14,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#build a circuit with the H gate\n",
        "mycircuit = QuantumCircuit(1)\n",
        "mycircuit.h(0)\n",
        "\n",
        "#apply the circuit into |x>\n",
        "sv_0 = sv_0.evolve(mycircuit)\n",
        "\n",
        "print('State_0 H|x> = ', sv_0.data)\n",
        "mycircuit.draw('mpl')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Xup_kKrIRuaE"
      },
      "source": [
        "### A Tensor Disclaimer\n",
        "\n",
        "Given two matrices,\n",
        "\n",
        "$$\n",
        "    A = \\begin{bmatrix}\n",
        "    a_{00} & a_{01} \\\\\n",
        "    a_{10} & a_{11} \n",
        "    \\end{bmatrix}  \\quad \n",
        "    B = \\begin{bmatrix}\n",
        "    b_{00} & b_{01} \\\\\n",
        "    b_{10} & b_{11} \n",
        "    \\end{bmatrix} \n",
        "$$\n",
        "\n",
        "we define the kronecker (tensor) product of $A \\otimes B$ as\n",
        "\n",
        "$$\n",
        "    A \\otimes B =  \\begin{bmatrix}\n",
        "a_{00} B & a_{01} B \\\\\n",
        "a_{10} B & a_{11} B \n",
        "\\end{bmatrix}  \n",
        "$$\n",
        "\n",
        "Some useful examples and notation for qubit strings\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "        |0\\rangle_0 \\otimes |0\\rangle_1 \\otimes \\dots \\otimes |0\\rangle_n & = |00 \\dots 0 \\rangle \\\\ & =|0\\rangle^{\\otimes n}\\\\\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Which is a vector of dimension $2^{n}$.\n",
        "\n",
        "Analagously for matrices,\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    H \\otimes H \\otimes \\dots \\otimes H = H^{\\otimes n}\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Which is a matrix of dimensions $2^{n} \\times 2^{n}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z6KOWUgXRuaE"
      },
      "source": [
        "# Shor's Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3UAltgtNRuaE"
      },
      "source": [
        "On the beggining of this article we saw why factoring is such a difficult problem, and now we are going to introduce an algorithm that solves this problem efficiently. However, there's a catch, of course: this algorithm needs a quantum computer to execute it.\n",
        "\n",
        "Invented by the MIT mathematician Peter Shor in 1994, Shor's algorithm is polinomyal-time quantum computer algorithm that solves the problem of integer factorization. In other words, the problem lies in the idea of: Given a integer $N$, such that $N = pq$, where $p$ and $q$ are large prime numbers, our goal is to find these factors efficiently. \n",
        "\n",
        "Classically as we have already discussed this problem would take an exponential amount of time to run in terms of the input lenght. While the quantum solution that we're going to discuss has a time complexity of the order of $O(N^3\\log_2 N)$, where $N$ is the number of qubits, which can be even faster with proper optimizations. Therefore, we have an exponential speed-up when compared with classical solutions with the most clever known sub-exponential running time complexity of $O(e^{1.9(N^{1/3})(\\log N)^{2/3}})$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9_gggO_aRuaE"
      },
      "source": [
        "<img src=\"images/shor_circuit.png\" style=\"width:1000px; height:180px\"/>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CGCEnwH5RuaF"
      },
      "source": [
        "## Setting up periodicity\n",
        "\n",
        "The algorithm lies on the idea of finding a non-trivial square root of 1 modulo $N$, where $N$ is the integer that we want to factorize. To find such root we will compute the order of a given element $1 \\leq a \\leq N - 1$ modulo N. Which will be precisely given by the period of the periodic function $f(x) = a^{x} \\text{ mod } N$ on the superposition created on $M$ qubits, where $M$ is a power of two $M \\approx N$. \n",
        "\n",
        "Let's take our periodic function $f(x) = x^a\\text{ mod }M$ and apply it to our algorithm input.\n",
        "\n",
        "Initially we will initialilize two quantum registers with $|0\\rangle^{\\log M}|0\\rangle^{N}$, and apply Hadamard gates on each of the $\\log M$ first ones, to get a uniform superposition of the states from $0$ to $M - 1$.\n",
        "\n",
        "$$\n",
        "    H^{\\otimes M}|0\\rangle^{\\log M}|0\\rangle^{N} = \\frac{1}{\\sqrt{M}} \\sum_{x = 0}^{M - 1} |x\\rangle |0\\rangle\n",
        "$$\n",
        "\n",
        "Now applying the periodic function $f(x)$ on the second register we will get an state\n",
        "\n",
        "$$\n",
        "    \\frac{1}{\\sqrt{M}} \\sum_{x = 0}^{M - 1} |x\\rangle |f(x)\\rangle\n",
        "$$\n",
        "\n",
        "Then by measuring the second register we will get a periodic superposition on the first register of period $r$, which more precisely is the order of $a$.\n",
        "\n",
        "The idea of why this happens is due the periodicity of our superposition, every *rth* position of the second register are the same, hence the measurement of the second register yelds a $y$ output between $0$ and $r - 1$. And the first register is now on superposition of only this values $y, y + r, \\dots, y + M - r$, which is a periodic superpostion, with period $r$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a1sOrf7xRuaF"
      },
      "source": [
        "## The Quantum Period Finding Function\n",
        "\n",
        "Finally, this period can be found by applying the Fast Fourier Transform, ops, the Quantum Fourier Transform :D \n",
        "\n",
        "The Fast Fourier Tranform can be seen as a transformation which takes our superposition on the computational basis and rotates it to the fourier basis.  For a input of size $M$ we have such as."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jg6XBZ4GRuaF"
      },
      "source": [
        "<img src=\"images/fourier_matrix.png\" style=\"width:290px; height:160px\"/>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gcGMb9D2RuaF"
      },
      "source": [
        "Effectvely the QFT is just a change of basis from the Computational Basis to the Fourier Basis, one small example that we already know is given by the function $f$ that takes a single qubit \n",
        "\n",
        "$$\n",
        "      f:\\{|0\\rangle, |1\\rangle\\} \\rightarrow \\{|+\\rangle, |-\\rangle\\} \n",
        "$$\n",
        "\n",
        "which is clearly done by the Hadarmard gate $H$, a single qubit QFT. Therefore, to the general case on state of $n$ qubits $|x\\rangle$ we define the QFT as follows\n",
        "\n",
        "$$\n",
        "    |\\chi\\rangle = QFT|x\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{y = 0}^{N-1}e^{\\frac{2\\pi i xy}{N}}|y\\rangle\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "813lEZUxRuaF"
      },
      "source": [
        "Hence, from that definition we can extract our single-qubit $\\{|0\\rangle, |1\\rangle\\}$ example, so let $N = 2$\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    QFT|x\\rangle &= \\frac{1}{\\sqrt{2}}\\sum_{y = 0}^{N-1}e^{\\frac{2\\pi ixy}{2}}|y\\rangle\\\\\n",
        "                 &= \\frac{1}{\\sqrt{2}}\\bigg[e^{i\\pi x0}|0\\rangle + e^{i\\pi x1}|1\\rangle\\bigg]\\\\\n",
        "                 &= \\frac{1}{\\sqrt{2}}\\bigg[|0\\rangle + e^{i\\pi x}|1\\rangle\\bigg]\\\\                    \n",
        "                 &= \\begin{cases} |+\\rangle, & \\mbox{if } |x\\rangle = |0\\rangle\\\\ |-\\rangle, & \\mbox{if } |x\\rangle = |1\\rangle \\end{cases}\\\\\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Now, expanding this from the general definition above on $n$ qubits we have that\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    |\\chi\\rangle &= \\frac{1}{\\sqrt{N}}\\sum_{y = 0}^{N-1}e^{\\frac{2\\pi i xy}{N}}|y\\rangle\\\\\n",
        "                 &= \\frac{1}{\\sqrt{N}}\\sum_{y = 0}^{N-1}e^{2\\pi ix\\sum_{k = 1}^{n}\\frac{y^k}{2^k}}|y_1 y_2 \\dots y_n\\rangle\\\\\n",
        "                 &= \\frac{1}{\\sqrt{N}}\\sum_{y = 0}^{N-1}\\displaystyle\\prod_{k = 1}^{n}e^{2\\pi ix\\frac{y^k}{2^k}}|y_1 y_2 \\dots y_n\\rangle\\\\                    \n",
        "                 &= \\frac{1}{\\sqrt{N}}\\bigotimes_{k = 1}^{n}\\bigg(|0\\rangle + e^{{\\frac{2\\pi ix}{2^k}}}|1\\rangle\\bigg)\\\\\n",
        "                 &= \\frac{1}{\\sqrt{N}}\\bigg(|0\\rangle + e^{{\\frac{2\\pi ix}{2^1}}}|1\\rangle\\bigg)\\otimes\\bigg(|0\\rangle + e^{{\\frac{2\\pi ix}{2^2}}}|1\\rangle\\bigg)\\otimes\\dots\\otimes\\bigg(|0\\rangle + e^{{\\frac{2\\pi ix}{2^{n}}}}|1\\rangle\\bigg)\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "This represents a huge improvement on computational parameters, since classically this fuction presents a time complexity of the order $\\mathcal{O}(M \\log M)$ while quantum its quantum analogue $\\mathcal{O}(\\log^2 M)$, i.e, an exponential speed-up. This becomes clear when we observe that to encode all $M$ values from $0$ to $M-1$ we just need $\\log M$ qubits.\n",
        "\n",
        "And we can use this function to extract the period $r$ of a periodic superposition. We're not get in details of how to extract the period precisely, but thinking about a function that applies a certain periodic rotation on a string of qubits, what would happen if we applie it's inverse?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cWwFwa9fRuaF"
      },
      "source": [
        "## The Protocol"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Mux0XJyIRuaG"
      },
      "source": [
        "Finally, with these concepts in hand we are able to see,  or almost, how the algorithm protocol works, with classical and quantum sub-routines. Let the input $N$ be an odd composite integer $N$.\n",
        "\n",
        "**Step 1.** Randomly pick a number $a$, so that, $1 < a \\leq N-1$. And choose $M$ to be a power of two close to $N$.\n",
        "\n",
        "**Step 2.** Check if $a$ is a non-trivial factor of $N$, i.e, $\\gcd(a, N) \\neq 1$. If it is, then we got our answer and are good to go.\n",
        "\n",
        "**Step 3.** Otherwise, initialize two registers with approximately $A \\approx \\log M$ and $B \\approx \\log N$ qubits (large enough to store modulo $M$ and $N$ values).\n",
        "\n",
        "$$\n",
        "   |q_0\\rangle = |0\\rangle^{A}|0\\rangle^{B}\n",
        "$$\n",
        "\n",
        "Then apply hadamard gates on the first register, obtaining\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "  |q_1\\rangle & = H^{\\otimes A}|0\\rangle^{A}|0\\rangle^{B}\\\\&= \\frac{1}{\\sqrt{M}} \\sum_{x = 0}^{M - 1} |x\\rangle |0\\rangle\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "\n",
        "**Step 4.** Now, apply the periodic function $U_f = f(x) \\equiv a^{x}\\text{ mod }N$ to get the state\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    |q_2\\rangle &= U_f |q_1\\rangle\\\\\n",
        "                &= \\frac{1}{\\sqrt{M}} \\sum_{x = 0}^{M - 1} |x\\rangle |a^{x}\\text{ mod }N\\rangle\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "Measuring the second register we get a superposition on the first register which contains the periodic superpostion desired\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "    |q_3\\rangle = \\sqrt{\\frac{r}{M}} \\sum_{s = 0}^{\\frac{M}{r - 1}} |sr + k\\rangle \n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "where $k$ is number between $0$ and $r - 1$.\n",
        "\n",
        "**Step 5.** Applying the inverse QFT (by Quantum Phase Estimation) we can extract the phase of our superposition and get the period $r$.\n",
        "\n",
        "**Step 6.** Now if $r$ is a even number we can compute the $\\gcd(N, r \\pm 1)$ and if it is a not non-trivial factor of $N$ go back to **step 1**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SrlNYjkqRuaG"
      },
      "source": [
        "## Why this works?\n",
        "\n",
        "The above results recurs from to lemmas, about non-trivial squaare roots. A non-trivial square root of $1$ modulo $N$ is any integer such that $x^2 \\equiv 1 \\text{ mod } N$ and $x^2 \\equiv \\pm 1 \\text{ mod } N$.\n",
        "\n",
        "**Lemma 1** *If* $x$ *is a non-trivial square root of* $1$ *modulo* $N$*, then one of* $\\gcd(x \\pm 1, N)$ *is a non-trivial factor of* $N$.\n",
        "\n",
        "\n",
        "*Proof:*  $x^2 \\equiv 1 \\text{ mod } N$ implies that $N | (x^2 - 1) = (x+1)(x-1)$. But since $x \\ncong \\pm 1 \\text{ mod } N$, $N$ does not divide either of the individual terms. Therefore one of $\\gcd(x \\pm 1, N)$ is a non-trivial factor of $N$.\n",
        "\n",
        "**Lemma 2** *Let $p, q$ be primes and $N = pq$, and* $x$ *be an uniformly chosen number between* $0$ *and* $N-1$. *If* $\\gcd(x, N) = 1$*, then with probability at least* $\\frac{3}{8}$ *the order* $r$ *of* $x \\text{ mod } N$ *is even, and moreover* $x^{r/2}$ *is a non-trivial square of* $1 \\text{ mod } N$.\n",
        "\n",
        "*Proof:* To prove this we can use the Chinese Remainder Theorem. Lets choose a number $x$ uniformly between $0$ and $N - 1$. Which is the same of choosing $x_i$ and $x_j$ from $0$ to $p-1$ and $0$ to $q-1$ respectvely. And moreover we have that $r_i | r$ and $r_j | r$, the orders of $x_i$ and $x_j$ respectively.\n",
        "\n",
        "Hence, $r_i$ is even when $x_i$ is odd and $r_j$ is even when $x_j$ is odd. Then, as $r$ is even when $r_i$ or $r_j$ is even, therefore $r$ is even with probability $3/4$.\n",
        "\n",
        "Now, we need to show that the probability of $x^{\\frac{r}{2}} \\equiv \\pm 1 \\text{ mod } N$ is at most $1/2$ when $r$ is even. As $x^{r} \\equiv 1 \\text{ mod } p$ and $x^{r} \\equiv \\text{ mod } q$ and there are only two square roots of 1 modulo a prime number, $\\pm 1$. There only four roots of $1$ modulo $N$, where only two of them can make  $x^{\\frac{r}{2}} \\equiv \\pm 1 \\text{ mod } N$.\n",
        "\n",
        "Further we conclude that our result holds."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "08TA1BSCRuaG"
      },
      "source": [
        "## References "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hjgmOg6VRuaG"
      },
      "source": [
        "__[Wikipedia | Shor's Algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm)__\\\n",
        "__[Learn Quantum Computation using Qiskit](https://qiskit.org/textbook/ch-algorithms/shor.html)__\\\n",
        "__[Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani]()__"
      ]
    }
  ],
  "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.8.10"
    },
    "colab": {
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}