扩展欧几里得算法的不同实现会产生不同的结果？

Question

我正在尝试实现RSA算法。我一直在研究扩展欧几里得算法，并尝试在不同的网站上实现代码。但是，对于我的某些解密操作，它没有给我正确的结果，因此我一直在调试，并注意到算法的不同实现会产生不同的结果。第一个实现来自Brilliant.org，第二个实现来自https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code。

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
    gcd = b
    return gcd, x, y


def extended_euclid_gcd(a, b):
"""
Returns a list `result` of size 3 where:
Referring to the equation ax + by = gcd(a, b)
    result[0] is gcd(a, b)
    result[1] is x
    result[2] is y
"""
    s = 0; old_s = 1
    t = 1; old_t = 0
    r = b; old_r = a
    while r != 0:
        quotient = old_r/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
    return old_r, old_s, old_t

对于a = 3，b = 25456，（源自稍微不太简单的示例https://www.di-mgt.com.au/rsa_alg.html），我分别得到了这两种实现的结果：

gcd:  1 x:  -8485 y:  1
gcd:  25456 x:  0 y:  1

为什么它们不同？为什么第二个实现的gcd根本不是1？一个后续问题是，因为我试图按照链接中的示例进行操作，所以我的x值为负数。他们的答案是16971。我在这里阅读到https://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm，扩展欧几里得算法找到最接近原点的答案。有没有办法指定最接近原点且为正数的答案？

- Lo Ran

---

根据WolframAlpha的结果，{-8485, 1}表示3 * -8485 + 1 * 25456 = 1。 - kelalaka

第二个显然是错误的。它可能是为Python 2编写的，如果你将old_r/r中的“/”更改为“//”，它可能会起作用。 - President James K. Polk

@JamesKPolk 是的，可以了，谢谢！ - Lo Ran

@kelalaka 谢谢你们两个。我仍然不明白链接中的示例如何使用算法得到16971作为私钥，当所有这些都明显得到-8485。根据其他StackExchange链接，我认为扩展欧几里得算法并不是唯一的。 - Lo Ran

显然，我们更喜欢正幂而不是负幂。d的计算是通过模phi(n)来完成的。 - kelalaka

你能把与问题相关的评论转化为答案吗？我会点赞的。 - kelalaka

Answer 1

在此，博客作者链接到新手实验室。

詹姆斯·K·波尔克是正确的，代码确实是用Python 2编写的，不兼容Python 3。

我们必须将quotient = old_r/r更新为quotient = old_r//r，以使其与Python 3兼容。

我将更新原始帖子以反映这一发现。谢谢洛然。

- Ravi Ojha