算法模块化逆

我已读到该扩展欧几里得算法&模块化逆，其中指出，它不仅计算部GCD(n,m)而且a和b，使得a*n+b*b=1; 算法是通过这种方式描述：算法模块化逆

写下N，M，和两个矢量（1,0）和（0,1）

除以两个数的由较大较小 - 调用此商q

Subtrac TQ倍从较大的情况下（即，减小较大模越小）

（我这里有问题，如果我们用QN/m，则n-q*m is不等于0？因为Q = N/m;（假设n> m），那么为什么需要这种操作呢？然后4步骤

4.Subtract Q倍对应于从矢量越小对应于较大 5.重复向量步骤2到4，直到结果为零 6.Publish前述结果作为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）。

来源

2011-09-30 dato datuashvili

什么？我很困惑 – Grammin

欲了解更多信息，请参阅本网站http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html，并参见本节扩展欧几里德算法与模块逆向 –

告诉我们你的代码迄今为止。关于步骤3：q是n/m的整数部分，所以余数n-q * m可以是非零的。 –

该部门应该是截断的整数除法。为gcd(a, b)与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。

来源

2011-09-30 17:45:37

算法模块化逆

回答

相关问题