def BSGB(g,b,p):
    N=p-1
    m=floor(sqrt(N))+1
    B=[]
    G=[]
    B.append(1)

    for j in range(1,m):
        B.append(power_mod(g,j,p))

    p2 = power_mod(g,m,p)
    for j in range(0,m-1):
        tempVal = b* power_mod(p2,-j,p) % p
        for i in range(len(B)):
            if(tempVal == B[i]):
                return (i+(m*j)) % (p-1)

    print("ERROR: didn't find private key")
    return -1

k=next_prime(738428)
l=BSGB(23,293,k)
l

b=power_mod(23,l,k)
b

p = next_prime(5623567)
g = 2
x = 1234
b = power_mod(g,x,p)
p
g
x
b
BSGB(g,b,p)

p = next_prime(8989898989)
g = 17
x = 77777777
b = power_mod(g,x,p)
p
g
x
b
BSGB(g,b,p)