扩展欧几里德算法解决方案

-1

我正在研究计算数字的乘法逆的算法。我不得不做一个功能来做到这一点。但是，我坚持优化。扩展欧几里德算法解决方案

我的算法可行，但只适用于相对较小的数字。

鉴于3个号码(a,b,n)，我需要返回a/b (mod n)。

这部分我可以做。然而，当n实在是大，因为我是这样解决它在我的代码变得不可能慢：

for i in range(1,n): 
    if b*i%n == a%n: 
     return i

我对这个问题又是n大小。如果它变大，代码不会运行。

现在，假设我的号码是3,2,7，我需要获得答案5而不检查所有数字。所以我尝试使用扩展的欧几里德算法。

这是我做过什么：

ax + by = 1 
ax = 1 (mod n) => ax - 1 = qn, where q is an integer

我最终的公式：

ax - qn = 1

如果我在我的数字综上所述，我结束了：

3x + 7q = 1

我该如何解决这个问题？有没有更好的办法？

来源

2014-01-16 Lord Raikan

您正在使用的'n'（以及'a'和'b'）的近似值是什么导致原始方法失败？ – senshin

昨天当你问这个问题时，我告诉你查找扩展的欧几里得算法。你显然没有这么做。在页面顶部的搜索框中，输入短语“扩展欧几里德算法”。你会发现几个相关的答案。包括我的。也许你应该把所有这些页面上的每个解决方案都付诸实践，作为感谢他们工作的一种方式。我正在投票结束这个问题。如果您在实施您找到的解决方案时遇到困难，请回过头来问一个具体问题。 – user448810

@ user448810我的确在查找euclidian算法，这促使我问这个问题。我对这个网站很陌生，所以我没有想到在这里搜索它，而是使用了外部资源。 –

你正在试图解决的是个不定方程

ax+by=1

，所有的数字都是整数。为了解决这样的问题，你需要（如你的标题所示）扩展的欧几里德算法，这是使用表格最好地解释的。首先，你做正常的欧几里德算法：

凡新一由a-b*q和q计算为a/b商。然后，您从底部开始并向上计算x和y，从x=1 y=0开始。在每一步中，新的x是旧的y，新的y是x _旧的 -q * y _旧的。为了证明这一点（可惜我不能更好地格式化）：

a b q x y 
3 7 0 
7 3 2 
3 1 3 
1 0 1 0 

a b q x y 
3 7 0 -2 0 // 1-0*(-2) 
7 3 2 1 -2 // 0-2*1 
3 1 3 0 1 // 1-3*0 
1 0 1 0 

3*(-2)+7*1=1 
3*(-2)=1 (mod 7) | +7 
-2=5 (mod 7)

所以，当你填写你在x域的答案表或自己的FPGA实现，即使它可能是在这种情况下，负你必须添加N次。

来源

2014-01-17 00:52:54 henje

扩展欧几里德算法解决方案

回答

相关问题