{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Baby-step/giant-step algorithm\n",
    "\n",
    "We will perform the baby-step/giant-step algorithm to compute $\\log_{a} b$ in $\\mathbf{Z}_{p}^*$, where $a = 47$, $b = 191$, and $p = 829$ is a prime number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 47\n",
    "b = 191\n",
    "p = 829"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let use first perform the giant steps. Since $p$ is a prime, the maximal order of an element of $\\mathbf{Z}_{p}^*$ is $p-1$. Therefore, we will perform $m = \\lceil \\sqrt{p-1} \\rceil$ giant steps. In step $i$, the value $a^{mi} \\bmod{p}$ is computed by repeatedly multiplying the last value by $a^m \\bmod{p}$, and is then used as a key in a dictionary for the value $i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 514\n",
      "2 574\n",
      "3 741\n",
      "4 363\n",
      "5 57\n",
      "6 283\n",
      "7 387\n",
      "8 787\n",
      "9 795\n",
      "10 762\n",
      "11 380\n",
      "12 505\n",
      "13 93\n",
      "14 549\n",
      "15 326\n",
      "16 106\n",
      "17 599\n",
      "18 327\n",
      "19 620\n",
      "20 344\n",
      "21 239\n",
      "22 154\n",
      "23 401\n",
      "24 522\n",
      "25 541\n",
      "26 359\n",
      "27 488\n",
      "28 474\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{1: 0,\n",
       " 514: 1,\n",
       " 574: 2,\n",
       " 741: 3,\n",
       " 363: 4,\n",
       " 57: 5,\n",
       " 283: 6,\n",
       " 387: 7,\n",
       " 787: 8,\n",
       " 795: 9,\n",
       " 762: 10,\n",
       " 380: 11,\n",
       " 505: 12,\n",
       " 93: 13,\n",
       " 549: 14,\n",
       " 326: 15,\n",
       " 106: 16,\n",
       " 599: 17,\n",
       " 327: 18,\n",
       " 620: 19,\n",
       " 344: 20,\n",
       " 239: 21,\n",
       " 154: 22,\n",
       " 401: 23,\n",
       " 522: 24,\n",
       " 541: 25,\n",
       " 359: 26,\n",
       " 488: 27,\n",
       " 474: 28}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order = p - 1\n",
    "m = ceil(sqrt(order))\n",
    "am = pow(a, m, p)\n",
    "gs = {1: 0}\n",
    "ap = 1\n",
    "for i in range(1, m):\n",
    "    ap = ap * am % p\n",
    "    gs[ap] = i\n",
    "    print(i, ap)\n",
    "gs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now perform the baby steps. In step $j$, the value $b \\cdot a^{-j} \\bmod{p}$ is computed by repeatedly multiplying the last value by $a^{-1} \\bmod{p}$, and is then stored in a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 251\n",
      "2 217\n",
      "3 181\n",
      "4 533\n",
      "5 223\n",
      "6 675\n",
      "7 32\n",
      "8 424\n",
      "9 644\n",
      "10 243\n",
      "11 111\n",
      "12 20\n",
      "13 265\n",
      "14 817\n",
      "15 670\n",
      "16 173\n",
      "17 427\n",
      "18 62\n",
      "19 407\n",
      "20 626\n",
      "21 419\n",
      "22 785\n",
      "23 246\n",
      "24 358\n",
      "25 184\n",
      "26 780\n",
      "27 387\n",
      "28 361\n",
      "29 431\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[191,\n",
       " 251,\n",
       " 217,\n",
       " 181,\n",
       " 533,\n",
       " 223,\n",
       " 675,\n",
       " 32,\n",
       " 424,\n",
       " 644,\n",
       " 243,\n",
       " 111,\n",
       " 20,\n",
       " 265,\n",
       " 817,\n",
       " 670,\n",
       " 173,\n",
       " 427,\n",
       " 62,\n",
       " 407,\n",
       " 626,\n",
       " 419,\n",
       " 785,\n",
       " 246,\n",
       " 358,\n",
       " 184,\n",
       " 780,\n",
       " 387,\n",
       " 361]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bp = b\n",
    "ai = a^-1 % p\n",
    "bs = []\n",
    "for j in range(m):\n",
    "    bs.append(bp)\n",
    "    bp = bp * ai % p\n",
    "    print(j+1, bp)\n",
    "bs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now find the index $j$ of the first element of the above list to appear as a key in the previously computed dictionary. If this key points to value $i$, then we have $a^{mi} \\equiv b \\cdot a^{-j} \\pmod{p}$, allowing us to express $b \\equiv a^{j + mi} \\pmod{p}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "230"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "j = next(i for i, bp in enumerate(bs) if bp in gs)\n",
    "x = j + m * gs[bs[j]]\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "j"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us check that we get the correct answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "191"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(a, x, p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running time comparison\n",
    "\n",
    "We will now use the function `babyStepGiantStep` to compute some more discrete logarithms and measure the evaluation times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from algorithms.discreteLogarithm import babyStepGiantStep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "babyStepGiantStep(104, 164, 197, order=7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "164"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(104, 186, 197)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "164"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(104, 4, 197)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 884 ms, sys: 14.8 ms, total: 899 ms\n",
      "Wall time: 898 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6935101882"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time babyStepGiantStep(47, 191, 100000000003)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%time babyStepGiantStep(47, 191, 10000000000000000051) # expected time: roughly 2 hours"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.2.rc2",
   "language": "sage",
   "name": "sagemath"
  },
  "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}