模块化逆计算卡住了

Question

到目前为止,这是我的代码:

def mod_div(a, b, n): 

if gcd(b,n) != 1:
    return 'Undefined'    

for x in range(1, n):
        if b*x%n == a%n:      
            return x   

这段代码接受我制作的函数gcd()并返回gcd,然后我用它来计算逆.我搜索了这些问题,但似乎没有人给我正确答案.

我的问题是:当我执行div_mod(3,2,7)时,代码返回5,就像它应该的那样.但是,当我为大数字(例如n> 10000)执行此操作时,解决方案计算需要很长时间,因为通过n的迭代来找到正确的数字.

我试着查看其他问题,在他们的答案中,他们都有类似的东西,但是如果gcd!= 1,他们都会返回x%n,而不是在n中使用i,这对我没有帮助没有给出正确的答案.

例如.如果我使用a = 12,b = 3和n = 11它应该返回4,但我发现除了我的所有函数都返回1.

我想知道是否有一种更有效的方法来使用eulids扩展定理而不是测试每个n,并希望一个有效.

Answer 1

你是对的,扩展欧几里德算法解决了这个任务.但是你不需要打电话n- 你只需要一次.查看http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

以下是来自http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm的命令式python算法

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

O(1)空间和最坏情况下的O(log n)时间.

现在,为了除以模数n,我们有了定义

def moddiv(a, b, n):
    binv = modinv(b, n)
    if not binv:
        return None
    return a * binv % n