Implementing index calculus for solving DLP

  discrete-mathematics, math, python, sage

So I need to implement index calculus algorithm for solving DLP. The main solveCalculus function should only take a,b and prime number p and return x so that a^x ≡ b mod p. Right now I only have this problems generator:

def gen_dlp_prime(nbits):
    p_0 = random_prime(pow(2, nbits), False, pow(2, nbits-1))
    a = 2
    p = a*p_0 + 1
    while p not in Primes():
        a += 1
        p = a * p_0 + 1
        return (p, p_0, a)
def rnd_dlp(nbits):
    p, p_0, a = gen_dlp_prime(nbits)
    g = 2
    while pow(g, p_0, p) != 1:
        g+=1
        x = randrange(2, p)
        return (p, g, x, pow(g, x, p))

def dlp_set_generator(beg, end, step=10):
    print("----- a = b^x (mod p) -----")
    for nbits in range(beg, end, step):
        p, g, x, a = rnd_dlp(nbits)
        print("Nbits = {}ntp = {}ntg = {}nta = {}ntx = {}".format(
            nbits, p,g,a,x))
        print(IndexCalculus(p,g,x,B))
dlp_set_generator(10, 160)

Where p is a prime number, g is generator of F_p*, x is a random number from 2 to p-1, so that a = g^x mod p. My question is how to implement this algorithm ? I searched some books about it online, but I’m more and more confused how it all works. Maybe someone has implementation in python or sage ? I would be really grateful.

Source: Python Questions

LEAVE A COMMENT