算法模塊化逆

我已讀到該擴展歐幾里得算法&模塊化逆，其中指出，它不僅計算部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

算法模塊化逆

回答

相關問題