扩展欧几里德算法和乘法逆的概念

我有蟒蛇：扩展欧几里德算法和乘法逆的概念

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

扩展欧几里德算法和乘法逆的概念

回答

相关问题