擴展歐幾里德算法和乘法逆的概念

我有蟒蛇：擴展歐幾里德算法和乘法逆的概念

e*d == 1%etf

我們知道（e）和（ETF），並且必須發現使用擴展歐幾里德算法和概念（d）模運算的乘法逆。

d = (1/e)%etf 

d = (e**-1)%etf

產生一個全球性的錯誤的號碼，請使用上面的規則解釋幫我找到（d）。

該解決方案如下圖所示（Modular multiplicative inverse function in Python）給了我錯了計算結果

e*d == 1 (mod etf) 
d = (e**(etf-2)) % etf 
d = pow(e,etf-2,etf)

我是不是做一些錯誤的其他地方？這個計算好嗎？

來源

2012-09-20 iuri

我給擴展歐幾里德算法的實現在回答中到一個單獨的問題：http://stackoverflow.com/a/11703184 –

嗯@伍德沃爾看起來內向你的函數我只看到輸入參數1。爲了計算d，我認爲有必要知道變量etf和e，因爲問題是（d * e == 1％etf）。 – iuri

d = pow（e，etf-2，etf）僅在etf爲素數時才起作用。 – phkahler

與d = (e**(etf-2)) % etf一起列出的技巧只有在etf爲素數時纔有效。如果不是，則必須使用EEA本身來查找模乘法逆。

來源

2012-09-20 19:30:14 Harel

下面是擴展歐幾里得算法的實現。我從Java所採取的代碼this answer，推廣它，使之與模除2 工作，並把它轉換到Python：

def multiplicativeInverse(x, modulus): 
    if modulus <= 0: 
     raise ValueError("modulus must be positive") 

    a = abs(x) 
    b = modulus 
    sign = -1 if x < 0 else 1 

    c1 = 1 
    d1 = 0 
    c2 = 0 
    d2 = 1 

    # Loop invariants: 
    # c1 * abs(x) + d1 * modulus = a 
    # c2 * abs(x) + d2 * modulus = b 

    while b > 0: 
     q = a/b 
     r = a % b 
     # r = a - qb. 

     c3 = c1 - q*c2 
     d3 = d1 - q*d2 

     # Now c3 * abs(x) + d3 * modulus = r, with 0 <= r < b. 

     c1 = c2 
     d1 = d2 
     c2 = c3 
     d2 = d3 
     a = b 
     b = r 

    if a != 1: 
     raise ValueError("gcd of %d and %d is %d, so %d has no " 
         "multiplicative inverse modulo %d" 
         % (x, modulus, a, x, modulus)) 

    return c1 * sign;

來源

2012-09-21 22:02:37

擴展歐幾里德算法和乘法逆的概念

回答

相關問題