확장 유클리드 알고리즘 & 동 여 방정식 & 모 m 곱셈 역 원 상세 해석

복습: 최대 공약수 알고리즘 구하 기

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

먼저 유클리드 확장 정 리 를 소개 합 니 다.
0 이 아 닌 두 개의 정수 a, b 에 대해 서 는 x, y 를 풀 어 x + by = gcd (a, b) 가 존재 해 야 합 니 다.
다시 말 하면 x + by 와 같은 최소 정 수 는 gcd (a, b) 와 같다.
구현 코드 는 다음 과 같 습 니 다. (일반 문 제 는 64 비트 를 사용 해 야 합 니 다)
(복잡 도: O (log max (a, b)))

typedef long long LL;

///   x y，  ax+by=gcd(a,b)， |x|+|y|  (|x|<=b,|y|<=a)
///  ：  a,b int   ，          int  

void exgcd(LL a, LL b, LL& d, LL& x, LL& y)
{
	if (!b) d = a, x = 1, y = 0;///  ax+by=ax,gcd(a,b)=gcd(a,0)=a, ax=a,  x=1,y       ,        y=0,     y=1,            ！
	else exgcd(b, a % b, d, y, x), y -= x * (a / b);///                    x y     
	
	/*
	         :
	 x,y          ,x',y'          
	  
	        gcd(a,b)=gcd(b,a%b)
	  
	        ax+by=gcd(a,b)   bx'+(a%b)y'=gcd(b,a%b)=gcd(a,b)
	 
	        bx'+(a-(a/b)*b)y'=gcd(a,b)
	     
	        ay'+b*(x'-(a/b)*y')=gcd(a,b)
	  
	        x=y',y=x'-(a/b)*y'
	*/
}

일반적인 상황: x + by = c, gcd (a, b) | c 의 해 는 P24 - 25 를 참고 하 십시오.
여기 서 왜 통 해 는 x = x0 + kb, y = y0 - ka (물론 너 도 x = x0 - kb, y = y0 + ka 로 쓸 수 있다):
먼저 a 를 a / gcd (a, b), b 를 b / gcd (a, b) 로 바 꿉 니 다. 이렇게 x + by = 1, gcd (a, b) = 1 (여기 a, b 는 실제 적 으로 a '와 b' 를 쓰 고 간단 한 견 해 를 위해 삐 침 표를 줄 입 니 다)
... 때문에
ax+by = ax0+by0
그래서.
a(x-x0) = -b(y-y0) = P
그래서.
a|P，b|P
a, b 호상 소 때문에
ab|P
즉시
P=kab
그래서.
x-x0=kb，y-y0=-ka
정리 할 수 있다
x=x0+kb，y=y0-ka
변형 1: 동 여 방정식
유클리드 확장 알고리즘 은 선형 부정 방정식 x + by = c 를 해결 하 는 것 을 제외 하고
동 여 방정식 a. 1. 1. 1. c (mod m), b. 1. 1. c (mod n) 도 풀 수 있다.
a = c + mx, b = c + ny 로 바 꾸 기
mx - ny = a - b, 선형 부정 방정식 으로 해결
변형 2: 모 m 곱셈 역 원
정의: 정수 a, m 에 대해 정수 b 가 존재 하면 ab 를 만족 시 킵 니 다. ≡ 1 (mod m) 은 b 는 a 의 모 m 곱셈 역 원 이 라 고 한다.
정리: a 에 존재 하 는 모 m 의 곱셈 역 원 의 충전 조건 은 gcd (a, m) = 1 이다.
충분 성: 왜냐하면
gcd(a,m) = 1
오로라 의 정리 에 따 르 면
a^φ(m) ≡ 1(mod m)
그러므로
a * a^(φ(m)-1) mod m = 1
그래서 a 의 모 m 곱셈 역 원, 즉 a ^ (φ(m) - 1) 필요 성: a 모델 m 의 곱셈 역 원 이 b 라 고 가정 하면
ab ≡ 1 (mod m)
그래서.
ab = km +1
그래서.
1 = ab - km
유클리드
gcd(a,m) = 1
정리 에서 알다.
x + by = 1 에 대해 x 는 a 모 b 의 곱셈 역 원 이 고 y 는 b 모 a 의 곱셈 역 원 임 을 알 수 있다.
반대로 a 모드 b 의 곱셈 역 원 을 계산 하려 면 x + by = 1 의 x 의 최소 정수 해 를 구하 여 선형 부정 방정식 으로 해결 하 는 것 과 같다.
(물론, 너 도 a ^ (φ(b) - 1) mod b, 하지만 우리 가 써 도φ함수 공식 과 순차 제곱 법 (복잡 도 역시 O (log b) 이다. 모델 링 의 횟수 가 유클리드 알고리즘 과 코드 를 확장 하 는 것 보다 훨씬 많 기 때문에 이 방법 은 실 용적 이지 않다)
* * * 전재 출처 를 밝 혀 주세요.http://blog.csdn.net/synapse7/article/details/9901195****