# Index calculus algorithm¶

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.

In [1]:
from algorithms.euclidean import gcd
from algorithms.factorization import factorizeByBase

p = 9330887
a = 5
b1 = 4389733
b2 = 1234567


We will use a base consisting of $-1$ and all primes less than $50$.

In [2]:
base = [-1] + prime_range(50)


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.

In [3]:
set_random_seed(0)

v = []
s = set()
r, l = 0, len(base)
M = Matrix(nrows=0, ncols=l)
while r < l:
i = randint(1, p-1)
if i in s:
continue
x = pow(a, i, p)
f = factorizeByBase(Integer(x), base, p)
if not f:
continue
MM = Matrix(list(M) + [f])
rr = MM.rank()
if rr > r:
M = MM
r = rr
v.append(i)
print(M)
print(v)

[1 0 2 1 0 0 1 0 0 0 0 0 0 0 2 0]
[1 0 1 0 0 0 0 0 0 0 0 1 3 0 0 0]
[0 3 8 0 1 0 0 0 0 1 0 0 0 0 0 0]
[0 1 2 1 2 0 0 0 0 0 1 0 1 0 0 0]
[1 0 0 0 1 3 1 0 0 0 0 0 0 1 0 0]
[1 4 0 0 1 0 0 1 0 0 1 0 0 0 0 0]
[1 2 0 3 3 0 0 0 0 1 0 0 0 0 0 0]
[1 2 2 0 0 1 1 1 0 1 0 0 0 0 0 0]
[0 8 1 0 0 2 0 0 0 0 0 0 0 0 1 0]
[0 3 1 0 0 1 0 0 1 1 0 0 0 0 0 0]
[0 5 0 1 0 0 0 1 0 0 1 0 1 0 0 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 2 0 0]
[0 0 0 0 2 0 0 0 1 0 1 0 0 0 0 1]
[0 1 3 0 4 0 1 0 0 0 0 0 0 0 0 0]
[1 4 1 5 0 0 0 0 0 1 0 0 0 0 0 0]
[1 1 1 2 0 2 1 0 1 0 0 0 0 0 0 0]
[1342485, 669118, 7237936, 7922551, 9149713, 4288717, 563606, 4482702, 7606125, 6167680, 7916700, 6825736, 4712055, 7120183, 7905940, 4584527]


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.

In [4]:
t = M^-1 * Matrix(zip(v)) % (p-1)
t

Out[4]:
[4665443]
[6670912]
[2030334]
[      1]
[5786904]
[1078197]
[8534197]
[7606749]
[8519903]
[2519168]
[6200403]
[9068634]
[7409417]
[5590350]
[6037417]
[6410599]

Let us verify that the table is correct.

In [5]:
[pow(a, i, p) for i, in t]

