🔷정수론에 대해 알아보자 !
💡 먼저 정수론이란 ?
정수론, 또는 수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문이다.
Die Mathematik ist die Königin der Wissenschaften, und die Arithmetik ist die Königin der Mathematik.
수학은 과학의 여왕이고 정수론은 수학의 여왕이다.
즉 정수론이란, 수의 성질을 파악하는 분야이다.
🔷알고리즘과 정수론
정수론은 알고리즘 분야에서도 적용된다. 정수론을 알아보며, 다양한 코딩 알고리즘으로 한번 적용해보자 !
알고리즘에 적용되는 정수론
- 모듈러의 성질
- 소수 판정
- 약수 구하기
- 소인수 분해
- 유클리드 호재법
- 에라토스테네스의 체
- 빠른 거듭제곱
1. 모듈러 연산의 성질 (Modular Arithmetic Properties)
모듈러 연산(Modular Arithmetic)은 나머지 연산을 기반으로 하는 연산 체계다. 주로
큰 수의 연산 최적화, 암호학, 수론 알고리즘에서 사용된다.
모듈러 연산의 기본 개념 :
a mod m = r
위에서 mod는 모듈러의 나머지 연산을 표현함.
즉, a를 m으로 나눈 나머지 구하는 연산이다 !
모듈러 연산은 덧셈, 뺄셈, 곱셈, 거듭제곱 등에 대해 다음과 같은 성질을 가짐.
(1) 덧셈의 성질
(a+b) mod m=[(a mod m)+(b mod m)] mod m
예제
(7+5) mod 4=12 mod 4= 0[(7 mod 4) + (5 mod 4)] mod 4 =(3 + 1) mod 4 =4 mod 4 = 0
(2) 뺄셈의 성질
(a−b) mod m=[(a mod m)−(b mod m)+m] mod m
예제
(7−5) mod 4=2 mod 4= 2[(7 mod 4) − (5 mod 4)+4] mod 4 =(3−1+4) mod 4 =6 mod 4 = 2
⚠️음수가 나올 경우 반드시 양수로 변환하기 위해 +m을 추가해 줌.
(3) 곱셈의 성질
(a×b) mod m=[(a mod m)×(b mod m)] mod m
예제
(7×5) mod 4=35 mod 4= 3[(7 mod 4) × (5 mod 4)] mod 4 =(3×1) mod 4 =3 mod 4 = 3
(3) 거듭제곱(지수)의 성질
(ab) mod m=[(a mod m)b] mod m
예제
(34) mod 5=81 mod 5=1
하지만 직접 계산하면 시간 복잡도가 너무 커지므로 반복 제곱법 (Exponentiation by Squaring)을 사용해야함. 이 방법을 사용하면 O(log b) 시간 안에 계산 가능.
💡모듈러 연산에서는 일반적인 나눗셈이 불가능해서. 대신, 모듈러 곱셈 역원을 이용해야 한다 !
ex) a−1 mod m
이 값은 다음 두 가지 방법으로 구할 수 있다.
-
확장 유클리드 알고리즘:
- ax ≡ 1 (mod m)을 만족하는 x 를 찾음.
- 시간 복잡도: O(log m)
-
페르마의 소정리 (m이 소수일 때 사용 가능):
- am−2 mod m 을 계산하면 역원이 됨.
- 시간 복잡도: O(log m)
💡추가적으로 모듈러 연산에서는 분배법칙과 동치관계가 존재한다 !
✅ 모듈러 연산의 활용
(1) 큰 수 연산 최적화
- 거듭제곱을 빠르게 계산 (반복 제곱법)
- 큰 수의 나눗셈을 모듈러 역원을 이용해 해결
(2) 암호학 및 보안 (RSA 암호, 디지털 서명)
- 소수 p,q를 이용해 RSA 암호를 구현할 때 모듈러 연산 사용. p,qp, q
- 공개키/개인키 연산에서 모듈러 역원이 필수.
(3) 중국인의 나머지 정리 (CRT)
- 서로소인 모듈러 관계를 이용해 방정식을 쉽게 해결.
- 큰 수 연산을 작은 수 연산으로 나눠서 처리 가능.
(4) 순환 수열 및 반복 패턴 분석
- 모듈러 연산을 이용하면 패턴이 반복되는 주기를 쉽게 찾을 수 있음.
