확장 유클리드 알고리즘 솔루션

Question

숫자의 곱셈 역함수를 계산하는 알고리즘을 연구 중입니다. 나는 이것을하기 위해 기능을 만들어야 만했다. 그러나, 나는 최적화에 붙어있다.

내 알고리즘이 작동하지만 비교적 적은 수입니다.

숫자가 (a,b,n) 인 경우, a/b (mod n)을 반환해야합니다.

이 부분은 할 수 있습니다. n 정말 큰 경우 내가 이런 식으로 해결하고 있기 때문에, 내 코드는 엄청나게 느려지이와

for i in range(1,n): 
    if b*i%n == a%n: 
     return i 

내 문제가 다시 n의 크기입니다. 거대 해지면 코드가 실행되지 않습니다.

이제 내 번호가 3,2,7이라고 가정하고 모든 번호를 확인하지 않고 대답 5을 얻어야합니다. 그래서 확장 된 유클리드 알고리즘을 사용해 보았습니다.

3x + 7q = 1 

: 내 숫자로 요약하면

ax - qn = 1 

, 내가 끝낼 :

ax + by = 1 
ax = 1 (mod n) => ax - 1 = qn, where q is an integer 

내가 식으로 끝날 :

이

내가 무슨 짓을 이 문제를 어떻게 해결할 수 있습니까? 더 좋은 방법이 있습니까? 당신이 해결하려고하는 어떤

Answer 1

는 디오 판 투스 방정식 모든 숫자가 정수

ax+by=1 

입니다. 이와 같은 것을 해결하기 위해서는 표를 사용하여 가장 잘 설명 된 확장 된 유클리드 알고리즘이 필요합니다 (제목에서 알 수 있듯이). 새로운 A는 a-b*q와 q에 의해 계산된다

a b q 
3 7 0 
7 3 2 
3 1 3 
1 0 

이 a/b의 몫입니다 : 먼저 일반 유클리드 알고리즘을한다. 그런 다음 하단에서 시작하여 위쪽으로 이동하여 x=1 y=0으로 시작하여 x와 y를 계산합니다. 각 단계에서 새로운 x는 오래된 y이고 새로운 y는 x _old -q * y _old입니다. 이를 설명하기 위해 (불행하게도 내가 더 잘 포맷 할 수 있습니다) :

a b q x y 
3 7 0 
7 3 2 
3 1 3 
1 0 1 0 

a b q x y 
3 7 0 -2 0 // 1-0*(-2) 
7 3 2 1 -2 // 0-2*1 
3 1 3 0 1 // 1-3*0 
1 0 1 0 

3*(-2)+7*1=1 
3*(-2)=1 (mod 7) | +7 
-2=5 (mod 7) 

을가 이러한 경우에 음수가 될 수도 비록 당신이 X 필드에 답을 테이블 또는 자신 실현하는 것이을 채우기 위해 그렇게 할 때 N을 한 번 더해야합니다.