逆计算器模Python

Question

在mod 543中154的inverse是67，我的代码告诉我它是58。这是我的Python代码：

def inverse(modulo, number):
    ri1 = number
    ri2 = modulo
    ti1 = 1
    ti2 = 0
    qi = 0
    ti = 0
    qi = 0
    ri = 0
    while ri1 != 0:
        ri = ri2 % ri1
        qi = (ri2 - ri) / ri1
        ti = ti2 - (qi * ti-1)
        ri2 = ri1
        ri1 = ri
        ti2 = ti1
        ti1 = ti
    return ti1
print(inverse(543, 154))

Answer 1

嗨，我想你的代码中有一个拼写错误，也许你没有尽可能好地实现算法。

在我下面的回答中，我将遵循this page上的伪代码。

它看起来像这样：

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

我已经更新了下面的代码，但你方法中的关键“缺陷”是你返回的是t而不是s。

def inverse(modulo, number):
    ri1 = number # a
    ri2 = modulo # b
    ti1 = 0 # old_t
    ti2 = 1 # t
    ti = 0
    
    si1 = 1 # old_s
    si2 = 0 # s
    ti = 0
    
    ri = 0 
    while ri1 != 0:
        ri = ri2 % ri1
        qi = (ri2 - ri) / ri1
        ti = ti2 - (qi * ti1)
        si = si2 - (qi * si1)
        ri2 = ri1
        ri1 = ri
        ti2 = ti1
        ti1 = ti
        si2 = si1
        si1 = si
            
    print(f"Bézout coefficients: ({si1}, {ti1})")
    print(f"greatest common divisor: {ri2}")
    print(f"quotients by the gcd: ({ti2}, {si2})")
    print(f"modulo inverse {si2}")
print(inverse(543, 154))

我们可以简化这段代码，只获得值si2，如下所示：

def inverse(modulo, number):
    ri1 = number # a
    ri2 = modulo # b
    ri = 0 
    
    
    si1 = 1 # old_s
    si2 = 0 # s
    
    while ri1 != 0:
        ri = ri2 % ri1
        qi = (ri2 - ri) / ri1
        si1, si2 = si2 - (qi * si1), si1
        ri2 = ri1
        ri1 = ri
            
    return si2
print(inverse(543, 154))

这就起作用了。

Answer 2

下面的代码可以工作：

def inverse(modulo, number):
    ri1 = number
    ri2 = modulo
    ti1 = 1
    ti2 = 0
    qi = 0
    ti = 0
    ri = 0
    while ri2 != 0:
        qi = ri1 // ri2
        ti = ri2
        ri2 = ri1 % ri2
        
        ri1 = ti
        ti = ti2
        ti2 = ti1-qi*ti2
        ti1 = ti
    
    if (ti1 < 0):
        ti1 = ti1 + modulo

    return ti1
print(inverse(543, 154))