{ "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": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "babyStepGiantStep(104, 164, 197, order=7)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 1.2 s, sys: 0 ns, total: 1.2 s\n", "Wall time: 1.2 s\n" ] }, { "data": { "text/plain": [ "6935101882" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time babyStepGiantStep(47, 191, 100000000003)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "ename": "KeyboardInterrupt", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n", "\u001b[0;32m~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py\u001b[0m in \u001b[0;36mbabyStepGiantStep\u001b[0;34m(a, b, n, order, trace)\u001b[0m\n\u001b[1;32m 23\u001b[0m \u001b[0map\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 24\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mxxrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 25\u001b[0;31m \u001b[0map\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0map\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mam\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 26\u001b[0m \u001b[0mgs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0map\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 27\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/sage/local/lib/python3.8/site-packages/sage/rings/finite_rings/integer_mod.pyx\u001b[0m in \u001b[0;36msage.rings.finite_rings.integer_mod.IntegerMod_abstract.__mod__ (build/cythonized/sage/rings/finite_rings/integer_mod.c:7213)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 491\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mNotImplemented\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 492\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;34m.\u001b[0m\u001b[0minteger_mod_ring\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mIntegerModRing\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 493\u001b[0;31m \u001b[0mR\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mIntegerModRing\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmodulus\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 494\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m<\u001b[0m\u001b[0mElement\u001b[0m\u001b[0;34m>\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_IntegerModRing_generic__order\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mR\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0morder\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 495\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mArithmeticError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"reduction modulo {modulus!r} not defined\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/sage/local/lib/python3.8/site-packages/sage/structure/factory.pyx\u001b[0m in \u001b[0;36msage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2258)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 367\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwds\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcreate_key_and_extra_args\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 368\u001b[0m \u001b[0mversion\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_version\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msage_version\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 369\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 370\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 371\u001b[0m \u001b[0mcpdef\u001b[0m \u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mextra_args\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/sage/local/lib/python3.8/site-packages/sage/structure/factory.pyx\u001b[0m in \u001b[0;36msage.structure.factory.UniqueFactory.get_object (build/cythonized/sage/structure/factory.c:2356)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 369\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 370\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 371\u001b[0;31m \u001b[0mcpdef\u001b[0m \u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mextra_args\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 372\u001b[0m \"\"\"\n\u001b[1;32m 373\u001b[0m \u001b[0mReturns\u001b[0m \u001b[0mthe\u001b[0m \u001b[0mobject\u001b[0m \u001b[0mcorresponding\u001b[0m \u001b[0mto\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\u001b[0m\u001b[0;31m\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;31m\u001b[0m\u001b[0;31m\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcreating\u001b[0m \u001b[0mit\u001b[0m \u001b[0;32mwith\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/sage/local/lib/python3.8/site-packages/sage/rings/finite_rings/integer_mod_ring.py\u001b[0m in \u001b[0;36mget_object\u001b[0;34m(self, version, key, extra_args)\u001b[0m\n\u001b[1;32m 196\u001b[0m \"\"\"\n\u001b[1;32m 197\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mextra_args\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 198\u001b[0;31m \u001b[0mout\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msuper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mIntegerModFactory\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_object\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mversion\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mextra_args\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 199\u001b[0m \u001b[0mcategory\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextra_args\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'category'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 200\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mcategory\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32msrc/cysignals/signals.pyx\u001b[0m in \u001b[0;36mcysignals.signals.python_check_interrupt\u001b[0;34m()\u001b[0m\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m: " ] } ], "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.5" } }, "nbformat": 4, "nbformat_minor": 2 }