�ݺ�ߣ

HI-ARC 정기모임 #10
(정수론 Part 1)
이재열(@kodingwarrior)

정수론은 말 그대로
정수의 성질을 다루는
이론

정수를 이용한 연산
덧셈, 뺄셈, 곱셈,
나눗셈, 나머지

나머지 연산(혹은 modulo 연산, n을 법으로 한
연산)
나누어 떨어지면 0을 반환.
● n | a
a는 n의 배수이다.
● a mod n
a를 n으로 나누었을 때 나머지 값

나머지 연산(혹은 modulo 연산, n을 법으로 한
연산)
● a ≡ b mod n
a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다)
● 모듈러 연산의 특성
a ≡ b mod n 이면, a - b는 n의 배수이다. -> (a - b) mod n = 0
mod n = Zn = { 0, 1, ..., n - 1 }

나머지 연산의 성질
a = mb+n, c = m’b + n’
● (a%b + c%b)%b == (a+c)%b
(a+c)%b = ((mb + n) + (m’b + n’)) % b = ((m’+m)b + (n+n’))%b = (n+n’) % b
● (a*c) % b == ((a%b) * (c%b)) % b
(a*c) % b == ((mb + n) + (m’b + n’)) % b == (((m*m’)b + n + n’)b + n*n’) % b == n*n’ % b
● 단, 나눗셈은 지원하지 않음

나머지 연산 연습문제
나머지 연산을 이용한 피보나치 수열 구현
https://www.acmicpc.net/problem/1904

유클리드 호제법
최대공약수를 구하는 알고리즘
유클리드 호제법의 시간 복잡도 : O(lg N)
A = BQ + R 이라 하면, GCD(A, B) = GCD(B, R) 이다 .

유클리드 호제법의 증명 (1)
● 일단은 GCD(A,B) = G 라고 가정해둔다.
○ 그렇다면, 서로소인 두 개의 정수 a, b 에 대해 A = Ga , B = Gb
● A = B*Q+R 라는 가정에 A = G*a, B = G*b 를 대입해보자
○ G*a = G*b*Q + R 이고 R = G*(a-b*Q)

유클리드 호제법의 증명 (2)
● gcd(b, a-b*Q) = m 이라고 한다면, 적당한 서로소인 정수 k, l에 대해
○ b = m*k, a-b*Q = m*l
○ 한편, a = m*l + b*Q = m*k + m*l*Q = m*(k+l*Q)
● 즉, gcd(a, b) = m 이라 할 수 있는데, a, b 는 서로소이므로 m = 1
● 따라서, B 와 R 이 최대공약수(G)가 같다는 가정하에 위와 같이 b와 a-b*Q 도
서로소가 됨.
○ (B 와 a-b*Q 가 서로소가 아니라면, GCD(B, R) = G*G’ 꼴로 나타나게 된다.)
● A = B*Q + R 일 때, GCD(A, B) == GCD(B, R) 임이 증명됨.

유클리드 호제법의 활용
재귀적으로 계속해서 유클리드
호제법을 수행하다보면 최대공약수를
얻어낼 수 있게 된다.

시간 복잡도의 증명
최악의 경우는 r1, r2, r3, r4, …, rn 을 나열한 형태가 피보나치 수열을 거꾸로 나열한
형태와 같음
610 = 377*1 + 233
377 = 233*1 + 144
...
5 = 3*1 + 1
3 = 2*1 + 1
2 = 1*1 + 1
1 = 1*1 + 0

Pseudo code
Typedef unsigned long long ULL;
ULL gcd(ULL a, ULL b)
{
if(a % b == 0) return b;
else return gcd(b, a % b);
}

유클리드 호제법 연습문제
유클리드 호제법을 이용한 최대공약수 최소공배수 구하기

확장 유클리드 정리
임의의 정수 a, b 에 대하여,
a*x + b*y = gcd(a, b) 를 만족시키는 정수 x, y 가 반드시 하나 존재한다.
중국인의 나머지 정리의 해를 구하거나,
모듈로(나머지) 연산 안에서 곱셈에 대한 역원을 구할 때 사용됨.

GCD(A, B) = AX + BY ?
유클리드 호제법을 다시 한번 들여다 보자
얘가 a와 b의
최대공약수

나머지 R 을 중심으로 식을 뒤집어서 생각해보자

a 와 b의 선형적인 합으로 나타낼 수 있다.
이는 재귀적으로 증명이
가능하다는 것을 알 수
있음
( -q2 )

51 과 19 의 선형결합으로 최대공약수 구하기

Pseudo code
a % b 의 결과가 0 일 경우
갈수록 작아지는 a, b 의 선형적인 결합으로도 GCD
는 동일하기 때문에, depth 가 더 깊은 함수에서 x,
y를 전달받아 최종 결과값을 내는 방식

