模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))