模块化逆算法 [英] algorithms for modular inverses
问题描述
我看了一下该扩展欧几里得算法和放大器部分;模块化逆，其中指出，它不仅计算 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.Subtract Q倍的矢量对应于从较小 对应于较大的载体 5.重复步骤2到4，直到结果为零 6.Publish的preceding结果为GCD（N，M）
所以我的问题要问这个问题，也是我怎么能实现在code此步骤？请帮帮我，我不知道如何开始，并从哪个角度可我开始解决这个问题，为澄清的结果，应该是这样的 这种算法的一个例子是在30以下计算^（ - 1）（模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）
。该部门被认为是与截断整数除法。标准EA为 GCD（A，B）与 A＆LT; = B 是这样的：
B = A * Q0 + R0
A = R0 * Q1 + R1
R0 = R1 * Q2 + R2
...
ř[N + 1] = 0
现在 RN 是所需的GCD。然后，你背的替代品：
研究[N-1] = R [N] * Q [N + 1]
ř[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）
ř[N-3] = R [N-2] * Q [N-1] + R [N-1]
= ...＆LT;替代＆GT; ...
直到你最后达到 RN = M * A + N * B 。您所描述的算法跟踪回溯数据向右走，所以它的效率更高一些。
如果 RN == GCD（A，B）== 1 ，那么你的确发现了乘法逆 A 模 B ，即 M ：（A * M）％B == 1 。
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).
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.
这篇关于模块化逆算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