확장 유클리드 정리의 응용
곱셈에 대한 역원을 구할 때 쓰인다. (특히, RSA 알고리즘)
페르마의 소정리
aN-1
≡ 1 (mod N) iff a 와 N 이 서로소 일 때
즉, 법 N 에 대해 a 에 대한 곱셈의 역원은 aN-2
한 편, x*N + s*t = 1 (mod N) 의 식을 이용해서도 곱셈의 역원을 구할 수 있다.

확장 유클리드 정리를 이용하는 문제

에라토스테네스의 체
N 이하의 소수의 리스트를 구하는 알고리즘
⁕ 1부터 n까지의 자연수를 전부 나열한다.
⁕ 소수도, 합성수도 아닌 1을 지운다.
⁕ 남아 있는 자연수 중 가장 작은 수인 2는 소수다. 이제 2의 배수들을 모두 지운다.
⁕ 남아 있는 자연수 중 가장 작은 수인 3은 소수다. 이제 3의 배수들을 모두 지운다.
⁕ 남아 있는 자연수 중 가장 작은 수는 소수다. 이 수의 배수들을 모두 지운다.
⁕ 위의 과정을 계속해서 반복하면, 남아 있는 수가 모두 소수다.

EX) 100 이하의 소수의 리스트 구하기
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2, 3

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2, 3, 5

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2, 3, 5, 7

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2, 3, 5, 7, ?

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Prime numbers :
2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37,
41, 43, 47, 53, 59,
61, 67, 71, 73, 79,
83, 89, 91, 97

Pseudo code(무식한 시도가 정답일 수도
있다.)#define MAX_LEN 1000
bool sieve[MAX_LEN+1];
int primes[MAX_LEN+1];
int cnt = 0;
sieve[1] = true;
for(int i=1; i<=MAX_LEN; ++i) {
if(!sieve[i]) {
primes[count++] = i;
for(int j=i; j<=MAX_LEN; j+=i) sieve[j] = true;
}
} 시간복잡도 계산
1 + N/2 + N/3 + 1 + N/5 + 1 + N/7 + …
~ N(1 + 1/2 + 1/3 + … + 1/N)
~ O(N lg N)
Fact :
∫ 1/x dx = ln x

Pseudo code
primes[count++] = 2;
for(int j=2; j<=MAX_LEN; j+=2) sieve[j] = true;
for(int i=3; i<=MAX_LEN; i+=2) {
if(!sieve[i]) {
for(int j=i; j<=MAX_LEN; j+=i) sieve[j] = true;
}
}
Fact : 2를 제외한 소수는 홀수이다.
== 3부터 검사할 때 두단계 뛰어도 상관없음
O Notation 으로 나타냈을때, 차수는 변하지
않지만 탐색범위와 계산시간은 절반으로
줄었음.

Pseudo code
for(int i=3; i<=MAX_LEN; i+=2) {
if(!sieve[i]) {
for(int j=i*i; j<=MAX_LEN; j+=i) sieve[j] = true;
}
}
Fact : 이와 같은 알고리즘을 계속해서 수행하고 있다고
가정할때,
i * i 미만의 수는 앞 단계에서 이미 조회했기 때문에
두번 다시 살펴볼 필요가 없음
EX) I, 2*i, 3*i, … , (i-1) * i 는 앞 단계에서 조회했던 원소
배수가 되는 원소를 제거하는 과정에서
근소하게나마 성능의 개선이 있음

Pseudo code
int primes[MAX_LEN+1]; int i;
for(i=3; i*i<=MAX_LEN; i+=2) {
if(!sieve[i]) {
for(int j=i*i; j<=MAX_LEN; j+=i) sieve[j] = true;
}
}
for( ; i <= MAX_LEN; i += 2) if(!sieve[i]) primes[count++] = i);
Fact : 최대범위인 N을 두 개의 약수(n,m)로 구성된
합성수로 본다면, 작은 편에 속하는 n은 아무리 커봐야
sqrt(N)
(즉, N이 제곱수라는 조건)
배수가 되는 수를 하나하나 제거하는 과정도 역시 sqrt(N)
까지만 조회하면 그만임
sqrt(N) 이상부터는 계속해서 한번만 조회하고
끝이기 때문에 상당한 성능개선이 있음
에라토스테네스 체 알고리즘의 최종 시간복잡도는 O(n log log n)

에라토스테네스의 체 연습문제
에라토스테네스의 체를 이용하여 소수 구하기

이건 시작에 불과함
중국인의 나머지 정리,
오일러 파이 함수, 뤼카의 정리, ...

�ݺ�ߣ

HI-ARC Number Theory

More Related Content

What's hot (20)

Similar to HI-ARC Number Theory (20)

More from Jae-yeol Lee (12)

HI-ARC Number Theory