# Алгоритм Гельфонда-Шенкса дискретного логарифмирования (baby-step giant-step algoritm)

def order(a, p):
    """Возвращает порядок числа a по модулю числа p"""
    i, x = 1, 0
    while x != 1:
        x, i = pow(a, i, p), i + 1
    return i - 1

def gelfond(a, b, p, q=None):
    if q == None: q = order(a, p)
    s = (int)(q**.5) + 1
    d = pow(a, p - 1 - s, p)
    
    #print(f"q = {q}, s = {s}, d = {d}")

    base = []
    for i in range(0, s):
        base.append(b % p * pow(d, i , p) % p)
    
    #print(base)

    for i in range(0, s):
        try:
            x = s*base.index(pow(a, i, p))+i
            #print(f"x≡{x}mod({q})")
            return x
        except: 
            pass

if __name__ == "__main__":
    print(gelfond(2, 7123, 1123))