Out[5]:
[9330886, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

We can now find a power of $b_i$ that can be factorized with our base. We will use the following function.

In [6]:
def findPower(b, p, base):
while True:
i = randint(1, p-1)
x = pow(b, i, p)
f = factorizeByBase(Integer(x), base, p)
if not f:
continue
return (i, f)


Let us find such a power of $b_1$ and its factorization.

In [7]:
i1, f1 = findPower(b1, p, base)
i1, f1

Out[7]:
(3157805, [0, 0, 3, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0])

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.

In [8]:
g1 = gcd(i1, p-1)
g1

Out[8]:
1

We can thus obtain a solution modulo $p-1$ divided by this GCD.

In [9]:
m1 = ((p-1)/g1)
(x1,), = Matrix([f1])*t / i1 % m1
x1

Out[9]:
5753305

Let us now put this into a function which will also verify the potential solutions.

In [10]:
def checkSolutions(a, b, p, t, i, f):
g = gcd(i, p-1)
m = (p-1)/g
(x,), = Matrix([f])*t / i % m
for j in range(g):
y = pow(a, x, p)
print("%d^%d mod %d = %d" % (a, x, p, y))
if y == b:
return x
x += m

checkSolutions(a, b1, p, t, i1, f1)

5^5753305 mod 9330887 = 4389733

Out[10]:
5753305

We have thus computed $\log_a b_1$. Let us now compute $\log_a b_2$.

In [11]:
i2, f2 = findPower(b2, p, base)
i2, f2

Out[11]:
(5353502, [0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0])
In [12]:
checkSolutions(a, b2, p, t, i2, f2)

5^2608331 mod 9330887 = 8096320
5^7273774 mod 9330887 = 1234567

Out[12]:
7273774

## Running time comparison¶

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.

In [13]:
from algorithms.discreteLogarithm import logarithmTable, indexCalculus

aa = 47
bb = 191

In [14]:
pp = 100000000003
table = %time logarithmTable(aa, pp, base, trace = True)
print(table)
%time indexCalculus(aa, bb, pp, base, table, trace = True)

found factorization 47^84497243479 = -1^1 * 2^1 * 3^1 * 5^6 * 7^1 * 11^2 * 23^1 * 29^1 (mod 100000000003)
found factorization 47^55045977185 = 2^1 * 11^1 * 13^3 * 19^2 * 37^1 * 43^1 (mod 100000000003)
found factorization 47^93740896216 = 13^4 * 23^2 * 29^1 (mod 100000000003)
found factorization 47^62252472984 = -1^1 * 2^5 * 3^2 * 5^1 * 7^1 * 11^1 * 17^1 * 19^2 * 41^1 (mod 100000000003)
found factorization 47^98257292990 = -1^1 * 3^1 * 23^4 * 41^1 * 47^1 (mod 100000000003)
found factorization 47^57017421058 = 2^5 * 13^2 * 17^1 * 23^2 (mod 100000000003)
found factorization 47^63831308173 = -1^1 * 2^3 * 5^3 * 7^2 * 19^1 * 31^1 * 41^1 * 43^1 (mod 100000000003)
found factorization 47^67516991484 = -1^1 * 3^1 * 5^1 * 7^4 * 11^2 * 19^1 * 31^2 (mod 100000000003)
found factorization 47^33797337121 = 2^10 * 3^2 * 5^2 * 11^1 * 43^1 * 47^1 (mod 100000000003)
found factorization 47^17498086004 = 2^1 * 7^2 * 11^2 * 13^1 * 29^1 * 31^1 * 43^1 (mod 100000000003)
found factorization 47^31657988253 = 2^1 * 7^7 * 17^1 * 31^1 (mod 100000000003)
found factorization 47^60619654035 = 2^3 * 3^4 * 5^2 * 13^2 * 23^1 * 47^1 (mod 100000000003)
found factorization 47^92434058549 = 2^6 * 3^3 * 5^3 * 13^1 * 19^1 * 31^1 * 37^1 (mod 100000000003)
found factorization 47^56456319013 = 2^3 * 3^5 * 5^1 * 11^1 * 13^1 * 17^1 * 47^2 (mod 100000000003)
found factorization 47^55622355719 = 2^9 * 3^1 * 7^2 * 13^1 * 23^1 * 37^1 (mod 100000000003)
rank not increased, discarding
found factorization 47^52004730500 = 3^3 * 7^2 * 17^1 * 23^1 * 31^2 * 47^1 (mod 100000000003)
found factorization 47^12484556881 = 2^11 * 5^1 * 11^1 * 23^2 * 37^1 * 43^1 (mod 100000000003)
rank not increased, discarding
found factorization 47^96345630522 = 2^2 * 3^1 * 5^3 * 7^2 * 19^2 * 41^2 (mod 100000000003)
rank not increased, discarding
found factorization 47^29509646289 = 3^2 * 5^1 * 11^1 * 13^1 * 19^2 * 31^1 * 41^1 (mod 100000000003)
rank not increased, discarding
found factorization 47^90014436945 = 2^6 * 3^2 * 13^1 * 17^2 * 31^2 * 43^1 (mod 100000000003)
rank not increased, discarding
found factorization 47^91058239375 = -1^1 * 2^5 * 3^5 * 5^8 * 29^1 (mod 100000000003)
CPU times: user 4.04 s, sys: 48.7 ms, total: 4.08 s
Wall time: 4.1 s
[50000000001, 88948660783, 74403602789, 76906212201, 2995382539, 11520765452, 33861633403, 95303711677, 78308239391, 74623569337, 9047223934, 26437938024, 66204838085, 75359412859, 30170333882, 1]
found factorization 191^75958412224 = 7^1 * 11^2 * 13^4 * 37^1 * 43^1 (mod 100000000003)
checking 2 solutions for 47^x = 191, x = 6935101882 (mod 50000000001)
47^6935101882 mod 100000000003 = 191
CPU times: user 1.03 s, sys: 19.6 ms, total: 1.05 s
Wall time: 1.06 s

Out[14]:
6935101882
In [15]:
pp = 10000000000000000051
base = [-1] + prime_range(5000)
table = %time logarithmTable(aa, pp, base, trace = True)
%time indexCalculus(aa, bb, pp, base, table, trace = True)

found factorization 47^2179497432067614218 = 2^4 * 5^1 * 107^1 * 293^1 * 317^1 * 643^1 * 2591^1 * 4793^1 (mod 10000000000000000051)
found factorization 47^8204853581526273040 = 2^1 * 3^3 * 7^1 * 19^1 * 101^1 * 109^1 * 1091^1 * 1567^1 * 1889^1 (mod 10000000000000000051)
found factorization 47^5332758726454119214 = 2^4 * 11^1 * 17^1 * 73^1 * 593^1 * 883^1 * 1013^1 * 3889^1 (mod 10000000000000000051)
found factorization 47^5587859396418665063 = 23^1 * 227^2 * 307^1 * 311^1 * 701^1 * 2659^1 (mod 10000000000000000051)
found factorization 47^226077030606921208 = 2^3 * 5^3 * 29^1 * 137^1 * 157^1 * 389^1 * 593^1 * 2957^1 (mod 10000000000000000051)
found factorization 47^999096871500948476 = -1^1 * 2^1 * 379^1 * 677^1 * 821^1 * 1049^1 * 1627^1 * 4159^1 (mod 10000000000000000051)
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)
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)
found factorization 47^2859630369235796494 = -1^1 * 2^1 * 3^1 * 17^1 * 181^1 * 293^1 * 1619^1 * 2801^1 * 4943^1 (mod 10000000000000000051)
found factorization 47^4193241327745824698 = 3^1 * 89^1 * 211^1 * 229^1 * 2371^1 * 3049^1 * 4273^1 (mod 10000000000000000051)
found factorization 47^1273501793223196459 = -1^1 * 3^1 * 307^1 * 577^1 * 619^1 * 1117^1 * 1999^1 * 3467^1 (mod 10000000000000000051)
found factorization 47^1769187930605990394 = -1^1 * 3^1 * 13^1 * 83^1 * 571^1 * 991^1 * 1061^1 * 1777^1 * 2069^1 (mod 10000000000000000051)
found factorization 47^4780857940387103231 = -1^1 * 13^1 * 71^1 * 101^1 * 137^1 * 701^1 * 1051^1 * 2843^1 (mod 10000000000000000051)
found factorization 47^1444277781522927847 = -1^1 * 2^2 * 523^1 * 3121^1 * 3541^1 * 4003^1 * 4517^1 (mod 10000000000000000051)
found factorization 47^4435853557423186328 = 2^1 * 3^1 * 17^2 * 43^1 * 149^1 * 409^1 * 587^1 * 1481^1 * 1663^1 (mod 10000000000000000051)
found factorization 47^8837828089629176966 = -1^1 * 2^3 * 3^6 * 7^1 * 83^1 * 281^1 * 727^1 * 2203^1 * 4339^1 (mod 10000000000000000051)
found factorization 47^7987897606114726628 = -1^1 * 2^4 * 3^2 * 53^1 * 83^1 * 271^1 * 757^1 * 2671^1 * 3089^1 (mod 10000000000000000051)
found factorization 47^8178769214846705235 = 2^2 * 7^1 * 157^1 * 269^1 * 419^1 * 1327^1 * 1697^1 * 4817^1 (mod 10000000000000000051)
found factorization 47^8463228572032171234 = 2^1 * 3^3 * 17^1 * 113^1 * 233^1 * 1061^1 * 1723^1 * 3389^1 (mod 10000000000000000051)
found factorization 47^8779453939329703949 = 2^3 * 5^1 * 101^1 * 103^1 * 347^1 * 1249^1 * 3769^1 * 4583^1 (mod 10000000000000000051)
found factorization 47^5474091186535589611 = -1^1 * 3^3 * 5^1 * 11^1 * 41^1 * 683^1 * 3853^1 * 4013^1 * 4409^1 (mod 10000000000000000051)
found factorization 47^4954575118402279281 = -1^1 * 2^1 * 11^1 * 47^1 * 61^1 * 191^1 * 349^1 * 457^1 * 1723^2 (mod 10000000000000000051)
found factorization 47^1518281886591774342 = -1^1 * 2^1 * 3^1 * 23^1 * 367^1 * 433^1 * 607^1 * 3089^1 * 3823^1 (mod 10000000000000000051)
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)
found factorization 47^260903128323509513 = -1^1 * 2^7 * 11^1 * 13^1 * 19^2 * 2081^1 * 2749^1 * 2803^1 (mod 10000000000000000051)
found factorization 47^2512852496525643242 = -1^1 * 2^3 * 7^1 * 17^1 * 59^1 * 131^2 * 401^1 * 1031^1 * 4157^1 (mod 10000000000000000051)
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)
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)
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)
found factorization 47^6546434270787613708 = 5^1 * 7^2 * 19^1 * 31^1 * 53^1 * 211^1 * 293^1 * 2927^1 * 4663^1 (mod 10000000000000000051)
found factorization 47^5575367014741603051 = 2^1 * 3^1 * 47^1 * 79^1 * 107^1 * 397^1 * 1049^1 * 1153^1 * 4093^1 (mod 10000000000000000051)
found factorization 47^2208189363741281117 = -1^1 * 2^2 * 3^3 * 7^2 * 23^1 * 337^1 * 1721^1 * 4337^1 * 4349^1 (mod 10000000000000000051)
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)
found factorization 47^1294056674836816677 = 2^6 * 151^1 * 199^1 * 449^1 * 479^1 * 3109^1 * 4931^1 (mod 10000000000000000051)
found factorization 47^5229989021208468051 = 2^2 * 7^1 * 73^1 * 241^1 * 367^1 * 1709^1 * 3083^1 * 3557^1 (mod 10000000000000000051)
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)
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)
found factorization 47^9445333779141676873 = 2^2 * 73^1 * 83^1 * 353^1 * 449^1 * 467^1 * 1163^1 * 3739^1 (mod 10000000000000000051)
found factorization 47^3621041543123407339 = 2^5 * 223^1 * 227^1 * 269^1 * 2081^1 * 2711^1 * 2749^1 (mod 10000000000000000051)
found factorization 47^8447974074538547891 = -1^1 * 3^1 * 5^1 * 67^2 * 347^1 * 439^1 * 569^1 * 823^1 * 881^1 (mod 10000000000000000051)
found factorization 47^9046877721977140702 = 3^1 * 11^1 * 41^1 * 47^1 * 53^1 * 283^1 * 977^1 * 2741^1 * 3659^1 (mod 10000000000000000051)
found factorization 47^1159928358980693386 = -1^1 * 2^3 * 29^1 * 199^1 * 569^1 * 829^1 * 1907^1 * 2357^1 (mod 10000000000000000051)
found factorization 47^8440250248839466090 = 19^1 * 59^1 * 293^1 * 547^1 * 1321^1 * 1489^1 * 4253^1 (mod 10000000000000000051)
found factorization 47^4408327007164968660 = -1^1 * 2^3 * 13^1 * 73^1 * 89^1 * 479^1 * 2113^1 * 2897^1 * 4153^1 (mod 10000000000000000051)
found factorization 47^9407208490524940976 = 2^1 * 7^1 * 41^1 * 53^1 * 347^1 * 617^1 * 659^1 * 857^1 * 1453^1 (mod 10000000000000000051)
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)
found factorization 47^9903874506685304914 = 3^1 * 5^2 * 7^1 * 89^1 * 271^1 * 317^1 * 2003^1 * 4799^1 (mod 10000000000000000051)
found factorization 47^6065228674828731510 = 11^1 * 13^1 * 19^1 * 73^1 * 1171^1 * 1787^1 * 2969^1 * 3943^1 (mod 10000000000000000051)
found factorization 47^1140021849073153749 = -1^1 * 3^2 * 5^4 * 7^2 * 29^1 * 59^1 * 149^1 * 1019^1 * 1567^1 (mod 10000000000000000051)
found factorization 47^6053249944320813054 = -1^1 * 23^1 * 79^1 * 181^1 * 547^1 * 1499^1 * 1987^1 * 2423^1 (mod 10000000000000000051)
found factorization 47^42816357289123641 = 2^1 * 3^1 * 13^2 * 59^1 * 317^1 * 431^1 * 433^1 * 1297^1 * 2011^1 (mod 10000000000000000051)
found factorization 47^2296847402754742070 = 2^6 * 13^1 * 29^1 * 233^2 * 359^1 * 947^1 * 3767^1 (mod 10000000000000000051)
found factorization 47^2794475815447091735 = 2^3 * 17^1 * 23^1 * 37^2 * 47^1 * 109^1 * 283^1 * 547^1 * 2879^1 (mod 10000000000000000051)
found factorization 47^423947503758756981 = 2^4 * 5^1 * 37^1 * 47^1 * 1187^1 * 1237^1 * 2113^1 * 2543^1 (mod 10000000000000000051)
found factorization 47^3969292717060976005 = -1^1 * 2^1 * 5^1 * 157^1 * 197^1 * 313^1 * 1249^1 * 3049^1 * 4937^1 (mod 10000000000000000051)
found factorization 47^1385104560440192072 = -1^1 * 2^4 * 11^1 * 17^1 * 281^1 * 359^1 * 1451^1 * 2683^1 * 3739^1 (mod 10000000000000000051)
found factorization 47^5133463935955782649 = 2^1 * 61^1 * 71^1 * 89^1 * 661^1 * 1217^1 * 1283^1 * 1447^1 (mod 10000000000000000051)
found factorization 47^1255958701434779082 = 37^1 * 167^1 * 191^1 * 269^1 * 1423^1 * 2287^1 * 4993^1 (mod 10000000000000000051)
found factorization 47^5773134569651730973 = 3^1 * 113^1 * 331^1 * 419^1 * 2027^1 * 2377^1 * 3617^1 (mod 10000000000000000051)
found factorization 47^5782260890911082530 = 2^2 * 3^1 * 107^1 * 113^1 * 157^1 * 173^1 * 199^1 * 521^1 * 3407^1 (mod 10000000000000000051)
found factorization 47^7021090602000602927 = 5^6 * 109^1 * 173^1 * 1453^1 * 4159^1 * 4787^1 (mod 10000000000000000051)
found factorization 47^757394578626478646 = -1^1 * 2^1 * 3^1 * 37^2 * 131^1 * 1201^1 * 1291^1 * 1433^1 * 2477^1 (mod 10000000000000000051)
found factorization 47^3670642106027243491 = 3^5 * 5^1 * 11^1 * 59^1 * 89^1 * 113^1 * 809^1 * 1619^1 (mod 10000000000000000051)
found factorization 47^1152506915024311731 = -1^1 * 3^1 * 5^1 * 11^1 * 347^1 * 1637^1 * 3019^1 * 3467^1 * 4339^1 (mod 10000000000000000051)
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)
found factorization 47^2342528196895492096 = 2^2 * 5^2 * 23^1 * 79^1 * 101^1 * 179^1 * 613^1 * 907^1 * 3767^1 (mod 10000000000000000051)
found factorization 47^325186157213753234 = 2^2 * 3^1 * 47^1 * 257^1 * 1171^1 * 2663^1 * 2963^1 * 3571^1 (mod 10000000000000000051)
found factorization 47^7708485993070530200 = -1^1 * 2^1 * 11^1 * 73^1 * 151^1 * 367^1 * 859^1 * 1039^1 * 2221^1 (mod 10000000000000000051)
found factorization 47^1235282735191417043 = -1^1 * 2^1 * 5^1 * 59^1 * 373^1 * 829^1 * 1699^1 * 1721^1 * 2659^1 (mod 10000000000000000051)
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)
found factorization 47^2124989123194036989 = 3^2 * 5^1 * 11^1 * 379^1 * 857^1 * 1033^1 * 2243^1 * 3299^1 (mod 10000000000000000051)
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)
found factorization 47^203327952928256998 = -1^1 * 5^3 * 53^1 * 277^1 * 283^1 * 631^1 * 787^1 * 4337^1 (mod 10000000000000000051)
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)
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)
found factorization 47^1258660080508409033 = -1^1 * 2^4 * 3^1 * 5^2 * 443^1 * 571^1 * 2663^1 * 3301^1 * 3691^1 (mod 10000000000000000051)
found factorization 47^7457774780564176939 = 2^3 * 5^2 * 11^1 * 41^1 * 61^1 * 101^1 * 1873^1 * 2609^1 * 3581^1 (mod 10000000000000000051)
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)
found factorization 47^7560804650852420591 = -1^1 * 5^3 * 7^1 * 31^1 * 659^1 * 727^1 * 2801^1 * 3391^1 (mod 10000000000000000051)
found factorization 47^1164723476676231606 = 2^1 * 3^1 * 71^1 * 107^1 * 1747^1 * 2039^1 * 3779^1 * 4339^1 (mod 10000000000000000051)
found factorization 47^3080318643732974544 = -1^1 * 769^1 * 797^1 * 859^1 * 1621^1 * 2281^1 * 4283^1 (mod 10000000000000000051)
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)
found factorization 47^1484037391417127896 = -1^1 * 2^1 * 7^1 * 137^1 * 157^1 * 823^1 * 2113^1 * 2729^1 * 3251^1 (mod 10000000000000000051)
found factorization 47^1577828132803256958 = 2^5 * 3^2 * 5^2 * 317^1 * 797^1 * 1129^1 * 1483^1 * 3011^1 (mod 10000000000000000051)
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)
found factorization 47^2501315712506904711 = -1^1 * 2^3 * 11^4 * 17^1 * 53^1 * 197^1 * 223^1 * 479^1 * 2953^1 (mod 10000000000000000051)
found factorization 47^194308953719522900 = 2^1 * 7^2 * 19^1 * 241^1 * 251^1 * 1993^1 * 2671^1 * 2753^1 (mod 10000000000000000051)
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)
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)
found factorization 47^1243416335509546261 = 2^4 * 3^4 * 5^1 * 17^2 * 19^1 * 103^1 * 239^1 * 499^1 * 751^1 (mod 10000000000000000051)
found factorization 47^4022154907862586101 = -1^1 * 2^2 * 7^1 * 67^1 * 151^1 * 251^1 * 977^1 * 2357^1 * 4001^1 (mod 10000000000000000051)
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)
found factorization 47^8206902393169777525 = -1^1 * 17^1 * 223^2 * 347^1 * 1291^1 * 1879^1 * 2819^1 (mod 10000000000000000051)
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)
found factorization 47^9742055419422140301 = 2^3 * 3^1 * 109^1 * 337^1 * 977^1 * 1367^1 * 1741^1 * 4481^1 (mod 10000000000000000051)
found factorization 47^3388856273798759752 = 37^1 * 107^1 * 419^1 * 563^1 * 1523^1 * 2087^1 * 2207^1 (mod 10000000000000000051)
found factorization 47^1051027178071525214 = 5^1 * 11^1 * 17^2 * 101^1 * 359^1 * 1847^1 * 2549^2 (mod 10000000000000000051)
found factorization 47^9939929902803808110 = -1^1 * 2^3 * 7^1 * 131^1 * 257^1 * 307^1 * 607^1 * 1979^1 * 4451^1 (mod 10000000000000000051)
found factorization 47^2396427496742989023 = -1^1 * 2^1 * 37^2 * 61^1 * 83^1 * 337^1 * 431^1 * 739^1 * 2053^1 (mod 10000000000000000051)
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)
found factorization 47^7155863318760889193 = -1^1 * 17^1 * 23^1 * 307^1 * 2297^1 * 2339^1 * 2473^1 * 4079^1 (mod 10000000000000000051)
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)
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)
found factorization 47^2499771078615744604 = -1^1 * 2^3 * 61^1 * 283^1 * 887^1 * 1913^1 * 4159^1 * 4651^1 (mod 10000000000000000051)
found factorization 47^7423207484577238868 = -1^1 * 2^2 * 37^1 * 613^1 * 1231^1 * 3067^1 * 4463^1 * 4787^1 (mod 10000000000000000051)
found factorization 47^668396945569389854 = 2^3 * 43^2 * 179^1 * 181^1 * 761^1 * 947^1 * 3539^1 (mod 10000000000000000051)
found factorization 47^6419321998601359324 = -1^1 * 2^1 * 17^1 * 37^1 * 89^1 * 1783^1 * 2113^1 * 2473^1 * 3121^1 (mod 10000000000000000051)
found factorization 47^7731529323320689560 = 2^1 * 13^1 * 29^1 * 31^1 * 157^1 * 337^1 * 1361^1 * 1913^1 * 2287^1 (mod 10000000000000000051)
found factorization 47^6047275738649906509 = 23^1 * 547^1 * 2729^1 * 3119^1 * 4297^1 * 4493^1 (mod 10000000000000000051)
found factorization 47^7942897863060992359 = 3^2 * 43^1 * 197^1 * 929^1 * 1151^1 * 1223^1 * 4133^1 (mod 10000000000000000051)
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)
found factorization 47^1487234489128201129 = 2^1 * 3^1 * 5^1 * 13^2 * 23^3 * 149^1 * 211^1 * 1069^1 * 2141^1 (mod 10000000000000000051)
found factorization 47^4222779078693727678 = 2^1 * 3^2 * 7^2 * 17^1 * 67^1 * 499^1 * 1913^1 * 2857^1 * 3571^1 (mod 10000000000000000051)
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)
found factorization 47^4916267078838154529 = 2^1 * 7^1 * 17^1 * 113^1 * 683^1 * 1723^1 * 3361^1 * 4463^1 (mod 10000000000000000051)
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)
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)
found factorization 47^3271660484333895736 = 2^1 * 5^1 * 13^1 * 59^1 * 67^1 * 127^1 * 439^1 * 839^1 * 4021^1 (mod 10000000000000000051)
found factorization 47^1871198672101494856 = 5^1 * 11^1 * 107^1 * 257^1 * 571^1 * 1019^1 * 2237^1 * 4139^1 (mod 10000000000000000051)
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)
found factorization 47^4559727615371219210 = 3^1 * 7^1 * 157^1 * 227^1 * 787^1 * 797^1 * 4423^1 * 4457^1 (mod 10000000000000000051)
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)
found factorization 47^5160252247840033863 = -1^1 * 2^1 * 7^1 * 89^1 * 631^1 * 787^1 * 1373^1 * 2713^1 * 3881^1 (mod 10000000000000000051)
found factorization 47^1138978953907096984 = 2^2 * 3^1 * 29^1 * 47^1 * 269^1 * 337^1 * 353^1 * 3559^1 * 3989^1 (mod 10000000000000000051)
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)
found factorization 47^5086945910651030397 = -1^1 * 3^1 * 89^1 * 127^1 * 281^1 * 311^1 * 401^1 * 947^1 * 1609^1 (mod 10000000000000000051)
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)
found factorization 47^8961760904011983737 = -1^1 * 2^2 * 13^1 * 1201^1 * 1627^1 * 1721^1 * 1759^1 * 4967^1 (mod 10000000000000000051)
found factorization 47^1691865556539576999 = 2^3 * 13^1 * 17^2 * 29^1 * 103^1 * 149^1 * 157^1 * 307^1 * 3779^1 (mod 10000000000000000051)
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)
found factorization 47^5770402188118517533 = -1^1 * 2^2 * 13^3 * 43^1 * 937^1 * 1559^1 * 2029^1 * 4787^1 (mod 10000000000000000051)
found factorization 47^8310336347054423603 = 31^1 * 61^1 * 487^1 * 983^1 * 1511^1 * 1531^1 * 4463^1 (mod 10000000000000000051)
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)
found factorization 47^6997458219288137252 = -1^1 * 3^1 * 19^1 * 67^2 * 103^1 * 163^1 * 421^1 * 1453^1 * 1933^1 (mod 10000000000000000051)
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)
found factorization 47^776947878167972109 = 2^8 * 13^1 * 31^1 * 37^1 * 79^1 * 101^1 * 409^1 * 2417^1 (mod 10000000000000000051)
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)
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)
found factorization 47^7505519678745940880 = -1^1 * 2^3 * 3^4 * 5^3 * 11^1 * 67^1 * 503^1 * 3391^1 * 3889^1 (mod 10000000000000000051)
found factorization 47^3392325432318618169 = -1^1 * 17^1 * 29^1 * 59^1 * 61^1 * 149^1 * 571^1 * 2633^1 * 4483^1 (mod 10000000000000000051)
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)
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)
found factorization 47^956925442214697627 = -1^1 * 5^2 * 7^1 * 17^3 * 19^1 * 349^1 * 757^1 * 761^1 * 1307^1 (mod 10000000000000000051)
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)
found factorization 47^4861666169539904791 = 7^1 * 11^1 * 17^1 * 43^1 * 211^1 * 311^1 * 313^1 * 331^1 * 2351^1 (mod 10000000000000000051)
found factorization 47^3088522635126857467 = -1^1 * 2^1 * 3^2 * 7^2 * 37^1 * 163^1 * 2879^1 * 3581^1 * 3847^1 (mod 10000000000000000051)
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)
found factorization 47^2988839167316057473 = 2^4 * 3^5 * 5^1 * 7^2 * 19^1 * 257^1 * 883^1 * 1187^1 * 1511^1 (mod 10000000000000000051)
found factorization 47^4145331219989760478 = -1^1 * 2^1 * 11^1 * 157^1 * 457^1 * 571^1 * 1481^1 * 2063^1 * 2699^1 (mod 10000000000000000051)
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)
found factorization 47^8283999020028622386 = -1^1 * 2^1 * 5^7 * 7^3 * 11^1 * 83^1 * 233^1 * 439^1 * 547^1 (mod 10000000000000000051)
found factorization 47^6845850317115268142 = 11^1 * 29^1 * 61^1 * 71^1 * 131^2 * 239^1 * 821^1 * 1429^1 (mod 10000000000000000051)
found factorization 47^6599615100940580515 = 2^4 * 3^3 * 173^1 * 229^1 * 373^1 * 409^1 * 613^1 * 829^1 (mod 10000000000000000051)
found factorization 47^5486724233338059988 = -1^1 * 2^2 * 11^2 * 97^1 * 571^1 * 587^1 * 593^1 * 727^1 * 1427^1 (mod 10000000000000000051)
found factorization 47^1612039955949810650 = -1^1 * 2^2 * 11^1 * 13^3 * 83^1 * 193^1 * 743^1 * 1009^1 * 1949^1 (mod 10000000000000000051)
found factorization 47^614191692845647905 = 3^2 * 53^1 * 83^1 * 1811^1 * 2309^1 * 3593^1 * 4159^1 (mod 10000000000000000051)
found factorization 47^8390058901047062362 = 3^1 * 7^1 * 11^1 * 71^1 * 79^1 * 193^1 * 431^1 * 1459^1 * 4481^1 (mod 10000000000000000051)
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)
found factorization 47^5453447591934009593 = -1^1 * 2^2 * 179^1 * 613^1 * 1229^1 * 2053^1 * 2267^1 * 3119^1 (mod 10000000000000000051)
found factorization 47^2182914775768441306 = 2^7 * 19^2 * 1087^1 * 2633^1 * 3083^1 * 3643^1 (mod 10000000000000000051)
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)
found factorization 47^3949379364605463656 = 2^3 * 3^2 * 5^1 * 79^1 * 409^1 * 433^1 * 739^1 * 953^1 * 2381^1 (mod 10000000000000000051)
found factorization 47^3149029509900564330 = -1^1 * 2^1 * 5^1 * 71^1 * 1439^1 * 1481^1 * 4259^1 * 4909^1 (mod 10000000000000000051)
found factorization 47^1575266652864365178 = -1^1 * 461^1 * 659^1 * 1249^1 * 2213^1 * 2957^1 * 3907^1 (mod 10000000000000000051)
found factorization 47^7576947466248802589 = 2^1 * 3^1 * 11^1 * 89^1 * 113^1 * 307^1 * 1531^1 * 2437^1 * 4373^1 (mod 10000000000000000051)
found factorization 47^8267438627830703531 = 2^6 * 3^1 * 11^1 * 13^2 * 23^1 * 53^1 * 821^1 * 1021^1 * 2903^1 (mod 10000000000000000051)
found factorization 47^1150907916133544941 = 3^4 * 181^1 * 461^1 * 947^1 * 1153^1 * 1451^1 (mod 10000000000000000051)
found factorization 47^832683721404463213 = 5^1 * 7^2 * 19^1 * 43^1 * 1597^1 * 2063^1 * 2099^1 * 4993^1 (mod 10000000000000000051)
found factorization 47^7775544234288089361 = 11^1 * 13^1 * 37^1 * 149^1 * 461^1 * 1399^1 * 2383^1 * 2971^1 (mod 10000000000000000051)
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)
found factorization 47^4038186452332630561 = 2^8 * 3^1 * 11^1 * 19^2 * 47^2 * 311^1 * 773^1 * 2029^1 (mod 10000000000000000051)
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)
found factorization 47^3606765994715434133 = 7^1 * 17^1 * 37^1 * 193^1 * 977^1 * 1321^1 * 1873^1 * 2341^1 (mod 10000000000000000051)
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)
found factorization 47^465300836661267803 = -1^1 * 2^5 * 41^2 * 79^1 * 181^1 * 257^1 * 2591^1 * 4621^1 (mod 10000000000000000051)
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)
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)
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)
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)
found factorization 47^6465966842813896812 = 37^1 * 193^1 * 337^1 * 827^1 * 1229^1 * 1237^1 * 3049^1 (mod 10000000000000000051)
found factorization 47^1500123202847697173 = 2^1 * 7^1 * 13^1 * 17^1 * 23^1 * 1993^1 * 2137^1 * 2143^1 * 4111^1 (mod 10000000000000000051)
found factorization 47^2862574341882497157 = 2^1 * 5^1 * 79^1 * 587^1 * 677^1 * 2131^1 * 2803^1 * 4019^1 (mod 10000000000000000051)
found factorization 47^3565829746697688170 = -1^1 * 13^1 * 101^1 * 131^1 * 929^1 * 1279^1 * 1423^1 * 4993^1 (mod 10000000000000000051)
found factorization 47^2396968054994230789 = 2^6 * 3^1 * 7^2 * 19^1 * 73^1 * 173^2 * 593^1 * 1913^1 (mod 10000000000000000051)
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)
found factorization 47^1350155702805810727 = 2^1 * 3^2 * 23^1 * 31^1 * 43^1 * 331^1 * 593^1 * 643^1 * 757^1 (mod 10000000000000000051)

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<timed eval> in <module>

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py in logarithmTable(a, p, base, trace)
108                   ' * '.join("%d^%d" % (q, e) for q, e in zip(base, f) if e != 0), p))
109         MM = Matrix(list(M) + [f])
--> 110         if all(Matrix(F, MM).rank() > r for F in fields):
111             M = MM
112             r += 1

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py in <genexpr>(.0)
108                   ' * '.join("%d^%d" % (q, e) for q, e in zip(base, f) if e != 0), p))
109         MM = Matrix(list(M) + [f])
--> 110         if all(Matrix(F, MM).rank() > r for F in fields):
111             M = MM
112             r += 1

