嗨,我认为您的代码中有错字,也许您还没有尽可能地实现算法。
在下面的回答中,我将遵循此页面上的伪代码。
看起来像这样:
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))
哪个有诀窍。