<jupyter_start><jupyter_text>Index calculus algorithmWe 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.<jupyter_code>from algorithms.euclidean import gcd
from algorithms.factorization import factorizeByBase

p = 9330887
a = 5
b1 = 4389733
b2 = 1234567<jupyter_output><empty_output><jupyter_text>We will use a base consisting of $-1$ and all primes less than $50$.<jupyter_code>base = [-1] + prime_range(50)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>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
    s.add(i)
    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)<jupyter_output>[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]<jupyter_text>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.<jupyter_code>t = M^-1 * Matrix(zip(v)) % (p-1)
t<jupyter_output><empty_output><jupyter_text>Let us verify that the table is correct.<jupyter_code>[pow(a, i, p) for i, in t]<jupyter_output><empty_output><jupyter_text>We can now find a power of $b_i$ that can be factorized with our base. We will use the following function.<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>Let us find such a power of $b_1$ and its factorization.<jupyter_code>i1, f1 = findPower(b1, p, base)
i1, f1<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>g1 = gcd(i1, p-1)
g1<jupyter_output><empty_output><jupyter_text>We can thus obtain a solution modulo $p-1$ divided by this GCD.<jupyter_code>m1 = ((p-1)/g1)
(x1,), = Matrix([f1])*t / i1 % m1
x1<jupyter_output><empty_output><jupyter_text>Let us now put this into a function which will also verify the potential solutions.<jupyter_code>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)<jupyter_output>5^5753305 mod 9330887 = 4389733<jupyter_text>We have thus computed $\log_a b_1$. Let us now compute $\log_a b_2$.<jupyter_code>i2, f2 = findPower(b2, p, base)
i2, f2
checkSolutions(a, b2, p, t, i2, f2)<jupyter_output>5^2608331 mod 9330887 = 8096320
5^7273774 mod 9330887 = 1234567<jupyter_text>Running time comparisonWe 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.<jupyter_code>from algorithms.discreteLogarithm import logarithmTable, indexCalculus

aa = 47
bb = 191
pp = 100000000003
table = %time logarithmTable(aa, pp, base, trace = True)
print(table)
%time indexCalculus(aa, bb, pp, base, table, trace = True)
pp = 10000000000000000051
base = [-1] + prime_range(5000)
table = %time logarithmTable(aa, pp, base, trace = True)
%time indexCalculus(aa, bb, pp, base, table, trace = True)<jupyter_output>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 *[...]
{'fraction_non_alphanumeric': 0.11824561403508772, 'fraction_numerical': 0.19263157894736843, 'mean_word_length': 3.627435064935065, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 46, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 9, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '375629', 'license': 'MIT', 'n_tokens_mistral': 3087, 'n_tokens_neox': 2268, 'n_words': 855, 'path': 'notebooks/IndexCalculus.ipynb', 'repo_name': 'tp4348/kirv', 'size': '5700'}