~/sage/local/lib/python3.8/site-packages/sage/matrix/constructor.pyx in sage.matrix.constructor.matrix (build/cythonized/sage/matrix/constructor.c:2529)()
633     """
634     immutable = kwds.pop('immutable', False)
--> 635     M = MatrixArgs(*args, **kwds).matrix()
636     if immutable:
637         M.set_immutable()

~/sage/local/lib/python3.8/site-packages/sage/matrix/args.pyx in sage.matrix.args.MatrixArgs.matrix (build/cythonized/sage/matrix/args.c:7953)()
662                     break
663         else:
--> 664             M = self.space(self, coerce=convert)
665
666         # Also store the matrix to support multiple calls of matrix()

~/sage/local/lib/python3.8/site-packages/sage/matrix/matrix_space.py in __call__(self, entries, coerce, copy)
849             [t]
850         """
--> 851         return self.element_class(self, entries, copy, coerce)
852
853     def change_ring(self, R):

~/sage/local/lib/python3.8/site-packages/sage/matrix/matrix_modn_dense_template.pxi in sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_template.__init__ (build/cythonized/sage/matrix/matrix_modn_dense_float.cpp:7223)()
530             v = self._matrix[i]
531             for j in range(ma.ncols):
--> 532                 x = next(it)
533                 if type(x) is int:
534                     tmp = (<long>x) % p

