有没有一个算法来计算x模y的乘法顺序（对于y> 1000 execpt mod（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]