Applications of Number Theory
유클리드 호제법과 합동, 중국인의 나머지 정리, 오일러 φ 함수와 원시근에서 디피-헬만 키 교환과 RSA, 연분수, 그리고 양자컴퓨터 기초까지. MATH463 영문 강의노트(최도훈)를 한국어·영어 대조로 정리했으며, 모든 시험 문제가 연습문제에서 출제되므로 Exercise 풀이를 중심에 둡니다. 강의노트가 갱신되는 학기 중에는 이 가이드도 함께 갱신됩니다.
각 단원의 정의(Definitions), 정리·따름정리(Theorems & Corollaries), 주의(Remarks), 예시(Examples), 알고리즘(Algorithms)과 연습문제(Exercises)를 영문 원문과 한국어 번역의 대조 형식으로 학습할 수 있습니다.
아래에서 원하는 단원을 선택하세요.
§1.1–1.3 The Euclidean Algorithm and the Diophantine Equation ax + by = c
최대공약수의 정의, 나눗셈 알고리즘과 유클리드 호제법, 확장 유클리드 호제법으로 구하는 ax + by = gcd(a, b)의 정수해, 그리고 특수해와 동차방정식 ax + by = 0의 해로부터 얻는 모든 정수해 — 원문 풀이가 인쇄된 Exercise 1.8·1.13 포함
환경 13 · 연습문제 7 · 알고리즘 3
§1.4–1.5 Modulo Arithmetic and Inverses Modulo n
법 n에 대한 합동의 정의와 성질, 거듭제곱의 나머지를 2진 표현으로 빠르게 계산하는 재귀 알고리즘, 법 n에 대한 역원의 존재 조건(gcd(a, n) = 1)과 유일성, 역원을 구하는 알고리즘
환경 23(+주의 1) · 연습문제 9 · 알고리즘 2
§1.6–1.9 Linear Congruences, CRT, Euler’s φ and Primitive Roots
일차합동식 ax ≡ b의 해, 중국인의 나머지 정리와 그 알고리즘, 오일러 φ 함수의 계산법, 법 n에 대한 위수와 원시근, 오일러 정리와 페르마 소정리 — 단원 중 연습문제가 가장 많은 구간
환경 33(+주의 3) · 연습문제 15 · 알고리즘 1
§2 Cryptology: Diffie-Hellman Key Exchange and RSA
이산로그 문제의 어려움에서 출발하는 디피-헬만 키 교환 알고리즘과 도청자 문제, 공개키 암호체계 RSA의 알고리즘과 암호화·복호화 예제
환경 9 · 연습문제 5 · 알고리즘 2
§3.1 Finite Continued Fractions
유리수의 단순연분수 전개와 유클리드 호제법의 관계, 기호 [a₀; a₁, …, aₙ], k번째 근사분수 Cₖ = pₖ/qₖ의 점화식과 성질, 연분수로 푸는 일차 디오판토스 방정식 — 버튼(Burton) 15장 기반
환경 20 · 연습문제 10 · 알고리즘 1
§3.2 Infinite Continued Fractions and Best Approximations
단순연분수의 유일성, 무리수의 무한 연분수 전개와 순환연분수, 근사분수의 오차 평가와 최선의 근사 정리 — π와 √2의 근사분수 예제 포함
환경 16 · 연습문제 6 · 알고리즘 1
§4.1–4.4 Qubits and Gates
고전컴퓨터와 양자컴퓨터, 비트와 큐비트, 중첩과 붕괴, 텐서곱으로 만드는 n-큐비트, AND·OR·NOT 고전 게이트와 진리표, 유니터리 행렬로 주어지는 양자 게이트와 CNOT·X·Z 게이트
환경 16 · 연습문제 10 · 그림 4
§4.5–4.6 Measurement, the Hadamard Gate and the CNOT Gate
에르미트 행렬과 정규직교 고유기저로 기술하는 측정, 측정 확률과 상태의 붕괴, 아다마르 게이트와 |+⟩·|−⟩, CNOT·SWAP 게이트의 기호와 회로
환경 9 · 연습문제 5 · 그림 1