-
백준 6064 카잉 달력을 풀다가 정수론 공부함
이하 출처 : https://dimenchoi.tistory.com/46
정수론
정수론
: 정수의 특징(약수와 배수, 몫과 나머지)에 대해 탐구
왜 필요?
1) 현대 암호의 원리: 두 개의 큰 소수를 곱하는 건 쉽지만, 이 결과를 다시 소인수분해하는 것은 어렵다
2) 컴퓨터를 이용한 계산, 메모리 설계 등에서 다양하게 쓰이고 있다.
최대공약수 GCD, Greatest Common Division
최소공배수 LCM, Least Common Multiple
A, B를 소인수분해 해서 공통된 소인수를 모두 곱하면 GCD, 두 수의 모든 소인수를 곱하면 LCM
출처: https://dimenchoi.tistory.com/46 벤다이어그램으로 표현하면 여러가지 정리를 유도하는 데 도움이 된다
예를 들면, AB = LG
정수론에서 GCD와 LCM는 각각 gcd(a,b), lcm(a,b)으로 표기
유클리드 호제법
최대공약수를 찾기 위한 알고리즘
유클리드 호제법은 다음 정리로부터 기인한다.
" A를 B로 나눈 몫을 Q라 하고, 나머지를 R이라 하자.
이 때, gcd(A,B) = gcd(B,R)이다. "
이 정리를 이용한 유클리드 호제법 : A를 B로 나눈 나머지 R1 ... Rn을 구한다. Rn-1이 최대공약수
유클리드 호제법의 증명
귀류법으로 증명. gcd(A,B)≠gcd(B,R)를 가정하고 모순을 이끌ㅇㅓ냄.
유클리드 호제법의 쓰임
컴퓨터로 계산하면 짱 빠르다~
정수론의 여러 정리를 증면하는데도 도움이 된다
베주 항등식
별그리기
a칸씩 건너 뛰었을 때 나오는 도형
a칸 건너뛰었을 때 도달하는 점의 위치 1, 5, 7, 11 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 2, 10 0, 2, 4, 6, 8, 10 3, 9 0, 3, 6, 9 4, 8 0, 4, 8 6 0, 6 a칸씩 건너뛰는 것으로 도달하는 점들은 gcd(a,12)의 배수
수직선 건너뛰기
만약 앞뒤로 6, 15씩만 움직일 수 있다면 어떤 점에 도달할 수 있을까?
먼저 15칸을 간 뒤 6칸을 뒤로 가면, 15−6=9칸을 갈 수 있다.
즉, 앞뒤로 6, 9칸 움직이면 도달하는 지점과 같은 문제
똑같이, 반대 방향으로9칸, 6칸 움직이면 9-6 = 3칸 갈 수 있음.
앞뒤로 3칸, 6칸을 움직일 수 있을 때 어떤 점에 도달할 수 있는가와 동일한 문제
6칸을 간 뒤 3칸을 뒤로 가면, 6−3= 3칸을 갈 수 있는데
이미 3칸을 갈 수 있는 상태였다. 즉, 3칸보다 더 조금 이동할 수는 없다는 결론.
결국 도달할 수 있는 점들은 3의 배수인 점.
=> 유클리드 호제법 gcd(a,b)=gcd(a,b−a)
앞뒤로 칸씩 움직일 수 있다면,
gcd(a,b)의 배수인 점들에만 도달할 수 있으며,
gcd(a,b)의 배수인 점들은 모두 도달할 수 있다.
수직선 건너뛰기 문제와 별 그리기 문제는 동일한 문제
베주 항등식(Bezout's Identity)
수직선 건너뛰기 문제의 결론을 수식으로 쓰면 아래와 같다.
" N, M이 정수일 때 aN + bM의 가능한 값은 gcd(a,b)의 배수이며, 오직 이 값만 가능하다. "
별 그리기 문제와 수직선 건너뛰기 문제의 연관성을 통해 위 정리는 아래 정리와 동치임을 알 수 있다.
" N이 정수일 때, aN을 b로 나눴을 때의 나머지는 gcd(a,b)의 배수이며, 오직 이 값들만이 가능하다. "
합동식
기하학에서의 합동
: 두 도형의 모양과 크기가 같음을 나타내는 관계
흔히 두 도형이 완전히 같다고 생각하지만, 도형의 위치와 회전이 다른 것은 큰 차이이다.
좌표평면에서 위치가 다른 두 점은 아예 다른 두 점이기 때문이다.
그런 차이에도 불구하고 두 도형의 크기와 모양이 같다는 점을 바탕으로 두 도형을 대략적으로 동일시 한다.
즉, 합동은
두 개의 다른 대상을 공통점을 바탕으로 대략적으로 동일시하는 것
이다.
정수론에서의 합동
정수 a, b를 정수 m으로 나눈 나머지가 같을 때, a와 b는 법 m에 대해 합동이라고 하고, 다음과 같이 표기한다.
a ≡ b mod m
예를 들어 13시와 1시가 같은 것은 다음과 같이 쓸 수 있다.
13 ≡ 1 mod 12
주의, 합동식에서는 정수만 다룬다. 예컨대 0.3을 12로 나눈 나머지는 생각하지 않는다.
합동식의 성질
합동식도 등식처럼 양변에 수를 더하고 뺄 수 있다.
a ≡ b mod m이고 c가 정수일 때,
a ± c ≡ b ± c mod m
ac ≡ bc mod m
그런데 합동식은 양변을 나누는 것은 안 될 수도 있다.
언제 나누기가 가능할까?
항등원과 역원
임의의 원소 a와 연산 *에 대해서
항등원 : a*e = e*a = a를 만족하는 원소 e
ex) 연산 +에 대해 항등원은 0, 연산 x에 대해 항등원은 1
역원 : a∗a⁻¹=a⁻¹∗a=e 를 만족하는
ex) 4의 +에 대한 역원은 -4, x에 대한 역원은 1/4
즉, '어떤 수를 a로 나눈다' = '어떤 수를 a의 곱셉에 대한 역원과 곱한다'
만약 a의 곱셈에 대한 역원이 존재하지 않는다면? 나눗셈은 정의할 수 없게 된다.
예를 들어 a=0일 때 a의 곱셈에 대한 역원이 존재하지 않으며,
때문에 0으로 나누기를 정의하지 않는다.
합동식에서는 훨씬 자주 발생하는 상황.
합동식에서 곱셈의 역원
법 9에 대해서, 5의 역원?
합동식에서도 곱셈에 대한 항등원은 1이다.
즉, 5의 곱셈에 대한 역원 x는 다음을 만족시켜야 한다.
5 x x ≡ 1 mod 9
역원은 일일이 대입해보면 찾을 수 있다...
법 9에서 9 이상의 수는 0~8의 수 중 하나와 합동이므로 그 안에서만 찾으면 된다.
역원의 유일성은 항상 보장되어 있으므로 x=2 이후로는 확인할 필요 없음.
위와 같이 5의 역원은 2이지만, 6의 역원은 존재하지 않는다.
양 변을 5로는 나눌 수 있지만 6으로는 나눌 수 없다.
30 ≡ 120 mod 9
6 ≡ 24 mod 9 (O)
5 ≡ 20 mod 9 (X)
합동식에서 곱셈의 역원이 존재할 조건
어느 경우에 역원이 존재할까?
법 m에 대하여 정수 a의 역원이 존재한다는 것은,
다음 식을 만족시키는 a⁻¹이 있다는 것이다
a x a⁻¹ ≡ 1 mod m
(정수 a x a⁻¹와 1을 m으로 나눈 나머지가 같다)
위 수식은 별 그리기 문제와 동일하다.
원 위에 m개의 점이 찍혀 있을 때, a칸씩 건너 뛰며 별을 그릴 경우
도달할 수 있는 최소 위치는 gcd(a,m)이었다
즉, 다음 식이 성립한다.
(합동식에서 부등식의 사용은 권장하지 않습니다만 이해의 편의를 위해 이렇게 쓰겠습니다)
a x b ≥ gcd(a,m) mod m
그렇다면 a가 역원을 가지기 위해서는 gcd(a,m) = 1이어야 한다.
즉, 'a와 m이 서로소'는 a의 mod m에 대한 역원이 존재할 필요충분조건이다.
???
✅ 합동식에서 나눗셈이란?
예를 들어 이런 식이 있다고 해 봅시다:
a × x ≡ b (mod m)
이 식에서 x를 구하고 싶은데,
양변을 a로 나누고 싶어요.
일반적인 수학에서는 x = b / a처럼 나눌 수 있지만,
mod 연산에서는 직접 나눌 수 없습니다!대신 우리는 다음과 같이 생각합니다:
x ≡ b × a⁻¹ mod m
즉, a의 역원이 있을 때만
x를 계산할 수 있어요!✅ 나눗셈이 가능한 조건은?
a의 역원 a⁻¹이 존재하려면
gcd(a, m) = 1, 즉 a와 m이 서로소여야 합니다.그래야:
- a × a⁻¹ ≡ 1 (mod m)인 a⁻¹이 존재하고
- 나눗셈: x ≡ b × a⁻¹ mod m이 가능해져요
✅ “합동식에서 나눗셈이 가능하려면 gcd(a, m) = 1이어야 한다.”
즉,
a × x ≡ b mod m 이라는 합동식에서 x를 구하려면,
a가 mod m에서 나눠져야 하는데
이를 위해서는 반드시 a와 m이 **서로소(공약수가 1)**여야 한다는 말입니다.a⁻¹이 존재하려면? → gcd(a, m) = 1
a⁻¹이 존재한다는 말은, 어떤 정수 a⁻¹이 있어서
a × a⁻¹ ≡ 1 mod m
↔ a × a⁻¹ + m × k = 1 (어떤 정수 k에 대해)이 식이 정수해를 가지는 경우를 말하는데,
이건 바로 **Bézout's identity (베주 항등식)**의 조건이에요:a × x + m × y = 1이 정수해를 가지려면,
반드시 gcd(a, m) = 1이어야 한다.즉, 1을 만들 수 있어야 a의 역원이 존재하고,
그래야 나눗셈이 가능하다는 것!베주 항등식 : " N이 정수일 때, aN을 b로 나눴을 때의 나머지는 gcd(a,b)의 배수이며, 오직 이 값들만이 가능하다. "
a x a⁻¹ ≡ 1 mod m를 만족하는 a⁻¹가 존재하기 위해서는 gcd(a,m) = 1이어야 한다.
a × a⁻¹ ≡ 1 (mod m) 가 성립한다면,
어떤 정수 k에 대해 a × a⁻¹ + m × k = 1 이 되는 식도 성립한다.왜?
x ≡ y (mod m)
→ x와 y는 m으로 나눈 나머지가 같다는 뜻
→ 즉, x - y는 m의 배수라는 뜻이에요.수식으로 쓰면:
x ≡ y (mod m) ↔ x - y = m × k
a × a⁻¹ ≡ 1 (mod m) 이 수식을 합동식 정의로 바꾸면
a × a⁻¹ - 1 = m x k
a × a⁻¹ = 1 + m x k
a × a⁻¹ - m x k = 1
그런데 여기서 k는 임의의 정수이므로 +이든 -이든 상관 없나봐
고로 a × a⁻¹ + m x k = 1
Bezout's Identity에서 ax + by = 1이 성립하기 위해서는 gcd(x,y)=1이어야 하니까 a × a⁻¹ ≡ 1 (mod m)가 되려면 gcd(a,m)
(수학적으로 이 방식이 증명일 순 없지만 아무튼 이해에 도움이 됨...)
가 역원을 가지기 위해서는, 이어야 한다
와 이 서로소 는 의 법 에 대한 역원이 존재할 필요충분조건
와 이 서로소인 경우, 법 에 대해 의 역원이 존재한다.
와 이 서로소인 경우, 법 의 합동식에서 양변을 로 나눌 수 있다.
가 소수일 떄, 법 의 합동식에서는 양변을 의 배수가 아닌 임의의 수로 나눌 수 있다.
페르마의 소정리
페르마 소정리
암호학의 핵심이 되는 정리
는 소수, 는 의 배수가 아닌 정수일 때,
증명
{ 1, 2, ... , p-1 }과 같은 크기가 인 집합 (p는 소수)
모든 원소에 a를 곱한다 (a는 p의 배수가 아닌 정수)
다음 사실을 보이는 것이 증명의 핵심
{ 1, 2, ⋯, p−1 } ≡ { a, 2a, ⋯, (p−1)a } mod p
집합이 같으려면 일단
{ a, 2a, ⋯, (p−1)a } mod p의 모든 원소들은 서로 다르다.
귀류법을 쓰면 간단하다.
인데 인 가 존재한다고 가정.
p가 소수이고 a는 p의 배수가 아닌 정수이므로 양변을 a로 나눌 수 있다.
양변을 나누면
따라서 두 집합은 같은 집합이다.
두 집합이 법p에 대해 동일하므로 이 두 집합의 모든 각 원소를 곱한 값도 같을 것이다.
aᴾ⁻¹(p−1)! ≡ (p−1)! mod p
(p−1)!과 p는 공통 인수를 가지지 않으므로 서로소이다.
따라서 (p−1)!의 역원이 존재하며, 양변을 (p−1)!로 나누면
페르마의 소정리 aᴾ⁻¹ ≡ 1 mod p
기약잉여계
페르마 소정리의 증명 과정에서 중요한 개념이 등장한다.
p가 소수일 때, 아래의 식이 성립한다.
{ 1, 2, ⋯, p−1 } ≡ { a, 2a, ⋯, (p−1)a } mod p이런 형태의 집합은 정수론 곳곳에서 중요하게 쓰인다.
그래서 이름도 있다.
기약잉여계 : 정수 m에 대하여 1부터 m-1까지 m과 서로소인 수들을 모아놓은 것
예를 들어 9 기약잉여계는
모든 원소가 역원을 가지기 때문에, 언제나 나눗셈이 가능하다.
오일러의 정리와 오일러 파이 함수
오일러 정리
aᵠ⁽ⁿ⁾ ≡ 1 mod n (단, a와 n은 서로소)
(페르마 소정리 aᴾ⁻¹ ≡ 1 mod p)
오일러 파이 함수 (Euler Phi Function) 으로 불리는 함수
1부터 n까지 n과 서로소인 수들의 개수
예를 들어 을 구하면, 10과 서로소인 수는 1, 3, 7, 9이므로,
오일러 정리의 증명
기약잉여계를 사용하면 됨! (기약잉여계: n과 서로소인 n 이하의 정수로 이루어진 집합 M)
정수 의 기약잉여계 의 모든 원소를 다음과 같이 써 봄
여기에서 은 오일러 파이 함수
페르마의 소정리와 동일한 단계를 밟으면
이 서로소일 때, 두 집합은 동일한 집합임.
M = {p₁, p₂, ⋯, pᵩ₍ₙ₎} n과 서로소인 수들로 이루어진 기약잉여계
여기서 과 의 각 원소를 곱한 값이 같아야 한다.
기약잉여계는 n과 서로소인 수들만 이루어져 있으므로,
기약잉여계의 원소의 총 곱인 p₁p₂⋯pᵩ₍ₙ₎도 n과 서로소이다.
따라서 양변을 p₁p₂⋯pᵩ₍ₙ₎로 나눌 수 있으며, 그 결과가 오일러 정리.
∴ aᵠ⁽ⁿ⁾ ≡ 1 mod n
오일러 파이 함수는 곱셈적 함수이다
중요한 것은, 오일러 파이 함수를 어떻게 계산할 수 있느냐다.
오일러 파이 함수를 계산할 수 있어야 실제로 정리를 써먹을 수 있음.
오일러 파이 함수의 계산을 위한 가장 중요한 성질은
오일러 파이 함수가 곱셈적 함수 라는 성질이다.
즉,
φ(m)φ(n) = φ(mn) (단, m,n은 서로소)
이 사실의 증명은 다음과 같다.
다음과 같은 m x n의 표가 있을 때,
여기서 다음 두 가지 경우를 생각해보자.
- 은 과 서로소가 아니다: 행, 즉 꼴의 모든 수는 과 서로소가 아니다.
- 은 과 서로소이다: 행, 즉 꼴의 모든 수는 과 서로소이 다.
두 번째 케이스의 경우, r행의 n개의 수들은 법 n에 대해 서로 다르다.
귀류법으로 증명 가능. 만약 이라면, 이 되고,
이 서로소이므로 양변을 으로 나눌 수 있어 이 됨.
그런데 이므로 가 되어 모순.
즉 다음 사실이 도출된다.
이 과 서로소일 때, 행의 원소들은 법 에 대해 서로 다르다.
그런데 r행의 원소가 n개 존재하므로, r행은 다음 집합과 합동이다.
0붙터 n-1까지 모든 수가 빠짐없이 있으므로,
여기에는 n과 서로소인
- 의 표로 수를 쭉 쓰면, 과 서로소인 정수 에 대해 행의 수들은 모두 과 서로소이며, 법 에 대해 서로 다르다.
- 그런데 행에는 개의 수가 있으므로, 이는 0부터 까지 모든 수가 빠짐없이 있다는 말이며, 과 서로소인 개의 수들도 빠짐없이 있다는 말이다.
- 한편 행의 모든 수는 과 서로소이므로, 이 수들은 과 동시에 서로소이며, 즉 과 서로소이다.
- 이러한 은 개 있으므로, 과 서로소인 수들은 총 개가 있다.
A와 의 최대공약수가 1이 아니려면
(p보다 작은 p 배수는 1,2,3 ... pᴷ⁻¹을 p의 곱한 것이니까 p의 배수의 개수도 pᴷ⁻¹ 개)
RSA 암호 개념
공개키로 잠그고 비밀키로 열기
잠그는 건 누구나 해도 상관 없다
RSA 암호: 준비
1. 매우 큰 소수 p, q를 고른다. (150 ~ 600 자리 정도)
2. 두 소수를 곱해 n = pq를 얻는다. 여기서 n은 첫번째 공개키이다.
3. φ(n)을 구한다. 파이 함수 성질에 의해 φ(n) = (p-1)(q-1)이다.
4. φ(n)과 서로소인 수 e를 고른다. 단, 1<e<φ(n)이다. e는 두번째 공개키이다.
5. de ≡ 1 mod φ(n)이 되는 d를 고른다. d는 비밀키이다.
비밀키 d는 d와 e를 곱한 값을 φ(n)으로 나누었을 때 나머지가 1이 되는 것으로 고른다.
여기서 d는 e의 모듈러 곱셈 역원이다.
확장 유클리드 호제법을 통해 d 구하기
e는 보통 이라는 소수를 사용하는 것이 관습이지만, 어떤 소수를 쓰든 상관 없다.
d는 확장 유클리드 알고리즘을 활용하면 쉽게 계산할 수 있다.
확장 유클리드 알고리즘은 를 만족하는 정수 를 구하는 알고리즘이다.
1. 풀어야 할 식 : de ≡ 1 (mod φ(n))
2. 모듈러 연산을 방적식 형태로 변형 : de - kφ(n) = 1
3. 확장 유클리드 호제법에 적용할 값: a = e, b = φ(n)
4. 알고리즘 실행하면 ex + φ(n)y = gcd(e, φ(n)) 형태의 해를 얻는다.
5. e와 φ(n)은 서로소이므로 최대공약수는 1이다. 따라서 식은 ex + φ(n)y = 1이 된다.
6. y값을 없애서 x를 찾기 위해 위 식을 법 에 대한 합동식으로 바꾸면 :
(RSA 암호에서 비밀키 d를 찾는 과정은 본질적으로 공개키 e의 모듈러 곱셈 역원을 찾는 과정이다.
따라서 방정식을 합동식으로 변환하면 우리가 풀어야 할 문제의 본질을
가장 단순하고 명료한 형태로 표현할 수 있다.)
7. 이때 찾게 되는 x값이 바로 비밀키 d이다. (x가 음수일 경우 φ(n)을 더해 양수로 만든다.)
RSA 암호 : 암호화
이제 e, d를 이용해 메세지를 암호화 하는 방법을 알아보자.
1. 발신자는 메세지를 미리 합의된 방법(ASCII, UTF-8 등)을 이용하여
숫자 m으로 바꾼다. m<n이어야만
다음 단계에서 법 n을 취할 때 정보가 손실되지 않는다.
2. 그 다음 c ≡ mᵉ mod n 을 구한다.
여기서 c가 암호화된 메세지이다.
공개키 n, e를 활용해 암호화 함.
RSA 암호 : 복호화
복호화에서 오일러 공식이 활약한다.
1. cᵈ를 n으로 나눈 나머지를 구한다. 그것이 바로 m이다.
2. m을 다시 알파벳으로 바꾸면 성공적 메세지 전달.
1번이 성립한 이유?
c ≡ mᵉ mod n 이므로, cᵈ ≡ mᵈᵉ mod n 이다.
그런데 앞서 de ≡ 1 mod φ(n)이 되도록 설정했기 때문에,
이를 일반 방정식으로 바꾸면 de = k * φ(n) + 1이다.
고로 cᵈ ≡ mᵈᵉ ≡ mᵏᵠ⁽ⁿ⁾⁺¹ mod n
지수법칙에 따라 식을 분리할 수 있다
cᵈ ≡ mᵏᵠ⁽ⁿ⁾⁺¹ ≡ mᵏᵠ⁽ⁿ⁾ × m mod n
오일러 정리 적용하기 (핵심!!)
오일러 정리 : m과 n이 서로소(최대공약수가 1)일 때, m^φ(n) ≡ 1 (mod n) 이 성립
(mᵠ⁽ⁿ⁾)ᵏ × m mod n 은 오일러 정리에 의해 mᵠ⁽ⁿ⁾ 부분은 1로 취급할 수 있다
1ᵏ × m mod n
1은 언제나 1이므로, 식은
cᵈ ≡ m mod n 으로 정리된다.
결론적으로 m이 복원된다.
중국인의 나머지 정리
여러 개의 합동식(congruence)이 주어졌을 때, 이 모든 합동식congruence를 동시에 만족하는 정수 해를 찾는 방법
어떤 수를 여러 다른 수로 나누었을 때 각각의 나머지가 주어진다면, 원래 수를 찾을 수 있다.
idea
각 나눗수의 나머지를 조합하여 하나의 유일한 해를 찾아내는 것
예를 들어 어떤 수가 3으로 나누면 2가 남고, 5로 나누면 3이 남는다.
중국인의 나머지 정리로 이 조건을 만족하는 수를 찾을 수 있다.
표현
x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)
와 같은 합동식이 있고
n₁, n₂, ..., nₖ는 서로소이고
a₁, a₂, ..., aₖ는 임의의 정수이면
이 연립 합동식의 해는 다음과 같이 표현될 수 있다.
x ≡ (a₁N₁M₁ + a₂N₂M₂ + ... + aₖNₖMₖ) (mod N)
위 조건의 연립 합동식은 항상 해를 가진다.
해를 구하는 방법
1. N 계산하기 : 모든 nᵢ를 곱하여 N = n₁⋅n₂⋅...⋅nₖ를 계산
2. Nᵢ 계산하기 : 각 i에 대해 nᵢ = N / nᵢ 를 계산
3. Mᵢ 계산하기 : 각 i에 대해 NᵢMᵢ 를 만족하는 Mᵢ
(즉, Nᵢ의 nᵢ에 대한 모듈러 역원)를 찾는다.
확장된 유클리드 호제법을 사용하여 찾을 수 있다.
4. 해 x 계산하기 : 최종 해 x는 다음과 같이 주어진다.
x ≡ (a₁N₁M₁ + a₂N₂M₂ + ... + aₖNₖMₖ) (mod N)
중국인의 나머지 정리와 정수론
(Chinese Remainder Theorem, CRT)
1. Congruence
정수 를 으로 나눈 나머지가 와 같을 때,
( 는 을 법으로 와 합동이다)라고 표현.
이는 가 의 배수라는 것을 의미한다.
중국인의 나머지 정리는 궁극적으로 연립 합동식을 해결하는 문제이다.
CRT는 여러 개의 독립적인 합동식
x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)
를 동시에 만족하는 x를 찾는 것이 목표이다.
각 합동식은 x에 대한 하나의 조건을 제시하며, CRT는 이 조건을 통합하여 하나의 해를 도출한다.
2. Coprime / Relatively Prime
두 정수 a와 b의 최대공약수(GCD)가 1일 때, a와 b는 서로소이다.
gcd(a,b) = 1
CRT의 핵심 전제 조건 중 하나는, 주어진 모듈러 n₁, n₂, ..., nₖ가
쌍마다 서로소(pairwise coprime)여야 한다는 것이다.
(모든 서로 다른 두 다항식의 쌍이 서로소라면, 이들이 쌍마다 서로소라고 한다.)
만약 모듈러들이 서로소가 아니라면, 연립 합동식의 해가 존재하지 않을 수도 있고, 존재하더라도 유일하지 않을 수 있다.
서로소 조건은 각 합동식이 동립적으로 x에 대한 정보를 제공하며, 이 정보들이 충돌하지 않고 유일한 해를 보장하는 데 필수적이다.
3. Modular Multiplicative Inverse
정수 a에 대해 ay ≡ 1 mod m을 만족하는 정수 y를 법 m에 대한 a의 모듈러 역원이라고 한다.
모듈러 역원은 a와 m이 서로소일 때만 존재한다.
CRT의 해 공식
x ≡ (a₁N₁M₁ + a₂N₂M₂ + ... + aₖNₖMₖ) (mod N)에서
에서 Mᵢ는 Nᵢ에 대한 nᵢ의 곱셈 역원입니다. 즉, NᵢMᵢ ≡ 1 (mod nᵢ) 를 만족하는 수입니다.
4. Extended Euclidean Algorithm
두 정수 a, b의 최대공약수 gcb(a,b)를 구하는 유클리드 호제법을 확장하여,
gcd(a,b) = ax + by를 만족하는 정수 x, y를 찾는 알고리즘. (베주항등식)
모듈러 역원 Mᵢ를 찾는 데 사용된다.
합동식: NᵢMᵢ ≡ 1 mod nᵢ
방정식화: NᵢMᵢ - 1 = knᵢ
베주 항등식: NᵢMᵢ - knᵢ = 1
=> 확장 유클리드 호제법을 통해 mᵢ를 구할 수 있다.
https://blog.naver.com/kks227/221635322468
중국인의 나머지 정리(Chinese Remainder Theorem)
안녕하세요. 다시 수학, 그 중에서도 정수론 관련 주제를 작성하려고 합니다. 이번에 다룰 주제는 글 제목...
blog.naver.com
CRT의 증명
존재성existence
i번째 합동식에 대해 N_i = N / n_i라고 하자.
모든 n_i값들끼리 서로소이므로, n_i와 N_i역시 서로소이다.
이 때 베주 항등식(Bezout;s identity)을 적용하면,
NᵢMᵢ + nᵢmᵢ = 1
위 식을 만족하는 Nᵢ mᵢ가 존재한다. 여기서 만약 x를
로 둔다면, 임의의 i에 대해
가 성립한다는 것을 관찰할 수 있다.
유일성uniqueness
'공부' 카테고리의 다른 글
I/O Bound와 Context Switching (0) 2025.07.18 DB 고민: PK, 정규화와 역정규화 (1) 2024.07.01 [JAVA] final (0) 2024.06.22 [JAVA] Thread Quiz (0) 2024.06.20 [JAVA]참조 유형의 4단계 / [운영체제] Locality of Reference (0) 2024.06.19