我需要计算乘法阶来解决离散对数问题。我尝试在下面使用此算法,但它不适用于大数字。
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
最佳答案
基于因式分解 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]
关于algorithm - 是否有计算 x 模 y 的乘法阶数的算法(对于 y > 1000 execpt mod(x,y).multipliative_order())?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55112573/