Simple Baby-Step-Giant-Step implementation in Python3 for finding discrete logs with a prime modulus

bsgs.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Towel 2017

from math import ceil, sqrt


def bsgs(g, h, p):
    '''
    Solve for x in h = g^x mod p given a prime p.
    If p is not prime, you shouldn't use BSGS anyway.
    '''
    N = ceil(sqrt(p - 1))  # phi(p) is p-1 if p is prime

    # Store hashmap of g^{1...m} (mod p). Baby step.
    tbl = {pow(g, i, p): i for i in range(N)}

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

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

    # Solution not found
    return None


print(bsgs(7894352216, 355407489, 604604729))

I'm a little lost on what you are computing for c.

Edit: nevermind. You're using Fermat's on the order of p. Ie inverse N.