확장 유클리드 알고리즘과 역수의 개념은

Question

나는 파이썬에 있습니다

우리가 알고

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) 

내가 다른 곳에서 몇 가지 실수를하고 있습니까 나에게 잘못 계산 결과를 제공? 이 계산은 괜찮습니까?

Answer 1

d = (e**(etf-2)) % etf으로 표시 한 속임수는 etf가 소수 인 경우에만 작동합니다. 그렇지 않은 경우 모듈 식 곱셈 역함수를 찾기 위해 EEA 자체를 사용해야합니다.

Answer 2

다음은 확장 유클리드 알고리즘을 구현 한 것입니다. 파이썬 자바에서 그것을, this answer의 코드를 가지고 그것을 일반화는 계수 다른 ⁶² 2 이상과 함께 작동하도록하고, 변환했습니다

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;