Существует ли алгоритм для вычисления мультипликативного порядка x по модулю y (для y> 1000, кроме ex modpt (x, y) .multipliative_order ())?

Question

Мне нужно вычислить мультипликативный порядок для решения задачи дискретного логарифма. Я попытался использовать этот алгоритм ниже, но он не работает с большими числами.

def multiplicativeOrder(A, N) : 
    if (GCD(A, N ) != 1) : 
        return -1

    result = 1

    K = 1
    while (K < N) : 

        result = (result * A) % N  

        if (result == 1) : 
            return K 

        K = K + 1

    return -1

Answer 1

Существуют более быстрые способы сделать это, основанные на факторизации n и применении большого количества математики.Тем не менее, в качестве базового улучшения, которое идет от O(n) до O(sqrt(n)) с использованием идеи гигантского шага "маленький шаг".Это также довольно просто по сравнению с альтернативой.

def multiplicative_order2(a, n):
    if gcd(a, n) != 1:
        return -1

    visited = {}
    count = 0

    count = slow = fast = 1
    while fast not in visited:
        visited[slow] = count
        count += 1
        slow = (slow * a) % n
        fast = (fast * slow) % n

    return count * (count + 1) // 2 - visited[fast]