2주차 – 수학적 배경 주교재 2장
목차 정수론 법연산 유한체 NP 문제
정수론 R : 실수 집합 Z : 정수 집합 N : 자연수 집합 Zm : { 0, 1, 2, … , m-1} 소수(prime number) 1과 자신으로만 나누어지는 수 약수가 1과 자신밖에 없는 수 서로소 두 정수 a와 b의 공약수가 1밖에 없는 경우, 서로소라고 한다.
정수 연산 덧셈 곱셈 항등원 역원 a, b ∈ Z → a + b ∈ Z a, b ∈ Z → a ⅹ b ∈ Z a + b = a ∈ Z , b는 덧셈 항등원 a ⅹ b = a ∈ Z , b는 곱셈 항등원 역원 a + c = 0 ∈ Z , c는 a의 덧셈에 대한 역원 a ⅹ c = 1 ∈ Z , c는 a의 곱셈에 대한 역원
공약수와 공배수 약수와 배수 공배수 공약수 b = a ∙c → a|b , c|b : 약수는 왼쪽에 배수는 오른쪽에 a|b , c|b → b는 a와 c의 공배수 최소공배수 lcm : least common multiple 공약수 a|b , a|c → a는 b와 c의 공약수 최대공약수 gcd : greatest common divisor
법 연산 합동식 완전 잉여계 (complete residue system) a ≡ b mod m → m|(a-b) , a-b = mk 완전 잉여계 (complete residue system) 법 m에 대한 완전 잉여계 Zm = {0, 1, 2, … , m-1} 기약 잉여계 (reduced residue system) Zm* = {a ∈ Zm | gcd(a, m) = 1} 오일러(Euler) 함수 Φ(m) = | Zm* |
잉여계 예 완전 잉여계 기약 잉여계 Question : Φ(97) = | Z97* | = ? 잉여계 예 완전 잉여계 Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8 } 기약 잉여계 Z9* = {1, 2, 4, 5, 7, 8 } Question : Φ(97) = | Z97* | = ? 힌트 : 97은 소수이다 정답 : 96 그렇다면, p가 소수일 때, Φ(p) = | Zp* | = p-1
Euler 함수 Φ(m)의 계산 Φ(m) = Φ(ps ⅹ qt ⅹ ru ) = (ps – ps-1 ) (qt – qt-1 ) (ru – ru-1 ) = m (1-p -1) (1-q -1) (1-r -1) 단, p, q, r 은 소수. 예 Φ(7) = (71-70) = 6 Φ(15) = Φ(3 ⅹ5) = (3 – 1)(5 – 1) = 8 Φ(9) = Φ(32) = (32 – 31) = 6
Euler의 정리와 Fermat의 정리 기약 잉여계 m은 소수 또는 합성수 p는 소수 오일러의 정리 페르마의 정리
유클리드(Euclid) 호제법 직접 계산하는 방법 일반적인 표기법 (판서) 1차 결합 만들기
역원 계산
원시근 위수 원시근 기약 잉여계에서 위수가 Φ(m)인 원소 a를 원시근(원시원소, 생성자)이라고 한다. → 이 식을 만족하는 가장 작은 양의 정수
이산 대수 (discrete logarithm)
이차 잉여 이차 잉여 이차 비잉여 이차 잉여 예 (Z13) 이차 잉여 : 이차 비잉여 :
유한체(Finite Field) 유한체의 조건 갈로아체(Galois field) 가감승제 정의 유한 집합 대소관계 무 연속성 무 갈로아체(Galois field) 법 p가 소수인 기약 잉여계
유한체 예 가산
유한체 예(계속) 승산 누승
유한체 예(계속) 원시근 3, 5 위수 2, 3, 6 | 6 이산 대수 - NP 문제
유한체와 확대체 유한체 확대체 확대체 연산
확대체 예 원소들
문제와 계산 복잡도 이론 계산 복잡도 이론 문제(Problem)의 분류 문제를 해결하는 알고리즘의 복잡도(시간, 공간)를 분류하기 위한 이론 O notation, Ω notation, Θ notation 문제(Problem)의 분류 풀 수 없는 문제 풀 수 있는 문제 쉬운 문제 (feasible) P문제 (다항식 시간 문제) : 문제 해결을 위한 다항식 복잡도의 결정적 알고리즘이 존재하는 경우 어려운 문제 (infeasible) NP문제 (지수식 시간 문제) : 문제 해결을 위한 다항식 복잡도의 비결정적 알고리즘이 존재하는 경우