模逆算法

发布于 2024-12-07 04:40:22 字数 1073 浏览 0 评论 0原文

我已阅读有关扩展欧几里得算法和扩展欧几里得算法的部分模逆，它指出它不仅计算 GCD(n,m) 还计算 a 和 b，使得 a*n+b*b=1; 算法是这样描述的：

写下 n、m 以及两个向量 (1,0) 和 (0,1)
将两个数字中较大的数字除以较小的数字 - 将此称为商q
用较大的值减去较小的 q 倍（即减少较大的值）对较小的取模）

（我在这里有疑问，如果我们用 qn/m 表示，那么 nq*m 不等于 0？因为 q=n/m；（假设 n>m），所以为什么需要这样的操作呢？然后4步

4.减去q乘以较小者对应的向量对应较大的向量 5.重复步骤2到4，直到结果为零 6.将上述结果发布为gcd(n,m)

所以我对这个问题的问题也是我如何在代码中实现这些步骤？请帮助我，我不知道如何开始以及从哪一点开始解决这个问题，为了澄清结果，它应该看起来像这样此算法的一个示例是以下 30^(-1)(mod 53) 的计算；

53           30           (1,0)                        (0,1)
53-1*30=23   30           (1,0)-1*(0,1)=(1,-1)         (0,1)
23           30-1*23=7    (1,-1)                       (0,1)-1*(1,-1)=(-1,2)
23-3*7=2      7           (1,-1)-3*(-1,2)=(4,-7)       (-1,2)
2             7-3*2=1     (4,-7)                      (-1,2)-3*(4,7)=(-13,23)
2-2*1=0       1           (4,-7)-2*(-13,23)=(30,-53)   (-13,23)

由此我们看到 gcd(30,53)=1，重新排列项，我们看到 1=-13*53+23*30，所以我们得出结论 30^(-1)=23(mod 53)。

原文

i have read section about The Extended Euclidean Algorithm & Modular Inverses,which states that it not only computes GCD(n,m) but also a and b such that a*n+b*b=1;
algorithm is described by by this way:

Write down n, m, and the two-vectors (1,0) and (0,1)
Divide the larger of the two numbers by the smaller - call this
quotient q
Subtract q times the smaller from the larger (ie reduce the larger
modulo the smaller)

(i have question here if we denote by q n/m,then n-q*m is not equal to 0?because q=n/m;(assume that n>m),so why it is necessary such kind of operation?
then 4 step

4.Subtract q times the vector corresponding to the smaller from the
vector corresponding to the larger
5.Repeat steps 2 through 4 until the result is zero
6.Publish the preceding result as gcd(n,m)

so my question for this problem also is how can i implement this steps in code?please help me,i dont know how start and from which point could i start to solve such problem,for clarify result ,it should look like this
An example of this algorithm is the following computation of 30^(-1)(mod 53);

53           30           (1,0)                        (0,1)
53-1*30=23   30           (1,0)-1*(0,1)=(1,-1)         (0,1)
23           30-1*23=7    (1,-1)                       (0,1)-1*(1,-1)=(-1,2)
23-3*7=2      7           (1,-1)-3*(-1,2)=(4,-7)       (-1,2)
2             7-3*2=1     (4,-7)                      (-1,2)-3*(4,7)=(-13,23)
2-2*1=0       1           (4,-7)-2*(-13,23)=(30,-53)   (-13,23)

From this we see that gcd(30,53)=1 and, rearranging terms, we see that 1=-13*53+23*30,
so we conclude that 30^(-1)=23(mod 53).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

白云不回头 2024-12-14 04:40:22

除法应该是带有截断的整数除法。具有 a <= b 的 gcd(a, b) 的标准 EA 如下所示：

 b =  a * q0 + r0
 a = r0 * q1 + r1
r0 = r1 * q2 + r2
  ...
r[N+1] = 0

现在 rN 是所需的 GCD。然后你回代：

r[N-1] = r[N] * q[N+1]

r[N-2] = r[N-1] * q[N] + r[N]
       = (r[N] * q[N+1]) * q[N] + r[N]
       = r[N] * (q[N+1] * q[N] + 1)

r[N-3] = r[N-2] * q[N-1] + r[N-1]
       = ... <substitute> ...

直到你最终达到rN = m * a + n * b。您描述的算法会立即跟踪回溯数据，因此效率更高一些。

如果rN == gcd(a, b) == 1，那么你确实找到了a模b的乘法逆元，即<代码>m：<代码>(a * m) % b == 1。

The division is supposed to be integer division with truncation. The standard EA for gcd(a, b) with a <= b goes like this:

 b =  a * q0 + r0
 a = r0 * q1 + r1
r0 = r1 * q2 + r2
  ...
r[N+1] = 0

Now rN is the desired GCD. Then you back-substitute:

r[N-1] = r[N] * q[N+1]

r[N-2] = r[N-1] * q[N] + r[N]
       = (r[N] * q[N+1]) * q[N] + r[N]
       = r[N] * (q[N+1] * q[N] + 1)

r[N-3] = r[N-2] * q[N-1] + r[N-1]
       = ... <substitute> ...

Until you finally reach rN = m * a + n * b. The algorithm you describe keeps track of the backtracking data right away, so it's a bit more efficient.

If rN == gcd(a, b) == 1, then you have indeed found the multiplicative inverse of a modulo b, namely m: (a * m) % b == 1.

回复收藏 0 原文

~没有更多了~