from math import ceil, sqrt

def bsgs(p, g, h):
    ##Berechne d in h = g^d mod p

    N = ceil(sqrt(p - 1))  # phi(p) is p-1 if p is prime

    # Baby step: compute a look-up table of g^i values for i = 0, 1, ..., N
    lookup_table = {pow(g, i, p): i for i in range(N)}

    # Precompute via Fermat's Little Theorem
    c = pow(g, N * (p - 2), p)

    # Giant step: Search for an equivalence in the lookup_table
    for j in range(N):
        y = (h * pow(c, j, p)) % p
        if y in lookup_table:
            return j * N + lookup_table[y]

    # Solution not found
    return None


def main():

    p = 27893
    g = 3729
    alpha = 11819
    beta = 1531

    # Find the discrete logarithm a such that g^a = alpha mod p
    a = bsgs(p, g, alpha)
    print(f"a = {a}")

    # Validate the result
    if a is None:
        print("No solution found for a")
    else:
        # Recompute the shared secret key: K = beta^a mod p
        K = pow(beta, a, p)
        print(f"Shared secret key K = {K}")

        # Find the discrete logarithm b such that g^b = beta mod p
        b = bsgs(p, g, beta)
        print(f"b = {b}")

        # Validate the result
        if b is None:
            print("No solution found for b")
        else:
            # Recompute the shared secret key: K = alpha^b mod p
            K2 = pow(alpha, b, p)
            if K2 == K:
                print("b is correct")
            else:
                print("b is not correct")


if __name__ == '__main__':
    main()