algorithm - 是否有计算 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]