{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Index calculus algorithm\n", "\n", "We will perform the Index calculus algorithm to compute $\\log_{a} b_i$ ($i = 1, 2$) in $\\mathbf{Z}_{p}^*$, where $a = 5$, $b_1 = 4389733$, $b_2 = 1234567$, and $p = 9330887$ is a prime number." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from algorithms.euclidean import gcd\n", "from algorithms.factorization import factorizeByBase\n", "\n", "p = 9330887\n", "a = 5\n", "b1 = 4389733\n", "b2 = 1234567" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will use a base consisting of $-1$ and all primes less than $50$." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "base = [-1] + prime_range(50)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us now try to find the logarithms table. We construct a matrix by trying random powers of $a$ and factoring them with the numbers in our base. We stop when the matrix has full rank." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1 0 2 1 0 0 1 0 0 0 0 0 0 0 2 0]\n", "[1 0 1 0 0 0 0 0 0 0 0 1 3 0 0 0]\n", "[0 3 8 0 1 0 0 0 0 1 0 0 0 0 0 0]\n", "[0 1 2 1 2 0 0 0 0 0 1 0 1 0 0 0]\n", "[1 0 0 0 1 3 1 0 0 0 0 0 0 1 0 0]\n", "[1 4 0 0 1 0 0 1 0 0 1 0 0 0 0 0]\n", "[1 2 0 3 3 0 0 0 0 1 0 0 0 0 0 0]\n", "[1 2 2 0 0 1 1 1 0 1 0 0 0 0 0 0]\n", "[0 8 1 0 0 2 0 0 0 0 0 0 0 0 1 0]\n", "[0 3 1 0 0 1 0 0 1 1 0 0 0 0 0 0]\n", "[0 5 0 1 0 0 0 1 0 0 1 0 1 0 0 0]\n", "[0 0 0 1 1 0 0 0 1 0 0 0 0 2 0 0]\n", "[0 0 0 0 2 0 0 0 1 0 1 0 0 0 0 1]\n", "[0 1 3 0 4 0 1 0 0 0 0 0 0 0 0 0]\n", "[1 4 1 5 0 0 0 0 0 1 0 0 0 0 0 0]\n", "[1 1 1 2 0 2 1 0 1 0 0 0 0 0 0 0]\n", "[1342485, 669118, 7237936, 7922551, 9149713, 4288717, 563606, 4482702, 7606125, 6167680, 7916700, 6825736, 4712055, 7120183, 7905940, 4584527]\n" ] } ], "source": [ "set_random_seed(0)\n", "\n", "v = []\n", "s = set()\n", "r, l = 0, len(base)\n", "M = Matrix(nrows=0, ncols=l)\n", "while r < l:\n", " i = randint(1, p-1)\n", " if i in s:\n", " continue\n", " s.add(i)\n", " x = pow(a, i, p)\n", " f = factorizeByBase(Integer(x), base, p)\n", " if not f:\n", " continue\n", " MM = Matrix(list(M) + [f])\n", " rr = MM.rank()\n", " if rr > r:\n", " M = MM\n", " r = rr\n", " v.append(i)\n", "print(M)\n", "print(v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now solve the system of equations we have obtained. The solution represents our table of logarithms and can be used to find logarithms of multiple numbers." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[4665443]\n", "[6670912]\n", "[2030334]\n", "[ 1]\n", "[5786904]\n", "[1078197]\n", "[8534197]\n", "[7606749]\n", "[8519903]\n", "[2519168]\n", "[6200403]\n", "[9068634]\n", "[7409417]\n", "[5590350]\n", "[6037417]\n", "[6410599]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = M^-1 * Matrix(zip(v)) % (p-1)\n", "t" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us verify that the table is correct." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[9330886, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[pow(a, i, p) for i, in t]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now find a power of $b_i$ that can be factorized with our base. We will use the following function." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def findPower(b, p, base):\n", " while True:\n", " i = randint(1, p-1)\n", " x = pow(b, i, p)\n", " f = factorizeByBase(Integer(x), base, p)\n", " if not f:\n", " continue\n", " return (i, f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us find such a power of $b_1$ and its factorization." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3157805, [0, 0, 3, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "i1, f1 = findPower(b1, p, base)\n", "i1, f1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now use the logarithm table to obtain a congruence in $\\log_a b_1$. However, there may be multiple solutions, and we need to check which one is our answer. The number of solutions is given by the greatest common divisor of $p-1$ and the obtained exponent." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g1 = gcd(i1, p-1)\n", "g1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can thus obtain a solution modulo $p-1$ divided by this GCD." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5753305" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m1 = ((p-1)/g1)\n", "(x1,), = Matrix([f1])*t / i1 % m1\n", "x1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us now put this into a function which will also verify the potential solutions." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5^5753305 mod 9330887 = 4389733\n" ] }, { "data": { "text/plain": [ "5753305" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def checkSolutions(a, b, p, t, i, f):\n", " g = gcd(i, p-1)\n", " m = (p-1)/g\n", " (x,), = Matrix([f])*t / i % m\n", " for j in range(g):\n", " y = pow(a, x, p)\n", " print(\"%d^%d mod %d = %d\" % (a, x, p, y))\n", " if y == b:\n", " return x\n", " x += m\n", "\n", "checkSolutions(a, b1, p, t, i1, f1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have thus computed $\\log_a b_1$. Let us now compute $\\log_a b_2$." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5353502, [0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0])" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "i2, f2 = findPower(b2, p, base)\n", "i2, f2" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5^2608331 mod 9330887 = 8096320\n", "5^7273774 mod 9330887 = 1234567\n" ] }, { "data": { "text/plain": [ "7273774" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "checkSolutions(a, b2, p, t, i2, f2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Running time comparison\n", "\n", "We will now use the function logarithmTable to compute tables of logarithms, which will then be used to compute some more discrete logarithms with the function indexCalculus. We will measure the evaluation times." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "from algorithms.discreteLogarithm import logarithmTable, indexCalculus\n", "\n", "aa = 47\n", "bb = 191" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "found factorization 47^84497243479 = -1^1 * 2^1 * 3^1 * 5^6 * 7^1 * 11^2 * 23^1 * 29^1 (mod 100000000003)\n", "found factorization 47^55045977185 = 2^1 * 11^1 * 13^3 * 19^2 * 37^1 * 43^1 (mod 100000000003)\n", "found factorization 47^93740896216 = 13^4 * 23^2 * 29^1 (mod 100000000003)\n", "found factorization 47^62252472984 = -1^1 * 2^5 * 3^2 * 5^1 * 7^1 * 11^1 * 17^1 * 19^2 * 41^1 (mod 100000000003)\n", "found factorization 47^98257292990 = -1^1 * 3^1 * 23^4 * 41^1 * 47^1 (mod 100000000003)\n", "found factorization 47^57017421058 = 2^5 * 13^2 * 17^1 * 23^2 (mod 100000000003)\n", "found factorization 47^63831308173 = -1^1 * 2^3 * 5^3 * 7^2 * 19^1 * 31^1 * 41^1 * 43^1 (mod 100000000003)\n", "found factorization 47^67516991484 = -1^1 * 3^1 * 5^1 * 7^4 * 11^2 * 19^1 * 31^2 (mod 100000000003)\n", "found factorization 47^33797337121 = 2^10 * 3^2 * 5^2 * 11^1 * 43^1 * 47^1 (mod 100000000003)\n", "found factorization 47^17498086004 = 2^1 * 7^2 * 11^2 * 13^1 * 29^1 * 31^1 * 43^1 (mod 100000000003)\n", "found factorization 47^31657988253 = 2^1 * 7^7 * 17^1 * 31^1 (mod 100000000003)\n", "found factorization 47^60619654035 = 2^3 * 3^4 * 5^2 * 13^2 * 23^1 * 47^1 (mod 100000000003)\n", "found factorization 47^92434058549 = 2^6 * 3^3 * 5^3 * 13^1 * 19^1 * 31^1 * 37^1 (mod 100000000003)\n", "found factorization 47^56456319013 = 2^3 * 3^5 * 5^1 * 11^1 * 13^1 * 17^1 * 47^2 (mod 100000000003)\n", "found factorization 47^55622355719 = 2^9 * 3^1 * 7^2 * 13^1 * 23^1 * 37^1 (mod 100000000003)\n", "rank not increased, discarding\n", "found factorization 47^52004730500 = 3^3 * 7^2 * 17^1 * 23^1 * 31^2 * 47^1 (mod 100000000003)\n", "found factorization 47^12484556881 = 2^11 * 5^1 * 11^1 * 23^2 * 37^1 * 43^1 (mod 100000000003)\n", "rank not increased, discarding\n", "found factorization 47^96345630522 = 2^2 * 3^1 * 5^3 * 7^2 * 19^2 * 41^2 (mod 100000000003)\n", "rank not increased, discarding\n", "found factorization 47^29509646289 = 3^2 * 5^1 * 11^1 * 13^1 * 19^2 * 31^1 * 41^1 (mod 100000000003)\n", "rank not increased, discarding\n", "found factorization 47^90014436945 = 2^6 * 3^2 * 13^1 * 17^2 * 31^2 * 43^1 (mod 100000000003)\n", "rank not increased, discarding\n", "found factorization 47^91058239375 = -1^1 * 2^5 * 3^5 * 5^8 * 29^1 (mod 100000000003)\n", "CPU times: user 4.04 s, sys: 48.7 ms, total: 4.08 s\n", "Wall time: 4.1 s\n", "[50000000001, 88948660783, 74403602789, 76906212201, 2995382539, 11520765452, 33861633403, 95303711677, 78308239391, 74623569337, 9047223934, 26437938024, 66204838085, 75359412859, 30170333882, 1]\n", "found factorization 191^75958412224 = 7^1 * 11^2 * 13^4 * 37^1 * 43^1 (mod 100000000003)\n", "checking 2 solutions for 47^x = 191, x = 6935101882 (mod 50000000001)\n", "47^6935101882 mod 100000000003 = 191\n", "CPU times: user 1.03 s, sys: 19.6 ms, total: 1.05 s\n", "Wall time: 1.06 s\n" ] }, { "data": { "text/plain": [ "6935101882" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pp = 100000000003\n", "table = %time logarithmTable(aa, pp, base, trace = True)\n", "print(table)\n", "%time indexCalculus(aa, bb, pp, base, table, trace = True)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "found factorization 47^2179497432067614218 = 2^4 * 5^1 * 107^1 * 293^1 * 317^1 * 643^1 * 2591^1 * 4793^1 (mod 10000000000000000051)\n", "found factorization 47^8204853581526273040 = 2^1 * 3^3 * 7^1 * 19^1 * 101^1 * 109^1 * 1091^1 * 1567^1 * 1889^1 (mod 10000000000000000051)\n", "found factorization 47^5332758726454119214 = 2^4 * 11^1 * 17^1 * 73^1 * 593^1 * 883^1 * 1013^1 * 3889^1 (mod 10000000000000000051)\n", "found factorization 47^5587859396418665063 = 23^1 * 227^2 * 307^1 * 311^1 * 701^1 * 2659^1 (mod 10000000000000000051)\n", "found factorization 47^226077030606921208 = 2^3 * 5^3 * 29^1 * 137^1 * 157^1 * 389^1 * 593^1 * 2957^1 (mod 10000000000000000051)\n", "found factorization 47^999096871500948476 = -1^1 * 2^1 * 379^1 * 677^1 * 821^1 * 1049^1 * 1627^1 * 4159^1 (mod 10000000000000000051)\n", "found factorization 47^2720398736870491859 = -1^1 * 2^1 * 3^3 * 23^1 * 67^1 * 71^1 * 89^2 * 193^1 * 283^1 * 1933^1 (mod 10000000000000000051)\n", "found factorization 47^1271998692131759176 = -1^1 * 2^1 * 3^1 * 17^1 * 61^1 * 131^1 * 173^1 * 1163^1 * 3989^1 * 4217^1 (mod 10000000000000000051)\n", "found factorization 47^2859630369235796494 = -1^1 * 2^1 * 3^1 * 17^1 * 181^1 * 293^1 * 1619^1 * 2801^1 * 4943^1 (mod 10000000000000000051)\n", "found factorization 47^4193241327745824698 = 3^1 * 89^1 * 211^1 * 229^1 * 2371^1 * 3049^1 * 4273^1 (mod 10000000000000000051)\n", "found factorization 47^1273501793223196459 = -1^1 * 3^1 * 307^1 * 577^1 * 619^1 * 1117^1 * 1999^1 * 3467^1 (mod 10000000000000000051)\n", "found factorization 47^1769187930605990394 = -1^1 * 3^1 * 13^1 * 83^1 * 571^1 * 991^1 * 1061^1 * 1777^1 * 2069^1 (mod 10000000000000000051)\n", "found factorization 47^4780857940387103231 = -1^1 * 13^1 * 71^1 * 101^1 * 137^1 * 701^1 * 1051^1 * 2843^1 (mod 10000000000000000051)\n", "found factorization 47^1444277781522927847 = -1^1 * 2^2 * 523^1 * 3121^1 * 3541^1 * 4003^1 * 4517^1 (mod 10000000000000000051)\n", "found factorization 47^4435853557423186328 = 2^1 * 3^1 * 17^2 * 43^1 * 149^1 * 409^1 * 587^1 * 1481^1 * 1663^1 (mod 10000000000000000051)\n", "found factorization 47^8837828089629176966 = -1^1 * 2^3 * 3^6 * 7^1 * 83^1 * 281^1 * 727^1 * 2203^1 * 4339^1 (mod 10000000000000000051)\n", "found factorization 47^7987897606114726628 = -1^1 * 2^4 * 3^2 * 53^1 * 83^1 * 271^1 * 757^1 * 2671^1 * 3089^1 (mod 10000000000000000051)\n", "found factorization 47^8178769214846705235 = 2^2 * 7^1 * 157^1 * 269^1 * 419^1 * 1327^1 * 1697^1 * 4817^1 (mod 10000000000000000051)\n", "found factorization 47^8463228572032171234 = 2^1 * 3^3 * 17^1 * 113^1 * 233^1 * 1061^1 * 1723^1 * 3389^1 (mod 10000000000000000051)\n", "found factorization 47^8779453939329703949 = 2^3 * 5^1 * 101^1 * 103^1 * 347^1 * 1249^1 * 3769^1 * 4583^1 (mod 10000000000000000051)\n", "found factorization 47^5474091186535589611 = -1^1 * 3^3 * 5^1 * 11^1 * 41^1 * 683^1 * 3853^1 * 4013^1 * 4409^1 (mod 10000000000000000051)\n", "found factorization 47^4954575118402279281 = -1^1 * 2^1 * 11^1 * 47^1 * 61^1 * 191^1 * 349^1 * 457^1 * 1723^2 (mod 10000000000000000051)\n", "found factorization 47^1518281886591774342 = -1^1 * 2^1 * 3^1 * 23^1 * 367^1 * 433^1 * 607^1 * 3089^1 * 3823^1 (mod 10000000000000000051)\n", "found factorization 47^2193851454966296067 = -1^1 * 2^1 * 5^1 * 11^1 * 13^1 * 467^1 * 719^1 * 1571^1 * 2099^1 * 4937^1 (mod 10000000000000000051)\n", "found factorization 47^260903128323509513 = -1^1 * 2^7 * 11^1 * 13^1 * 19^2 * 2081^1 * 2749^1 * 2803^1 (mod 10000000000000000051)\n", "found factorization 47^2512852496525643242 = -1^1 * 2^3 * 7^1 * 17^1 * 59^1 * 131^2 * 401^1 * 1031^1 * 4157^1 (mod 10000000000000000051)\n", "found factorization 47^3691888902966828755 = -1^1 * 2^1 * 7^1 * 13^1 * 41^1 * 67^1 * 191^1 * 2767^1 * 3719^1 * 4877^1 (mod 10000000000000000051)\n", "found factorization 47^9403142627478890061 = -1^1 * 2^2 * 3^1 * 11^1 * 43^1 * 163^1 * 419^1 * 1489^1 * 1733^1 * 3463^1 (mod 10000000000000000051)\n", "found factorization 47^8095490419802843954 = -1^1 * 2^1 * 3^2 * 5^1 * 7^2 * 41^1 * 43^1 * 61^1 * 401^1 * 439^1 * 3559^1 (mod 10000000000000000051)\n", "found factorization 47^6546434270787613708 = 5^1 * 7^2 * 19^1 * 31^1 * 53^1 * 211^1 * 293^1 * 2927^1 * 4663^1 (mod 10000000000000000051)\n", "found factorization 47^5575367014741603051 = 2^1 * 3^1 * 47^1 * 79^1 * 107^1 * 397^1 * 1049^1 * 1153^1 * 4093^1 (mod 10000000000000000051)\n", "found factorization 47^2208189363741281117 = -1^1 * 2^2 * 3^3 * 7^2 * 23^1 * 337^1 * 1721^1 * 4337^1 * 4349^1 (mod 10000000000000000051)\n", "found factorization 47^3029919379372598139 = -1^1 * 2^1 * 3^1 * 13^1 * 31^1 * 353^1 * 379^1 * 1721^1 * 2707^1 * 3643^1 (mod 10000000000000000051)\n", "found factorization 47^1294056674836816677 = 2^6 * 151^1 * 199^1 * 449^1 * 479^1 * 3109^1 * 4931^1 (mod 10000000000000000051)\n", "found factorization 47^5229989021208468051 = 2^2 * 7^1 * 73^1 * 241^1 * 367^1 * 1709^1 * 3083^1 * 3557^1 (mod 10000000000000000051)\n", "found factorization 47^6139840335265768774 = -1^1 * 5^1 * 7^1 * 11^1 * 19^1 * 131^1 * 293^1 * 2377^1 * 3121^1 * 3461^1 (mod 10000000000000000051)\n", "found factorization 47^1293768518622218656 = -1^1 * 2^2 * 7^1 * 29^1 * 31^1 * 257^1 * 379^1 * 521^1 * 1229^1 * 4603^1 (mod 10000000000000000051)\n", "found factorization 47^9445333779141676873 = 2^2 * 73^1 * 83^1 * 353^1 * 449^1 * 467^1 * 1163^1 * 3739^1 (mod 10000000000000000051)\n", "found factorization 47^3621041543123407339 = 2^5 * 223^1 * 227^1 * 269^1 * 2081^1 * 2711^1 * 2749^1 (mod 10000000000000000051)\n", "found factorization 47^8447974074538547891 = -1^1 * 3^1 * 5^1 * 67^2 * 347^1 * 439^1 * 569^1 * 823^1 * 881^1 (mod 10000000000000000051)\n", "found factorization 47^9046877721977140702 = 3^1 * 11^1 * 41^1 * 47^1 * 53^1 * 283^1 * 977^1 * 2741^1 * 3659^1 (mod 10000000000000000051)\n", "found factorization 47^1159928358980693386 = -1^1 * 2^3 * 29^1 * 199^1 * 569^1 * 829^1 * 1907^1 * 2357^1 (mod 10000000000000000051)\n", "found factorization 47^8440250248839466090 = 19^1 * 59^1 * 293^1 * 547^1 * 1321^1 * 1489^1 * 4253^1 (mod 10000000000000000051)\n", "found factorization 47^4408327007164968660 = -1^1 * 2^3 * 13^1 * 73^1 * 89^1 * 479^1 * 2113^1 * 2897^1 * 4153^1 (mod 10000000000000000051)\n", "found factorization 47^9407208490524940976 = 2^1 * 7^1 * 41^1 * 53^1 * 347^1 * 617^1 * 659^1 * 857^1 * 1453^1 (mod 10000000000000000051)\n", "found factorization 47^2618192304072479114 = -1^1 * 2^3 * 3^1 * 31^1 * 47^1 * 53^1 * 61^1 * 101^1 * 137^1 * 1301^1 * 4441^1 (mod 10000000000000000051)\n", "found factorization 47^9903874506685304914 = 3^1 * 5^2 * 7^1 * 89^1 * 271^1 * 317^1 * 2003^1 * 4799^1 (mod 10000000000000000051)\n", "found factorization 47^6065228674828731510 = 11^1 * 13^1 * 19^1 * 73^1 * 1171^1 * 1787^1 * 2969^1 * 3943^1 (mod 10000000000000000051)\n", "found factorization 47^1140021849073153749 = -1^1 * 3^2 * 5^4 * 7^2 * 29^1 * 59^1 * 149^1 * 1019^1 * 1567^1 (mod 10000000000000000051)\n", "found factorization 47^6053249944320813054 = -1^1 * 23^1 * 79^1 * 181^1 * 547^1 * 1499^1 * 1987^1 * 2423^1 (mod 10000000000000000051)\n", "found factorization 47^42816357289123641 = 2^1 * 3^1 * 13^2 * 59^1 * 317^1 * 431^1 * 433^1 * 1297^1 * 2011^1 (mod 10000000000000000051)\n", "found factorization 47^2296847402754742070 = 2^6 * 13^1 * 29^1 * 233^2 * 359^1 * 947^1 * 3767^1 (mod 10000000000000000051)\n", "found factorization 47^2794475815447091735 = 2^3 * 17^1 * 23^1 * 37^2 * 47^1 * 109^1 * 283^1 * 547^1 * 2879^1 (mod 10000000000000000051)\n", "found factorization 47^423947503758756981 = 2^4 * 5^1 * 37^1 * 47^1 * 1187^1 * 1237^1 * 2113^1 * 2543^1 (mod 10000000000000000051)\n", "found factorization 47^3969292717060976005 = -1^1 * 2^1 * 5^1 * 157^1 * 197^1 * 313^1 * 1249^1 * 3049^1 * 4937^1 (mod 10000000000000000051)\n", "found factorization 47^1385104560440192072 = -1^1 * 2^4 * 11^1 * 17^1 * 281^1 * 359^1 * 1451^1 * 2683^1 * 3739^1 (mod 10000000000000000051)\n", "found factorization 47^5133463935955782649 = 2^1 * 61^1 * 71^1 * 89^1 * 661^1 * 1217^1 * 1283^1 * 1447^1 (mod 10000000000000000051)\n", "found factorization 47^1255958701434779082 = 37^1 * 167^1 * 191^1 * 269^1 * 1423^1 * 2287^1 * 4993^1 (mod 10000000000000000051)\n", "found factorization 47^5773134569651730973 = 3^1 * 113^1 * 331^1 * 419^1 * 2027^1 * 2377^1 * 3617^1 (mod 10000000000000000051)\n", "found factorization 47^5782260890911082530 = 2^2 * 3^1 * 107^1 * 113^1 * 157^1 * 173^1 * 199^1 * 521^1 * 3407^1 (mod 10000000000000000051)\n", "found factorization 47^7021090602000602927 = 5^6 * 109^1 * 173^1 * 1453^1 * 4159^1 * 4787^1 (mod 10000000000000000051)\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "found factorization 47^757394578626478646 = -1^1 * 2^1 * 3^1 * 37^2 * 131^1 * 1201^1 * 1291^1 * 1433^1 * 2477^1 (mod 10000000000000000051)\n", "found factorization 47^3670642106027243491 = 3^5 * 5^1 * 11^1 * 59^1 * 89^1 * 113^1 * 809^1 * 1619^1 (mod 10000000000000000051)\n", "found factorization 47^1152506915024311731 = -1^1 * 3^1 * 5^1 * 11^1 * 347^1 * 1637^1 * 3019^1 * 3467^1 * 4339^1 (mod 10000000000000000051)\n", "found factorization 47^843769353555840246 = -1^1 * 3^2 * 23^1 * 31^1 * 83^1 * 89^1 * 149^1 * 571^1 * 719^1 * 1009^1 (mod 10000000000000000051)\n", "found factorization 47^2342528196895492096 = 2^2 * 5^2 * 23^1 * 79^1 * 101^1 * 179^1 * 613^1 * 907^1 * 3767^1 (mod 10000000000000000051)\n", "found factorization 47^325186157213753234 = 2^2 * 3^1 * 47^1 * 257^1 * 1171^1 * 2663^1 * 2963^1 * 3571^1 (mod 10000000000000000051)\n", "found factorization 47^7708485993070530200 = -1^1 * 2^1 * 11^1 * 73^1 * 151^1 * 367^1 * 859^1 * 1039^1 * 2221^1 (mod 10000000000000000051)\n", "found factorization 47^1235282735191417043 = -1^1 * 2^1 * 5^1 * 59^1 * 373^1 * 829^1 * 1699^1 * 1721^1 * 2659^1 (mod 10000000000000000051)\n", "found factorization 47^4440329003857653011 = 2^1 * 3^1 * 11^1 * 13^1 * 19^1 * 61^1 * 367^1 * 953^1 * 3373^1 * 3877^1 (mod 10000000000000000051)\n", "found factorization 47^2124989123194036989 = 3^2 * 5^1 * 11^1 * 379^1 * 857^1 * 1033^1 * 2243^1 * 3299^1 (mod 10000000000000000051)\n", "found factorization 47^2415118869213497302 = -1^1 * 2^2 * 11^2 * 19^1 * 31^1 * 107^1 * 131^1 * 313^1 * 1303^1 * 1697^1 (mod 10000000000000000051)\n", "found factorization 47^203327952928256998 = -1^1 * 5^3 * 53^1 * 277^1 * 283^1 * 631^1 * 787^1 * 4337^1 (mod 10000000000000000051)\n", "found factorization 47^7612810780339220813 = -1^1 * 2^1 * 3^1 * 5^1 * 89^1 * 191^1 * 769^1 * 2459^1 * 2969^1 * 3119^1 (mod 10000000000000000051)\n", "found factorization 47^7159693367875208095 = 2^1 * 3^2 * 5^1 * 7^1 * 23^1 * 41^1 * 89^1 * 271^1 * 619^1 * 853^1 * 1213^1 (mod 10000000000000000051)\n", "found factorization 47^1258660080508409033 = -1^1 * 2^4 * 3^1 * 5^2 * 443^1 * 571^1 * 2663^1 * 3301^1 * 3691^1 (mod 10000000000000000051)\n", "found factorization 47^7457774780564176939 = 2^3 * 5^2 * 11^1 * 41^1 * 61^1 * 101^1 * 1873^1 * 2609^1 * 3581^1 (mod 10000000000000000051)\n", "found factorization 47^8138232256619200727 = -1^1 * 2^1 * 3^1 * 5^1 * 7^1 * 11^1 * 17^1 * 53^1 * 83^1 * 107^1 * 109^1 * 521^1 * 1733^1 (mod 10000000000000000051)\n", "found factorization 47^7560804650852420591 = -1^1 * 5^3 * 7^1 * 31^1 * 659^1 * 727^1 * 2801^1 * 3391^1 (mod 10000000000000000051)\n", "found factorization 47^1164723476676231606 = 2^1 * 3^1 * 71^1 * 107^1 * 1747^1 * 2039^1 * 3779^1 * 4339^1 (mod 10000000000000000051)\n", "found factorization 47^3080318643732974544 = -1^1 * 769^1 * 797^1 * 859^1 * 1621^1 * 2281^1 * 4283^1 (mod 10000000000000000051)\n", "found factorization 47^1533299057005919302 = -1^1 * 2^1 * 13^1 * 19^1 * 53^1 * 67^2 * 131^1 * 167^1 * 229^1 * 4297^1 (mod 10000000000000000051)\n", "found factorization 47^1484037391417127896 = -1^1 * 2^1 * 7^1 * 137^1 * 157^1 * 823^1 * 2113^1 * 2729^1 * 3251^1 (mod 10000000000000000051)\n", "found factorization 47^1577828132803256958 = 2^5 * 3^2 * 5^2 * 317^1 * 797^1 * 1129^1 * 1483^1 * 3011^1 (mod 10000000000000000051)\n", "found factorization 47^329888597625052644 = -1^1 * 2^1 * 3^3 * 7^1 * 13^2 * 19^1 * 83^1 * 151^1 * 353^1 * 547^1 * 1297^1 (mod 10000000000000000051)\n", "found factorization 47^2501315712506904711 = -1^1 * 2^3 * 11^4 * 17^1 * 53^1 * 197^1 * 223^1 * 479^1 * 2953^1 (mod 10000000000000000051)\n", "found factorization 47^194308953719522900 = 2^1 * 7^2 * 19^1 * 241^1 * 251^1 * 1993^1 * 2671^1 * 2753^1 (mod 10000000000000000051)\n", "found factorization 47^4228133316643997639 = -1^1 * 2^1 * 3^2 * 7^1 * 13^1 * 257^1 * 349^1 * 1409^1 * 4621^1 * 4817^1 (mod 10000000000000000051)\n", "found factorization 47^3803029917061962574 = -1^1 * 2^3 * 3^1 * 5^1 * 53^1 * 89^1 * 257^1 * 373^2 * 397^1 * 419^1 (mod 10000000000000000051)\n", "found factorization 47^1243416335509546261 = 2^4 * 3^4 * 5^1 * 17^2 * 19^1 * 103^1 * 239^1 * 499^1 * 751^1 (mod 10000000000000000051)\n", "found factorization 47^4022154907862586101 = -1^1 * 2^2 * 7^1 * 67^1 * 151^1 * 251^1 * 977^1 * 2357^1 * 4001^1 (mod 10000000000000000051)\n", "found factorization 47^1023587846077958379 = -1^1 * 3^3 * 7^1 * 11^1 * 19^2 * 41^1 * 281^1 * 373^1 * 1163^1 * 2309^1 (mod 10000000000000000051)\n", "found factorization 47^8206902393169777525 = -1^1 * 17^1 * 223^2 * 347^1 * 1291^1 * 1879^1 * 2819^1 (mod 10000000000000000051)\n", "found factorization 47^7723831218151236322 = -1^1 * 2^2 * 3^1 * 11^1 * 97^1 * 227^1 * 401^1 * 479^1 * 2459^1 * 3049^1 (mod 10000000000000000051)\n", "found factorization 47^9742055419422140301 = 2^3 * 3^1 * 109^1 * 337^1 * 977^1 * 1367^1 * 1741^1 * 4481^1 (mod 10000000000000000051)\n", "found factorization 47^3388856273798759752 = 37^1 * 107^1 * 419^1 * 563^1 * 1523^1 * 2087^1 * 2207^1 (mod 10000000000000000051)\n", "found factorization 47^1051027178071525214 = 5^1 * 11^1 * 17^2 * 101^1 * 359^1 * 1847^1 * 2549^2 (mod 10000000000000000051)\n", "found factorization 47^9939929902803808110 = -1^1 * 2^3 * 7^1 * 131^1 * 257^1 * 307^1 * 607^1 * 1979^1 * 4451^1 (mod 10000000000000000051)\n", "found factorization 47^2396427496742989023 = -1^1 * 2^1 * 37^2 * 61^1 * 83^1 * 337^1 * 431^1 * 739^1 * 2053^1 (mod 10000000000000000051)\n", "found factorization 47^3162299080884729352 = -1^1 * 2^2 * 5^2 * 7^1 * 11^2 * 41^1 * 53^1 * 71^1 * 101^1 * 2381^1 * 2857^1 (mod 10000000000000000051)\n", "found factorization 47^7155863318760889193 = -1^1 * 17^1 * 23^1 * 307^1 * 2297^1 * 2339^1 * 2473^1 * 4079^1 (mod 10000000000000000051)\n", "found factorization 47^2160716663298313657 = 3^2 * 5^1 * 7^2 * 13^1 * 23^1 * 31^1 * 389^1 * 601^1 * 1321^1 * 1439^1 (mod 10000000000000000051)\n", "found factorization 47^6945018678025296211 = -1^1 * 2^2 * 3^2 * 41^1 * 71^1 * 73^1 * 353^1 * 643^1 * 1129^1 * 3259^1 (mod 10000000000000000051)\n", "found factorization 47^2499771078615744604 = -1^1 * 2^3 * 61^1 * 283^1 * 887^1 * 1913^1 * 4159^1 * 4651^1 (mod 10000000000000000051)\n", "found factorization 47^7423207484577238868 = -1^1 * 2^2 * 37^1 * 613^1 * 1231^1 * 3067^1 * 4463^1 * 4787^1 (mod 10000000000000000051)\n", "found factorization 47^668396945569389854 = 2^3 * 43^2 * 179^1 * 181^1 * 761^1 * 947^1 * 3539^1 (mod 10000000000000000051)\n", "found factorization 47^6419321998601359324 = -1^1 * 2^1 * 17^1 * 37^1 * 89^1 * 1783^1 * 2113^1 * 2473^1 * 3121^1 (mod 10000000000000000051)\n", "found factorization 47^7731529323320689560 = 2^1 * 13^1 * 29^1 * 31^1 * 157^1 * 337^1 * 1361^1 * 1913^1 * 2287^1 (mod 10000000000000000051)\n", "found factorization 47^6047275738649906509 = 23^1 * 547^1 * 2729^1 * 3119^1 * 4297^1 * 4493^1 (mod 10000000000000000051)\n", "found factorization 47^7942897863060992359 = 3^2 * 43^1 * 197^1 * 929^1 * 1151^1 * 1223^1 * 4133^1 (mod 10000000000000000051)\n", "found factorization 47^7198480498854393938 = -1^1 * 2^3 * 5^2 * 7^1 * 13^1 * 349^1 * 701^1 * 709^1 * 937^1 * 2153^1 (mod 10000000000000000051)\n", "found factorization 47^1487234489128201129 = 2^1 * 3^1 * 5^1 * 13^2 * 23^3 * 149^1 * 211^1 * 1069^1 * 2141^1 (mod 10000000000000000051)\n", "found factorization 47^4222779078693727678 = 2^1 * 3^2 * 7^2 * 17^1 * 67^1 * 499^1 * 1913^1 * 2857^1 * 3571^1 (mod 10000000000000000051)\n", "found factorization 47^1379323400533391822 = -1^1 * 2^7 * 5^1 * 17^1 * 53^1 * 83^1 * 101^1 * 257^1 * 1237^1 * 3469^1 (mod 10000000000000000051)\n", "found factorization 47^4916267078838154529 = 2^1 * 7^1 * 17^1 * 113^1 * 683^1 * 1723^1 * 3361^1 * 4463^1 (mod 10000000000000000051)\n", "found factorization 47^8996629720030685269 = -1^1 * 2^1 * 3^3 * 5^1 * 53^1 * 353^1 * 439^1 * 857^1 * 1321^1 * 2207^1 (mod 10000000000000000051)\n", "found factorization 47^6292054030479845893 = -1^1 * 2^1 * 5^1 * 17^1 * 37^1 * 229^1 * 281^1 * 863^1 * 1693^1 * 4591^1 (mod 10000000000000000051)\n", "found factorization 47^3271660484333895736 = 2^1 * 5^1 * 13^1 * 59^1 * 67^1 * 127^1 * 439^1 * 839^1 * 4021^1 (mod 10000000000000000051)\n", "found factorization 47^1871198672101494856 = 5^1 * 11^1 * 107^1 * 257^1 * 571^1 * 1019^1 * 2237^1 * 4139^1 (mod 10000000000000000051)\n", "found factorization 47^7916118774951018347 = -1^1 * 2^3 * 3^1 * 13^1 * 37^1 * 41^1 * 83^1 * 1459^1 * 2593^1 * 4259^1 (mod 10000000000000000051)\n", "found factorization 47^4559727615371219210 = 3^1 * 7^1 * 157^1 * 227^1 * 787^1 * 797^1 * 4423^1 * 4457^1 (mod 10000000000000000051)\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "found factorization 47^3368485832692685615 = 2^1 * 3^1 * 5^2 * 7^2 * 41^1 * 61^1 * 79^1 * 251^1 * 1571^1 * 3061^1 (mod 10000000000000000051)\n", "found factorization 47^5160252247840033863 = -1^1 * 2^1 * 7^1 * 89^1 * 631^1 * 787^1 * 1373^1 * 2713^1 * 3881^1 (mod 10000000000000000051)\n", "found factorization 47^1138978953907096984 = 2^2 * 3^1 * 29^1 * 47^1 * 269^1 * 337^1 * 353^1 * 3559^1 * 3989^1 (mod 10000000000000000051)\n", "found factorization 47^2855788244171642468 = -1^1 * 2^2 * 3^1 * 5^1 * 7^1 * 47^1 * 431^2 * 617^1 * 1217^1 * 1601^1 (mod 10000000000000000051)\n", "found factorization 47^5086945910651030397 = -1^1 * 3^1 * 89^1 * 127^1 * 281^1 * 311^1 * 401^1 * 947^1 * 1609^1 (mod 10000000000000000051)\n", "found factorization 47^2230405413970961393 = -1^1 * 2^6 * 3^2 * 5^2 * 43^1 * 73^1 * 167^1 * 179^1 * 797^1 * 1667^1 (mod 10000000000000000051)\n", "found factorization 47^8961760904011983737 = -1^1 * 2^2 * 13^1 * 1201^1 * 1627^1 * 1721^1 * 1759^1 * 4967^1 (mod 10000000000000000051)\n", "found factorization 47^1691865556539576999 = 2^3 * 13^1 * 17^2 * 29^1 * 103^1 * 149^1 * 157^1 * 307^1 * 3779^1 (mod 10000000000000000051)\n", "found factorization 47^1123164819442552558 = -1^1 * 2^1 * 7^1 * 13^1 * 17^2 * 19^1 * 443^1 * 1013^1 * 1723^1 * 2447^1 (mod 10000000000000000051)\n", "found factorization 47^5770402188118517533 = -1^1 * 2^2 * 13^3 * 43^1 * 937^1 * 1559^1 * 2029^1 * 4787^1 (mod 10000000000000000051)\n", "found factorization 47^8310336347054423603 = 31^1 * 61^1 * 487^1 * 983^1 * 1511^1 * 1531^1 * 4463^1 (mod 10000000000000000051)\n", "found factorization 47^7816637457804443125 = -1^1 * 2^6 * 3^1 * 11^2 * 13^1 * 17^1 * 19^1 * 61^1 * 241^1 * 2003^1 * 2179^1 (mod 10000000000000000051)\n", "found factorization 47^6997458219288137252 = -1^1 * 3^1 * 19^1 * 67^2 * 103^1 * 163^1 * 421^1 * 1453^1 * 1933^1 (mod 10000000000000000051)\n", "found factorization 47^5368562660875596157 = -1^1 * 2^2 * 5^1 * 7^1 * 13^1 * 53^1 * 109^2 * 613^1 * 859^1 * 4967^1 (mod 10000000000000000051)\n", "found factorization 47^776947878167972109 = 2^8 * 13^1 * 31^1 * 37^1 * 79^1 * 101^1 * 409^1 * 2417^1 (mod 10000000000000000051)\n", "found factorization 47^9722523860545029318 = -1^1 * 2^2 * 5^1 * 11^1 * 23^1 * 73^1 * 127^1 * 233^1 * 277^1 * 1303^1 * 2441^1 (mod 10000000000000000051)\n", "found factorization 47^4308357245789554919 = -1^1 * 2^2 * 3^6 * 13^1 * 19^1 * 83^1 * 269^1 * 367^1 * 389^1 * 617^1 (mod 10000000000000000051)\n", "found factorization 47^7505519678745940880 = -1^1 * 2^3 * 3^4 * 5^3 * 11^1 * 67^1 * 503^1 * 3391^1 * 3889^1 (mod 10000000000000000051)\n", "found factorization 47^3392325432318618169 = -1^1 * 17^1 * 29^1 * 59^1 * 61^1 * 149^1 * 571^1 * 2633^1 * 4483^1 (mod 10000000000000000051)\n", "found factorization 47^2225212247596000895 = -1^1 * 2^4 * 3^1 * 5^3 * 53^1 * 59^1 * 211^1 * 607^1 * 773^1 * 3391^1 (mod 10000000000000000051)\n", "found factorization 47^7013295151063629717 = -1^1 * 2^1 * 7^2 * 11^1 * 13^1 * 211^1 * 509^1 * 857^1 * 1063^1 * 2609^1 (mod 10000000000000000051)\n", "found factorization 47^956925442214697627 = -1^1 * 5^2 * 7^1 * 17^3 * 19^1 * 349^1 * 757^1 * 761^1 * 1307^1 (mod 10000000000000000051)\n", "found factorization 47^6450991525921814330 = -1^1 * 2^3 * 5^1 * 7^1 * 17^1 * 67^1 * 79^1 * 227^1 * 463^1 * 853^1 * 2341^1 (mod 10000000000000000051)\n", "found factorization 47^4861666169539904791 = 7^1 * 11^1 * 17^1 * 43^1 * 211^1 * 311^1 * 313^1 * 331^1 * 2351^1 (mod 10000000000000000051)\n", "found factorization 47^3088522635126857467 = -1^1 * 2^1 * 3^2 * 7^2 * 37^1 * 163^1 * 2879^1 * 3581^1 * 3847^1 (mod 10000000000000000051)\n", "found factorization 47^3358720939023079793 = -1^1 * 3^2 * 7^1 * 11^1 * 83^1 * 109^1 * 439^1 * 839^1 * 1361^1 * 1531^1 (mod 10000000000000000051)\n", "found factorization 47^2988839167316057473 = 2^4 * 3^5 * 5^1 * 7^2 * 19^1 * 257^1 * 883^1 * 1187^1 * 1511^1 (mod 10000000000000000051)\n", "found factorization 47^4145331219989760478 = -1^1 * 2^1 * 11^1 * 157^1 * 457^1 * 571^1 * 1481^1 * 2063^1 * 2699^1 (mod 10000000000000000051)\n", "found factorization 47^5226793216623825183 = -1^1 * 2^1 * 3^3 * 7^1 * 11^1 * 227^1 * 443^1 * 1471^1 * 2293^1 * 2371^1 (mod 10000000000000000051)\n", "found factorization 47^8283999020028622386 = -1^1 * 2^1 * 5^7 * 7^3 * 11^1 * 83^1 * 233^1 * 439^1 * 547^1 (mod 10000000000000000051)\n", "found factorization 47^6845850317115268142 = 11^1 * 29^1 * 61^1 * 71^1 * 131^2 * 239^1 * 821^1 * 1429^1 (mod 10000000000000000051)\n", "found factorization 47^6599615100940580515 = 2^4 * 3^3 * 173^1 * 229^1 * 373^1 * 409^1 * 613^1 * 829^1 (mod 10000000000000000051)\n", "found factorization 47^5486724233338059988 = -1^1 * 2^2 * 11^2 * 97^1 * 571^1 * 587^1 * 593^1 * 727^1 * 1427^1 (mod 10000000000000000051)\n", "found factorization 47^1612039955949810650 = -1^1 * 2^2 * 11^1 * 13^3 * 83^1 * 193^1 * 743^1 * 1009^1 * 1949^1 (mod 10000000000000000051)\n", "found factorization 47^614191692845647905 = 3^2 * 53^1 * 83^1 * 1811^1 * 2309^1 * 3593^1 * 4159^1 (mod 10000000000000000051)\n", "found factorization 47^8390058901047062362 = 3^1 * 7^1 * 11^1 * 71^1 * 79^1 * 193^1 * 431^1 * 1459^1 * 4481^1 (mod 10000000000000000051)\n", "found factorization 47^4582886555950805428 = -1^1 * 2^2 * 3^4 * 5^1 * 83^1 * 197^1 * 239^1 * 647^1 * 757^1 * 2909^1 (mod 10000000000000000051)\n", "found factorization 47^5453447591934009593 = -1^1 * 2^2 * 179^1 * 613^1 * 1229^1 * 2053^1 * 2267^1 * 3119^1 (mod 10000000000000000051)\n", "found factorization 47^2182914775768441306 = 2^7 * 19^2 * 1087^1 * 2633^1 * 3083^1 * 3643^1 (mod 10000000000000000051)\n", "found factorization 47^7694122436427527486 = 2^1 * 3^1 * 5^4 * 13^1 * 17^2 * 41^1 * 59^1 * 89^1 * 1223^1 * 1619^1 (mod 10000000000000000051)\n", "found factorization 47^3949379364605463656 = 2^3 * 3^2 * 5^1 * 79^1 * 409^1 * 433^1 * 739^1 * 953^1 * 2381^1 (mod 10000000000000000051)\n", "found factorization 47^3149029509900564330 = -1^1 * 2^1 * 5^1 * 71^1 * 1439^1 * 1481^1 * 4259^1 * 4909^1 (mod 10000000000000000051)\n", "found factorization 47^1575266652864365178 = -1^1 * 461^1 * 659^1 * 1249^1 * 2213^1 * 2957^1 * 3907^1 (mod 10000000000000000051)\n", "found factorization 47^7576947466248802589 = 2^1 * 3^1 * 11^1 * 89^1 * 113^1 * 307^1 * 1531^1 * 2437^1 * 4373^1 (mod 10000000000000000051)\n", "found factorization 47^8267438627830703531 = 2^6 * 3^1 * 11^1 * 13^2 * 23^1 * 53^1 * 821^1 * 1021^1 * 2903^1 (mod 10000000000000000051)\n", "found factorization 47^1150907916133544941 = 3^4 * 181^1 * 461^1 * 947^1 * 1153^1 * 1451^1 (mod 10000000000000000051)\n", "found factorization 47^832683721404463213 = 5^1 * 7^2 * 19^1 * 43^1 * 1597^1 * 2063^1 * 2099^1 * 4993^1 (mod 10000000000000000051)\n", "found factorization 47^7775544234288089361 = 11^1 * 13^1 * 37^1 * 149^1 * 461^1 * 1399^1 * 2383^1 * 2971^1 (mod 10000000000000000051)\n", "found factorization 47^3211902203503938684 = 3^1 * 5^1 * 7^2 * 11^1 * 13^1 * 37^1 * 251^1 * 367^1 * 2399^1 * 2473^1 (mod 10000000000000000051)\n", "found factorization 47^4038186452332630561 = 2^8 * 3^1 * 11^1 * 19^2 * 47^2 * 311^1 * 773^1 * 2029^1 (mod 10000000000000000051)\n", "found factorization 47^6418929545664832536 = -1^1 * 2^1 * 3^1 * 7^3 * 31^1 * 83^1 * 89^1 * 101^1 * 167^1 * 179^1 * 1277^1 (mod 10000000000000000051)\n", "found factorization 47^3606765994715434133 = 7^1 * 17^1 * 37^1 * 193^1 * 977^1 * 1321^1 * 1873^1 * 2341^1 (mod 10000000000000000051)\n", "found factorization 47^6406493994220476225 = -1^1 * 2^1 * 5^1 * 7^1 * 97^1 * 163^1 * 431^1 * 937^1 * 1889^1 * 4729^1 (mod 10000000000000000051)\n", "found factorization 47^465300836661267803 = -1^1 * 2^5 * 41^2 * 79^1 * 181^1 * 257^1 * 2591^1 * 4621^1 (mod 10000000000000000051)\n", "found factorization 47^2763520366398235161 = -1^1 * 3^2 * 7^1 * 41^1 * 89^1 * 149^1 * 193^1 * 311^1 * 541^1 * 2389^1 (mod 10000000000000000051)\n", "found factorization 47^8196585122558850259 = -1^1 * 2^2 * 5^1 * 7^1 * 97^1 * 277^1 * 307^1 * 577^1 * 2671^1 * 4507^1 (mod 10000000000000000051)\n", "found factorization 47^9891625001741231152 = 2^1 * 5^1 * 29^1 * 43^1 * 53^1 * 83^1 * 107^1 * 151^1 * 1451^1 * 1481^1 (mod 10000000000000000051)\n", "found factorization 47^9168021568836619451 = 2^2 * 3^1 * 17^1 * 23^1 * 103^1 * 127^1 * 173^1 * 277^1 * 577^1 * 1999^1 (mod 10000000000000000051)\n", "found factorization 47^6465966842813896812 = 37^1 * 193^1 * 337^1 * 827^1 * 1229^1 * 1237^1 * 3049^1 (mod 10000000000000000051)\n", "found factorization 47^1500123202847697173 = 2^1 * 7^1 * 13^1 * 17^1 * 23^1 * 1993^1 * 2137^1 * 2143^1 * 4111^1 (mod 10000000000000000051)\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "found factorization 47^2862574341882497157 = 2^1 * 5^1 * 79^1 * 587^1 * 677^1 * 2131^1 * 2803^1 * 4019^1 (mod 10000000000000000051)\n", "found factorization 47^3565829746697688170 = -1^1 * 13^1 * 101^1 * 131^1 * 929^1 * 1279^1 * 1423^1 * 4993^1 (mod 10000000000000000051)\n", "found factorization 47^2396968054994230789 = 2^6 * 3^1 * 7^2 * 19^1 * 73^1 * 173^2 * 593^1 * 1913^1 (mod 10000000000000000051)\n", "found factorization 47^5112545423367201006 = -1^1 * 2^1 * 3^1 * 23^1 * 29^1 * 43^1 * 199^1 * 211^1 * 233^1 * 929^1 * 3701^1 (mod 10000000000000000051)\n", "found factorization 47^1350155702805810727 = 2^1 * 3^2 * 23^1 * 31^1 * 43^1 * 331^1 * 593^1 * 643^1 * 757^1 (mod 10000000000000000051)\n" ] }, { "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;36mlogarithmTable\u001b[0;34m(a, p, base, trace)\u001b[0m\n\u001b[1;32m 108\u001b[0m ' * '.join(\"%d^%d\" % (q, e) for q, e in zip(base, f) if e != 0), p))\n\u001b[1;32m 109\u001b[0m \u001b[0mMM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMatrix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlist\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[0mf\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--> 110\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0mall\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mMatrix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mF\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mMM\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrank\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0mr\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mF\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfields\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 111\u001b[0m \u001b[0mM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMM\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 112\u001b[0m \u001b[0mr\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[0;32m~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py\u001b[0m in \u001b[0;36m\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 108\u001b[0m ' * '.join(\"%d^%d\" % (q, e) for q, e in zip(base, f) if e != 0), p))\n\u001b[1;32m 109\u001b[0m \u001b[0mMM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMatrix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlist\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[0mf\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--> 110\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0mall\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mMatrix\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mF\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mMM\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrank\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0mr\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mF\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfields\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 111\u001b[0m \u001b[0mM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMM\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 112\u001b[0m \u001b[0mr\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[0;32m~/sage/local/lib/python3.8/site-packages/sage/matrix/constructor.pyx\u001b[0m in \u001b[0;36msage.matrix.constructor.matrix (build/cythonized/sage/matrix/constructor.c:2529)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 633\u001b[0m \"\"\"\n\u001b[1;32m 634\u001b[0m \u001b[0mimmutable\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mkwds\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'immutable'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 635\u001b[0;31m \u001b[0mM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mMatrixArgs\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[0mmatrix\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 636\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mimmutable\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 637\u001b[0m \u001b[0mM\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mset_immutable\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/matrix/args.pyx\u001b[0m in \u001b[0;36msage.matrix.args.MatrixArgs.matrix (build/cythonized/sage/matrix/args.c:7953)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 662\u001b[0m \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 663\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 664\u001b[0;31m \u001b[0mM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mspace\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoerce\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mconvert\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 665\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 666\u001b[0m \u001b[0;31m# Also store the matrix to support multiple calls of matrix()\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/matrix/matrix_space.py\u001b[0m in \u001b[0;36m__call__\u001b[0;34m(self, entries, coerce, copy)\u001b[0m\n\u001b[1;32m 849\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 850\u001b[0m \"\"\"\n\u001b[0;32m--> 851\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0melement_class\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mentries\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcopy\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoerce\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 852\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 853\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mchange_ring\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mR\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/matrix/matrix_modn_dense_template.pxi\u001b[0m in \u001b[0;36msage.matrix.matrix_modn_dense_float.Matrix_modn_dense_template.__init__ (build/cythonized/sage/matrix/matrix_modn_dense_float.cpp:7223)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 530\u001b[0m \u001b[0mv\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_matrix\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 531\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mma\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mncols\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--> 532\u001b[0;31m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mit\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 533\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 534\u001b[0m \u001b[0mtmp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m<\u001b[0m\u001b[0mlong\u001b[0m\u001b[0;34m>\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mp\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/matrix/args.pyx\u001b[0m in \u001b[0;36miter (build/cythonized/sage/matrix/args.c:7374)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 559\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnrows\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 560\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mncols\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--> 561\u001b[0;31m \u001b[0msig_check\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 562\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 563\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mconvert\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneed_to_convert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\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;31mKeyboardInterrupt\u001b[0m: " ] }, { "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;36mindexCalculus\u001b[0;34m(a, b, p, base, table, trace)\u001b[0m\n\u001b[1;32m 126\u001b[0m \u001b[0mbase\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtable\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mzip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\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 127\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 128\u001b[0;31m \u001b[0mtable\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlogarithmTable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbase\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrace\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdescend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrace\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 129\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 130\u001b[0m \u001b[0mi\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrandint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py\u001b[0m in \u001b[0;36mlogarithmTable\u001b[0;34m(a, p, base, trace)\u001b[0m\n\u001b[1;32m 101\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 102\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 103\u001b[0;31m \u001b[0mf\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfactorizeByBase\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbase\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\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 104\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 105\u001b[0m \u001b[0;32mcontinue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/factorization.py\u001b[0m in \u001b[0;36mfactorizeByBase\u001b[0;34m(n, base, m)\u001b[0m\n\u001b[1;32m 138\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0midx\u001b[0m \u001b[0;32mis\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 139\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 140\u001b[0;31m \u001b[0mfactors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfactorizeByBase\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbase\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 141\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mfactors\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 142\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/factorization.py\u001b[0m in \u001b[0;36mfactorizeByBase\u001b[0;34m(n, base, m)\u001b[0m\n\u001b[1;32m 131\u001b[0m \u001b[0mfactors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mbase\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 132\u001b[0m \u001b[0mx\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[0;32m--> 133\u001b[0;31m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m \u001b[0;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbase\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 134\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mp\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 135\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m//=\u001b[0m \u001b[0mp\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": [ "pp = 10000000000000000051\n", "base = [-1] + prime_range(5000)\n", "table = %time logarithmTable(aa, pp, base, trace = True)\n", "%time indexCalculus(aa, bb, pp, base, table, trace = True)" ] } ], "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 }