扩展欧几里德算法的不同实现会产生不同的结果?
Different implementations for Extended Euclidean algorithm yield different results?
我正在尝试实现 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?一个后续问题是,因为我正在尝试按照 link 中的示例进行操作,所以我得到了 x 的负值。他们的答案是 16971。我在这里 https://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm 读到扩展欧几里得算法找到最接近原点的答案。有什么方法可以指定最接近原点,并且是正值吗?
post 的作者在此处链接到 Rookie's Lab。
James K Polk 是对的,代码确实是用 Python 2 编写的,与 Python 3 不兼容。
我们必须将 quotient = old_r/r
更新为 quotient = old_r//r
以使其与 Python 兼容 3.
我将更新原来的 post 以反映这一发现。谢谢罗运行.
我正在尝试实现 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?一个后续问题是,因为我正在尝试按照 link 中的示例进行操作,所以我得到了 x 的负值。他们的答案是 16971。我在这里 https://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm 读到扩展欧几里得算法找到最接近原点的答案。有什么方法可以指定最接近原点,并且是正值吗?
post 的作者在此处链接到 Rookie's Lab。
James K Polk 是对的,代码确实是用 Python 2 编写的,与 Python 3 不兼容。
我们必须将 quotient = old_r/r
更新为 quotient = old_r//r
以使其与 Python 兼容 3.
我将更新原来的 post 以反映这一发现。谢谢罗运行.