~/sage/local/lib/python3.8/site-packages/sage/matrix/args.pyx in iter (build/cythonized/sage/matrix/args.c:7374)()
559             for i in range(self.nrows):
560                 for j in range(self.ncols):
--> 561                     sig_check()
562                     x = m[i, j]
563                     if convert and self.need_to_convert(x):

KeyboardInterrupt: 
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<timed eval> in <module>

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py in indexCalculus(a, b, p, base, table, trace)
126             base, table = zip(*table.items())
127         else:
--> 128             table = logarithmTable(a, p, base, trace = descend(trace))
129     while True:
130         i = randint(1, p-1)

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/discreteLogarithm.py in logarithmTable(a, p, base, trace)
102         x = pow(a, i, p)
--> 103         f = factorizeByBase(int(x), base, p)
104         if not f:
105             continue

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/factorization.py in factorizeByBase(n, base, m)
138         if idx is None:
139             return False
--> 140         factors = factorizeByBase(-n % m, base)
141         if factors is False:
142             return False

~/fri/kirv/kriptografija-in-racunalniska-varnost/kirv/notebooks/algorithms/factorization.py in factorizeByBase(n, base, m)
131     factors = [0 for i in base]
132     x = n
--> 133     for i, p in enumerate(base):
134         while x % p == 0:
135             x //= p

src/cysignals/signals.pyx in cysignals.signals.python_check_interrupt()

KeyboardInterrupt: