# Arup Guha
# 10/17/2025
# Illustration of Discrete Log Divide and Conquer Algorithm

# Note: Changed function call to find private key for CIS 3362
#       Homework #6 Question #4 (Fall 25)

import math

# Returns the exponent x such that b to the x mod p is y
def disclogslow(b,y,p):

    ans = 1
    for i in range(p):
        if ans == y:
            return i
        ans = (ans*b)%p

    # Not found.
    return -1


# Runs Divide and Conquer Algorithm
def disclogfaster(b,y,p):

    # Get a number slightly bigger than the square root.
    n = math.sqrt(p)
    n = int(n + 2)

    # Dictionary for exponents.
    mypows = {}

    # This is my base I am building off of.
    product = pow(b,n,p)

    ans = 1
    for i in range(n):
        ans = (ans*product)%p
        mypows[ans] = (i+1)*n

    # Value I am looking for in table.
    lookfor = y
    for i in range(n):

        # This mod is in my table.
        if lookfor in mypows:
            return (mypows[lookfor] - i)%(p-1)

        lookfor = (lookfor*b)%p

    return -1

''' Put in information for CIS 3362 Homework 6 Question 4 '''
print(disclogfaster(726288716355, 268931642640, 1234567890133))