홈 > 강의소개
정수론
이석민 교수
고려대학교 대학원 수학교육과 석사과정 졸업
Ph.D. in Mathematics at Johns Hopkins University, USA
고려대학교 대학원 수학교육과 석사과정 졸업
Ph.D. in Mathematics at Johns Hopkins University, USA
Johns Hopkins Univ.
건국대학교
현) 유니와이즈 자문교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 0개 챕터, 46강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
|
[1강] 정수의 기본성질
|
1:
15:
54
|
|
|
정수의 기본 성질과 수 집합, 정렬성 및 가산성 요약
• 정수·수집합·정렬성 및 대수적 수: 자연수·정수·유리수·실수·복소수와 정수공리·순서·정렬성 정의, 이를 이용한 √2의 무리수성 증명과 대수적 수 개념 정리 • 정수부분·비둘기집 원리·디리클레 근사: 최대정수함수와 소수부분 구조, 비둘기집 원리 공식화, 소수부분과 구간 분할을 통한 디리클레 근사 정리의 근사 절차 요약 • 수열·가산성·불가산성: 수열·등차·등비수열 정의, 정수·유리수의 가산성(대각선 열거)과 실수 집합의 불가산성(대각선 논법)을 통한 서로 다른 무한의 크기 구조 제시 |
||
|
[2강] 수학적 귀납법
|
1:
15:
59
|
|
|
수학적 귀납법과 이항정리, 다각수
• 수학적 귀납법·정렬성·일반화: 정렬성 원리에 기반한 제1·제2·일반화된 수학적 귀납법 정의와 동치성, 명제 집합 표현과 증명 구조 체계화 • 점화식·팩토리얼·이항계수·이항정리: 점화식에 의한 수열·함수의 유일한 정의 원리, 팩토리얼의 점화·파이 표기, 이항계수 정의·대칭성·파스칼 삼각형과 이항정리 및 합 공식(2^n, 교대합, k·이항계수 합) 구조 정리 • 다각수(삼각수·사각수·오각수·일반 m각형): 삼각수·사각수·오각수의 점화식·합·닫힌형 공식과 상호 관계, 일반 m각형 다각수 P(m,n)의 점화식·2차식 닫힌형·삼각수 분해 및 각수 증가에 따른 삼각수 차이 관계 정리 |
||
|
[3강] 피보나치 수열
|
0:
46:
33
|
|
|
Summary Content:
피보나치 수열의 합, 항등식, 황금비, 생성함수 핵심 정리 • 피보나치 수열과 기본 항등식: 재귀 정의와 음의 지수 확장, 전체·짝수항·제곱합 합 공식, 세·네 연속 항의 곱·제곱 차이가 ±1이 되는 항등식 및 64–65 퍼즐로 일반화되는 넓이 차이 구조 • 황금분할·황금비와 성장 속도: 황금분할에서 유도되는 황금비 α=(1+√5)/2, 근과 계수 관계(α+β=1, αβ=-1, α^2=α+1)와 피보나치 수의 기하급수적 성장 불등식 f_n>α^{n-2} 및 α^n과의 비교 • Binet 공식과 생성함수: 2차 방정식의 근 α,β와 생성함수 G(x)=x/(1-x-x^2)을 이용한 부분분수·등비급수 전개, 계수 비교를 통한 닫힌형 Binet 공식 f_n=(α^n-β^n)/√5 도출 및 피보나치 수의 정확한 값·점근 분석 도구 정리 |
||
|
[4강] 나눗셈 정리. 약수와 배수
|
1:
00:
04
|
|
|
정수론 나눗셈 정리와 약수·배수, 최대정수함수 응용 핵심 정리 정리
• 약수·배수와 배수집합 구조: 약수·배수 정의와 기본 성질, 공약수의 선형결합, 배수집합 aℤ의 포함관계와 덧셈·뺄셈에 닫힌 정수 부분집합의 구조 정리 • 나눗셈 정리와 정수 분류: 나눗셈 정리의 존재성·유일성 증명, 짝수·홀수와 나머지에 따른 정수 분류, 음수 포함 몫·나머지 표현의 규칙 정리 • 최대정수함수와 배수 계산: 몫과 최대정수함수의 대응, 구간 내 배수 개수 계산, ⌊x/b⌋·⌊x/(ab)⌋ 형태 공식과 배수 개수·거듭제곱 분모 처리 응용 |
||
|
[5강] 정수의 여러 가지 표현
|
1:
02:
30
|
|
|
정수의 여러 가지 표현: 진법 전개와 Cantor 전개 핵심 정리
• 정수의 b진법 전개: 모든 양의 정수를 고정된 밑수 b의 거듭제곱 합으로 유일하게 표현하고, 자릿수·몫·나머지 구조 및 2진법에서의 서로 다른 2의 거듭제곱 표현과 다양한 진법 변환 규칙을 제시 • b진법과 나눗셈 구조: b진수에서 특정 자릿수 분할을 통해 b^r로 나눈 몫(상위 자릿수)과 나머지(하위 r자리)를 결정하는 규칙으로 10진법 포함 각 진법의 나눗셈 구조를 통합적으로 해석 • 정수의 Cantor 전개식: 모든 양의 정수를 계수 조건 0≤a_k≤k, a_m≠0를 갖는 팩토리얼 합 n=∑a_k k! 형태로 유일하게 표현하고, 존재성·유일성 증명과 두 가지 계수 계산 알고리즘(큰 팩토리얼부터 나누기, 2·3·4·… 순차 나눗셈)을 제공 |
||
|
[6강] 소수. 최대공약수. 유클리드호제법
|
1:
10:
13
|
|
|
정수론 소수, 최대공약수, 유클리드 호제법 핵심 정리 요약
• 정수론 기초 개념: 소수·합성수·소인수 정의, 소수의 무한성, 합성수의 √n 이하 소인수 존재 정리 및 이를 기반으로 한 소수 판정법·에라토스테네스의 체 알고리즘 구조 • 최대공약수와 선형결합: 최대공약수의 정의와 서로소 개념, 가감 성질 (a+kb,b)=(a,b), aℤ+bℤ=(a,b)ℤ와 Bezout 정리로서 (a,b)=am+bn, (a,b)=1 ⇔ am+bn=1 구조 • 유클리드 호제법과 확장 알고리즘: 나머지열과 “마지막 0이 아닌 나머지 = (a,b)” 원리를 이용한 최대공약수 계산 절차, 몫 수열과 점화식 s_k,t_k로 (a,b)=as_n+bt_n 계수 산출 방법 정식화 |
||
|
[7강] 산술의 기본정리
|
1:
21:
42
|
|
|
정수론 산술의 기본정리와 소수·팩토리얼의 성질 요약
• 산술의 기본정리·표준분해: 모든 정수의 소수 곱 표현 존재·유일성, 표준분해를 통한 약수 개수, 최대공약수·최소공배수 구조와 특정 꼴 소수의 무한성, 연속 합성수 구성 원리 정리 • 유리수·무리수 판정: 유리수의 기약분수 유일 표현, √2 등 제곱근의 무리성 증명, 정계수 다항식 유리근 조건을 통한 정수근·무리근 판별 구조 제시 • 팩토리얼 소인수 구조: 정확한 소인수 지수 표기와 n!의 소인수 지수 합 공식, 팩토리얼 표준분해 계산 및 끝자리 0 개수 산출 절차 정리 |
||
|
[8강] Fermat 소수와 Mersenne 소수. 일차부정방정식
|
1:
11:
18
|
|
|
Summary Content:
페르마 소수와 메르센소수, 일차부정방정식 핵심 정리 요약 • Fermat 수·Fermat 소수·소수 무한성: Fermat 수 $F_n=2^{2^n}+1$의 정의와 인수분해 성질, 상호 서로소 구조와 각기 다른 소인수를 이용한 소수의 무한 존재 증명, $2^m+1$ 소수 ⇒ $m=2^n$ 조건 정리 • Mersenne 수·Mersenne 소수·최대공약수 정리: $M_m=2^m-1$ 정의와 $2^m-1$ 소수 ⇒ $m$ 소수 조건, $(a^m-1,a^n-1)=a^{(m,n)}-1$ 및 $(m,n)=1\iff (M_m,M_n)=1$ 구조로 지수와 최대공약수 관계, Mersenne 소수 예시와 미해결성 정리 • 일차부정방정식(2변수·다변수): $ax+by=c$ 및 $a_1x_1+\cdots+a_nx_n=c$의 해 존재 조건 $\gcd(\text{계수})\mid c$, 두 변수 일반해 공식 $x=x_0+\frac{b}{d}t,\;y=y_0-\frac{a}{d}t$와 Euclid(확장 Euclid) 알고리즘 활용, 매개변수 도입을 통한 다변수 환원과 부등식 조건에 따른 정수해 개수 결정 방법 정리 |
||
|
[9강] 소수의 분포
|
1:
24:
40
|
|
|
소수의 분포, 소수 생성 다항식과 소수 관련 정리·추측
• 소수 생성 다항식과 소수정리: 정계수 다항식의 전역 소수 생성 불가능성, 소수 개수 함수 π(x)와 소수정리(π(x)∼x/log x), n번째 소수의 성장률(pₙ∼n log n) 및 소수 역수합의 발산 구조 • 해석적·조합적 소수 분포 정리: Riemann zeta 함수와 Euler 곱을 통한 소수 분포 표현, 등차수열 속 소수(Dirichlet 정리·Green–Tao 정리), Bertrand 공준과 이항계수·valuation을 이용한 증명 및 pₙ≤2n, 조화급수 꼴 분수합의 비정수성 • 대표 소수 분포 추측: Landau 네 추측(제곱 사이 소수 Legendre 추측, 쌍둥이 소수와 Brun 상수, Goldbach 추측의 두 동치 형태, n²+1 꼴 소수 무한 존재 추측)과 각각의 내용·예시·미해결 현황 정리 |
||
|
[10강] 합동. 잉여류. 합동식의 활용
|
1:
24:
05
|
|
|
정수론 합동, 잉여류, 합동식의 활용 요약 (합동식, 잉여류, 바코드·ISBN 응용 중심)
• 합동과 잉여류 구조: 법 m에 대한 합동의 정의·동치관계 성질·연산법칙(덧셈·곱셈·다항식 대입)·소거 조건과 소수 모듈로 성질, 나머지와의 대응, 잉여류와 완전 잉여계(표준·절대 최소 완전 잉여계) 및 그 판정·변형 구조 정리 • 합동식 계산 규칙: 큰 거듭제곱 나머지 계산, 십진 전개를 이용한 2ᵏ·5ᵏ에 대한 뒤 k자리 규칙, 3·9의 자릿수 합 규칙, 11의 교차합 규칙, 7·11·13에 대한 세 자리 교차합 규칙을 통한 나머지 계산 절차 정리 • 바코드·ISBN 검증 구조: EAN-13 바코드의 가중합(1,3) 합동식 검증번호 구조, ISBN-10의 가중합 mod 11 검증식과 한 자리·두 자리 교환 오류 검출 원리, ISBN-13에서 접두부(978/979)와 바코드 규칙 결합을 통한 검증번호 산출 체계 정리 |
||
|
[11강] 일차합동식. 중국인의 나머지정리
|
1:
09:
40
|
|
|
정수론 일차합동식과 중국인의 나머지 정리 핵심 정리 요약
• 일차합동식과 역원: 일차합동식 ax≡b(mod m)의 해 존재 조건 d=(a,m)∣b와 해의 개수 d개 정리, (a,m)=1일 때 역원 a⁻¹(mod m) 존재와 유클리드 호제법을 통한 역원 계산 및 소거법 구조 제시 • 다항 합동식과 해 구조: 다항 합동식 f(x)≡0(mod m)의 차수·해·완전잉여계에서의 해 개수·동치 개념을 통해 합동식 해 집합과 표현 x≡a+mt(mod mn)의 구조적 분류 제시 • 중국인의 나머지 정리와 연립합동식: 쌍마다 서로소인 법에 대한 CRT 정리와 해 구성 공식 x≡∑a_kM_kx_k(mod M), 최소공배수를 통한 합동식 통합, 그리고 법이 서로소가 아닐 때 치환·소거·일차합동식 해법을 결합한 연립일차합동식 일반 해법 제시 |
||
|
[12강] 다항합동식
|
0:
53:
29
|
|
|
다항합동식 해법과 Hensel 보조정리 요약 (정수론 3.6 단원)
• 다항합동식 해법과 소수 거듭제곱 전략: 법 m의 소인수분해 후 각 소수 거듭제곱 모듈러에서 해를 구하고 중국인의 나머지 정리로 통합하여 f(x)≡0 (mod m)의 해를 구성함 • 형식적 도함수·다항식 테일러 전개: 형식적 도함수와 고계 도함수 정의, 이를 이용한 다항식 테일러 전개와 계수의 정수성으로 Hensel 보조정리 전개에 필요한 기본 도구를 제공함 • Hensel의 보조정리와 근 올리기: 단순근·다중근(분기/소멸) 세 경우로 분류하여 법 p의 해를 법 p^k로 올리는 조건과 절차를 제시하고, 반복 공식(정수론적 Newton 방법)으로 소수 거듭제곱 법에서의 다항합동식 해를 체계적으로 계산함 |
||
|
[13강] 일차연립합동식 (1)
|
0:
53:
24
|
|
|
일차 연립합동식과 행렬 역원, Cramer 공식 요약
• 일차 연립합동식과 행렬 표현: 연립합동식을 행렬식 형태 $AX≡B\pmod{m}$로 표현하고, 소거법과 합동 보존 성질을 통해 해 구조를 분석 • 모듈러 역행렬과 adjoint: $\gcd(\det A,m)=1$ 조건에서 법 $m$에 관한 역행렬 존재·유일성, 2×2 역원 공식과 일반 $n×n$에서 수반행렬(adj $A$)을 사용한 모듈러 역원 구성 • Cramer 공식의 모듈러 버전: $AX≡B\pmod{m}$에서 $\Delta=\det A$, $\bar\Delta$를 법 $m$에 관한 역원이라 할 때, 열 교체 행렬 $A_j$의 행렬식을 이용해 각 해 성분을 $x_j≡\bar\Delta\det A_j\pmod{m}$로 표현하는 해 공식 정리 |
||
|
[14강] 일차연립합동식 (2)
|
1:
07:
13
|
|
|
마방진과 일차연립합동식
• 마방진·대각마방진·대칭마방진: $0\sim n^2-1$과 위치 $(i,j)$의 1대1 대응을 이용해 행·열·대각·대칭쌍의 합을 일정하게 만드는 배열 구조, 전체 합과 한 줄 합·대칭쌍 합의 기본 공식 제시 • 선형 연립합동식과 구성 조건: 행렬식 $(ad-bc,n)=1$ 및 $a,b,c,d,a\pm c,b\pm d$의 서로소 조건에 따른 1대1 대응 존재 여부, 행·열·대각선 합이 $\tfrac{n(n^2-1)}2$가 되는 필요충분 조건, 짝수 $n$·$3$의 배수 $n$에서의 구성 불가능성 • 대칭 마방진 조건: 중심 대칭쌍 합이 $n^2-1$이 되기 위한 구조와 $2e-a-b\equiv1,\;2f-c-d\equiv1\pmod n$이라는 필요충분 조건을 통해 종횡·대각·대칭 성질을 동시에 갖는 마방진의 존재 조건 정리 |
||
|
[15강] Wilson의 정리. Fermat의 정리. Euler의 정리
|
1:
10:
42
|
|
|
윌슨 정리, 페르마 소정리, 오일러 정리 핵심 정리와 응용 요약
• 윌슨의 정리와 합성수 팩토리얼 합동: 소수 판정 동치조건 $(p-1)!\equiv-1\pmod p$과 합성수에서의 $(n-1)!\equiv0\pmod n$ 구조, 역원 짝짓기 논리 및 윌슨 정리 기반 나머지 계산·이론적 소수 판정 정리 • 페르마의 소정리와 카마이컬 수: 소수 및 서로소 조건에서 $a^{p-1}\equiv1\pmod p$, $a^p\equiv a\pmod p$ 두 형태와 완전 잉여계·이항정리 증명, 소수 판정 활용과 Fermat-pseudoprime·Carmichael 수에 따른 한계 정리 • 오일러의 φ함수·기약 잉여계·오일러 정리: φ함수 정의와 값 계산, 기약 잉여계 성질과 상수배 보존 정리, 일반 모듈러에서 $a^{\phi(m)}\equiv1\pmod m$ 구조를 이용한 큰 거듭제곱 나머지 계산·역원 $a^{\phi(m)-1}$ 구하기 및 중국인의 나머지 정리 결합 응용 |
||
|
[16강] Lagrange의 정리
|
0:
57:
51
|
|
|
라그랑주 정리와 다항 합동식의 해 구조 요약
• 라그랑주 정리 및 차수 내림 정리: 소수 p에서 n차 정계수 다항합동식의 해 개수 상한(n개)과 최대 해를 가질 때의 1차 인수 분해 구조, x^p−x로 나누는 차수 감소 기법과 p-1의 약수 차수 d에 대한 x^d−1≡0 (mod p)의 해 개수(d개) 정리 • 페르마 소정리 및 특수 다항식 구조: Fermat 소정리를 이용한 x^p−x, x^{p−1}−1의 해 전개와 인수분해 표현, x^p−a, 고차 다항합동식 예제 풀이, 합성수 법에서 라그랑주 정리 실패 사례와 해 개수 초과 현상 • 홀수 소수에서의 지수 구조와 따름정리: x^{(p−1)/2}≡±1 (mod p)의 해 개수((p−1)/2개)와 상호 배타성, x^{p−1}−1의 인수분해를 통한 해 분할, 제곱잉여·원시근 이론으로 이어지는 멱지수 구조 파악 |
||
|
[17강] 유사소수
|
0:
53:
58
|
|
|
유사소수와 Carmichael 수, 페르마·메르센 수의 관계 핵심 정리
• 유사소수·페르마·메르센 수: 페르마의 소정리를 바탕으로 밑 b 유사소수(b^n≡b (mod n)인 합성수) 정의, 합성인 Fermat 수 F_n=2^{2^n}+1·Mersenne 수 M_p=2^p−1가 밑 2 유사소수가 되는 조건과 구조 정리 • 밑 변환과 유사소수 무한 존재: 밑 변환 정리(밑 a,b ⇒ ab, n−a, 역원 ã에도 유사소수 성질 전이)와 n=(a^{2p}−1)/(a^2−1) 구성을 통해 임의의 밑 a>1에 대해 밑 a 유사소수가 무한히 존재함을 증명 • Carmichael 수와 Korselt 조건: 모든 서로소 밑 b에 대해 b^{n-1}≡1 (mod n)을 만족하는 Carmichael 수 정의, square-free 성질과 n=p_1···p_k에서 모든 소인수 p_i에 대해 (p_i−1)|(n−1)인 Korselt 판별 조건 및 561·1729·6601 등의 예 제시 |
||
|
[18강] Euler 파이함수. 약수의 합. 약수의 개수. Mobius 반전공식
|
1:
46:
56
|
|
|
정수론적 함수와 곱셈함수, 오일러 파이 함수와 약수함수, Möbius 반전공식
• 곱셈함수와 대표 정수론적 함수: 정수론적 함수·곱셈함수 정의와 소인수분해 표현, 오일러 파이 함수 φ·약수 개수 함수 τ·약수 합 함수 σ·Möbius 함수 μ의 곱셈함수 구조와 표준분해 공식 정리 • 오일러 파이 함수와 약수 관련 함수: φ(p^k), φ(n)=n∏(1−1/p) 일반 공식과 짝수성, τ(n), σ(n)의 소수 거듭제곱·표준분해 공식, 완전수 정의와 짝수 완전수–Mersenne 소수 2^{p-1}(2^p−1) 분류 정리 • Möbius 함수와 반전공식: Möbius 함수 μ의 정의·곱셈함수성·약수합 성질 Σ_{d|n}μ(d), Möbius 반전공식을 통한 약수합 형태 함수의 역복원 원리, φ·τ·σ 등 곱셈함수 및 약수합 연산의 “역방향” 구조 정리 |
||
|
[19강] Dirichlet 곱
|
1:
10:
10
|
|
|
Dirichlet 곱과 완전곱셈함수, Liouville 함수 핵심 정리 요약
• Dirichlet 곱과 역원 구조: Dirichlet 곱 정의·교환·결합법칙·항등원 함수 ι와 역원 존재 조건 f(1)≠0, 역원 점화식과 (f*g)⁻¹=f⁻¹*g⁻¹, 곱셈함수에서 곱셈성 보존 및 완전곱셈함수 역원 공식 f⁻¹(n)=μ(n)f(n) 정리 • 정수론적 함수와 Möbius 반전: 완전곱셈함수·곱셈함수 개념과 u_k, φ, τ, σ, μ의 Dirichlet 곱 표현(φ*u₀=u₁, τ=u₀*u₀, σ=u₁*u₀, μ*u₀=ι) 및 일반 Möbius 반전 F=f*g ⇒ f=F*g⁻¹ 구조, 곱셈함수의 곱과 역원의 곱셈성 정리 • Liouville 함수와 제곱수 판별: Liouville 함수 λ 정의와 완전곱셈성, 약수합 ∑_{d|n}λ(d)가 완전제곱수/비완전제곱수 판별 함수가 됨을 보이는 정리, λ의 Dirichlet 역원 λ⁻¹(n)=μ(n)λ(n)=μ(n)² 및 u₁⁻¹(n)=μ(n)n, φ⁻¹(n)=∑_{d|n}μ(d)d 등의 역원 표현 정리 |
||
|
[20강] 위수. 소수의 원시근
|
1:
01:
42
|
|
|
정수론 위수와 원시근 핵심 정리 요약
• 위수(order)와 거듭제곱 구조: 법 m에서의 위수 정의(최소 r, a^r≡1), 위수의 배수 조건(a^k≡1⇔r|k), φ(m)과의 약수 관계, 지수 합동(i≡j mod r ⇔ a^i≡a^j), 거듭제곱 위수 공식 ord_m a^k = ord_m a / (ord_m a, k) • 원시근(primitive root)과 단위군 구조: 원시근 정의(ord_m g = φ(m)), 존재 시 Z_m^*의 순환군 구조와 기약잉여계 생성, g^k의 위수 공식 및 원시근 판별[(k,φ(m))=1], 원시근 개수 φ(φ(m))과 법 7·8·Fermat 소수 등에서의 존재·부존재 조건 • 응용 계산 및 구조 분석: 위수 계산 절차(φ(m)의 약수 탐색)와 특정 위수 원소 찾기(예: 법 17, 19), Fermat 소수에서 2의 위수와 비-원시근 성질, Z_m 환과 단위군 Z_m^*의 군론적 의미 및 primitive root of unity와의 동치 구조 이해 |
||
|
[21강] 원시근의 존재성
|
1:
17:
02
|
|
|
원시근 존재 조건과 지수(index) 정리 핵심 요약
• 원시근 존재 조건: 법 m에서 원시근이 존재하는 경우는 m=2,4,p^k,2p^k(홀수 소수 p, k≥1)뿐이며, 합성곱 mn(m,n>2, (m,n)=1) 및 2^k(k≥3)에서는 위수와 φ(m) 비교로 원시근이 존재하지 않음을 증명 • 법 p^k·2p^k에서의 원시근 구조: 소수 p 및 p^k,2p^k에서 ord_m a | φ(m), ord_p a = p−1 조건과 귀납·이항정리를 이용해 모든 k에 대해 원시근이 존재함을 보이고, 이로부터 단위군 ℤ_m^×가 순환군이 되는 정확한 조건을 분류 • 지수(index, 이산로그)와 지수합동식: 원시근 g 존재 시 ind_g a를 정의하고 로그형 법칙 ind_g(ab), ind_g(a^n)을 이용해 x^n≡a (mod m)을 선형합동식 nX≡B (mod φ(m))으로 환원, a^{φ(m)/d}≡1 (mod m) (d=(n,φ(m)))을 해 존재의 필요충분조건 및 해 개수 d로 정리 |
||
|
[22강] 실수의 소수표현 (1)
|
0:
49:
27
|
|
|
실수의 비진법 소수표현, 유한소수·순환소수와 유리수의 관계
• 비진법 소수표현 원리: 임의의 양의 실수를 정수부분·소수부분으로 분해하고, 소수부분에 기수 b를 반복 곱해 얻은 자리수열로 무한급수 형태의 b진법 전개식으로 표현하는 방법 정리 • 유한소수·무한소수·순환소수 개념 및 유리수 대응: b진법에서의 유한소수·무한소수·순환소수 정의와 주기·순환마디 개념을 정립하고, 유한소수·순환소수가 항상 유리수이며 순환부를 등비급수로 표현해 분모가 b의 거듭제곱이나 b^r−1 꼴이 되는 구조 제시 • 유리수와 기수의 소인수 구조: 유리수가 b진법에서 유한소수로 표현될 필요충분조건을 분모와 기수 b의 소인수분해 일치성으로 제시하고, 다양한 진법(10진·2진·8진·6진 등)에서 분수를 소수로·소수를 분수로 변환하는 계산 절차와 예제를 통해 조건 검증 및 표현 변환 훈련 |
||
|
[23강] 실수의 소수표현 (2)
|
1:
12:
38
|
|
|
유리수의 b진법 순환소수 표현과 원시근, 예제 정리
• b진법 순환소수 구조: 유리수 c/q의 b진법 표현 조건(분모·밑의 서로소성), 위수 ord_q(b)와 순환마디 길이·자리수 구조, c·b^i에 따른 순환마디 회전과 1/q·1/p에서의 원시근·최대주기 분석 • 유리수의 b진법 분류: 분모 q와 밑 b의 소인수 관계(완전 포함·서로소·부분 포함)에 따른 유한소수·처음부터 순환소수·유한부분+순환부분 형태 분류, 모든 양의 유리수의 “유한 또는 순환소수” 표현 정리와 일반적 순환표현 가능성 • 유리수·무리수 판정과 예시: 비순환 무한소수 ⇔ 무리수 판정 기준, 1/7·1/13·1/77 등의 구체적 진법 표현 예제, 위수의 최소성·최소공배수 이용 주기 결정, 1 = 0.\overline{(b-1)}_b 등을 통한 유한소수 표현의 비유일성과 순환소수 표현 전환 원리 |
||
|
[24강] 보편지수(Universal Exponent)
|
0:
43:
44
|
|
|
보편지수와 최소보편지수, 카마이클 수의 구조 요약
• 보편지수·최소보편지수 λ(n): (a,n)=1인 모든 a에 대해 a^u≡1 (mod n)을 만족시키는 공통 지수와 그 최소값 λ(n) 정의, 소인수분해를 이용한 보편지수 계산 및 홀수 소수 거듭제곱·2의 거듭제곱에서의 λ(p^k), λ(2^k) 값과 일반 n에 대한 λ(n)=lcm(λ(2^{e0}),ϕ(p1^{e1}),…,ϕ(pm^{em})) 공식 정리 • 최소보편지수 계산과 예제: 법 2^k에서 λ(2^k)=2^{k-2} 증명 구조(모든 홀수 a에 대한 지수 2^{k-2}와 ord_{2^k}5=2^{k-2} 이용), n=600,180에 대해 소인수분해와 각 소인수 거듭제곱의 λ, ϕ 값을 통해 λ(n)을 최소공배수로 구하고, 중국인의 나머지 정리로 ord_n a=λ(n)을 갖는 a 구성 절차 제시 • 카마이클 수 구조와 λ(n)과의 관계: 합성수 n에 대해 (b,n)=1인 모든 b에 대해 b^{n-1}≡1 (mod n)을 만족시키는 카마이클 수 정의, n-1이 보편지수이므로 λ(n)| (n-1) 및 각 소인수 p_i에 대해 (p_i−1)|λ(n)| (n−1) 관계, n이 서로 다른 홀수 소수 p_1…p_k(k≥3)의 곱이며 제곱인수 없음과 소인수 두 개인 경우가 배제되는 구조적 조건 정리 |
||
|
[25강] 보편지수 (2)
|
0:
51:
12
|
|
|
보편지수와 ±1-지수, 전화 케이블 연결 문제 요약
• ±1-지수와 최대 ±1-지수 λ₀(m): 법 m에서 $(a,m)=1$일 때 $a^e≡±1\pmod m$을 만족하는 최소 e를 ±1-지수라 하고, 그 최대값 λ₀(m)은 원시근이 존재하면 $λ₀(m)=φ(m)/2=λ(m)/2$, 존재하지 않으면 $λ₀(m)=λ(m)$이 되도록 보편지수·위수·CRT를 이용해 소인수분해 경우별로 구성·증명함 • 전화 케이블 연결 규칙 S(j): m가닥 전선과 $(m,s)=1$인 s에 대해 $S(j)=1+(j-1)s\pmod m$으로 정의하면 S는 {1,…,m} 위의 순열이 되고, 합성 $S^n(j)=1+(j-1)s^n\pmod m$에 의해 n번째 케이블에서의 전선 위치와 전체 배열의 주기(원위치 복귀 조건 $s^n≡1\pmod m$)를 기술함 • 이웃 전선 재접촉 조건과 최적 선택: 이웃 전선 (j, j+1)이 n번째 케이블에서 다시 이웃이 되는 필요충분조건은 $S^n(j)-S^n(j+1)≡±1\pmod m \iff s^n≡±1\pmod m$이며, 따라서 s를 법 m에서 ±1-지수가 최대인 수(±1-지수 = λ₀(m))로 택해 이웃 전선이 다시 이웃이 되지 않는 구간을 최장으로 만들고, 이를 m=100, 25 등의 예에서 구체적으로 계산함 |
||
|
[26강] 이차잉여와 Legendre 기호. 이차합동식
|
1:
33:
18
|
|
|
이차잉여, Legendre 기호와 이차합동식 핵심 정리 요약
• 이차잉여·이차비잉여와 해의 구조: 법 m에서 제곱으로 표현되는 기약잉여/비잉여 정의, 홀수 소수 p에서 이차잉여·비잉여가 각각 (p−1)/2개인 구조, 원시근 지수와의 관계 및 x²≡a (법 p, pq) 해 개수·CRT 조합 원리 정리 • Legendre 기호와 Euler 기준·특수값: 홀수 소수 p에서 Legendre 기호 (a/p)의 정의, Euler의 표준 a^( (p−1)/2 )≡(a/p) (법 p), 합동 보존·곱셈성 등 기본 성질, 특수값 (−1/p), (2/p), 이차상호법칙을 이용한 (a/p) 계산 체계화 • 이차·일반 이차합동식 해법: x²≡a (법 p)에서 이차잉여 여부에 따른 해 존재·2개 구조, p≡3 (법 4)일 때 x≡±a^( (p+1)/4 ) 공식, ax²+bx+c≡0 (법 p)의 계수 정규화·완전제곱 변형으로 X²≡e (법 p) 환원 및 Legendre 기호를 통한 해 존재 판정·복원 방법 정리 |
||
|
[27강] 이차잉여의 상호법칙
|
1:
04:
23
|
|
|
Summary Content:
• Gauss Lemma와 Legendre 기호 표현: 집합 T와 기약잉여계 R,R′에서 음수에 합동인 원소 개수 n을 이용해 $(\frac{a}{p})=(-1)^n$으로 표현하고, 정수부분 합 $M$과의 관계로 $(\frac{a}{p})=(-1)^M$을 도출 • 이차잉여 판별 공식: $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$ 및 $p\bmod 8$에 따른 $(\frac{2}{p})$ 판별, $(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}$와 모듈러 4·8 조건을 이용한 이차잉여 여부 판별 구조 정리 • 이차잉여의 상호법칙: 서로 다른 홀수 소수 $p,q$에 대해 격자점 개수 세기를 사용해 $(\frac{p}{q})(\frac{q}{p}) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$을 증명하고, $p,q\bmod 4$에 따른 부호 조건으로 $(\frac{p}{q})$와 $(\frac{q}{p})$의 관계를 규명 |
||
|
[28강] Jacobi 기호
|
0:
46:
06
|
|
|
정수론 자코비 기호와 이차 잉여, 상호법칙 정리
• Legendre·Jacobi 기호와 이차 잉여: Legendre 기호를 이용한 이차 잉여 판정, 2·3·5·6의 이차 잉여 조건 분류, 4n+1 꼴 소수 무한 존재 증명 구조 정리 • Jacobi 기호 정의·성질: 합성수 모듈러로 확장된 Jacobi 기호의 정의, 곱셈·합동 보존 성질, 이차 잉여와의 논리 관계(값 1·-1 해석) 및 -1, 2에 대한 값 공식 정리 • Jacobi 상호법칙과 계산법: Jacobi 기호 상호법칙의 일반식과 증명 골격, 보조정리(지수 합동) 활용, 소인수분해 없이 Jacobi 기호로 Legendre 값을 계산하는 절차 및 응용 정리 |
||
|
[29강] 유한 연분수
|
0:
48:
49
|
|
|
유한 단순 연분수와 근사분수, 유리수 표현 정리
• 유한 연분수·유한 단순 연분수: 연분수 일반형과 표기법 정의, 정수항 조건을 갖는 유한 단순 연분수로 유리수 표현 구조 제시 • 유리수와 연분수 전개·수열 (p_k, q_k): Euclid 호제법을 이용한 모든 유리수의 유한 단순 연분수 전개, 점화식으로 정의된 p_k, q_k의 서로소성 및 p_k/q_k 표현 구조 정리 • 근사분수(convergent): [a_0;…;a_k]=p_k/q_k로 정의되는 k번째 근사분수 개념과 기약분수 성질, 원래 연분수 값에 점점 수렴하는 근사 구조 설명 |
||
|
[30강] 무한 연분수
|
1:
14:
51
|
|
|
무한 단순연분수, 수렴성, 무리수 표현과 예제(황금비, √2)
• 무한 단순연분수의 구조와 수렴성: 정수열로 정의되는 유한 연분수 수열의 극한으로 무한 단순연분수 값을 정의하고, 근사분수의 재귀식·단조성·유계성을 통해 항상 수렴함을 보임 • 근사분수의 오차 평가와 무리수성: 근사분수 p_k/q_k에 대해 |α−p_k/q_k|<1/(q_kq_{k+1})≤1/q_k²를 이용해 높은 정밀도의 유리근사 성질을 정리하고, 유리수 가정 시 모순을 통해 무한 단순연분수 값의 무리수성을 증명함 • 무리수의 연분수 전개와 대표 예제: 임의 무리수의 연분수 전개 알고리즘과 표현의 유일성을 정리하고, 황금비 [1;1,1,1,…]와 √2=[1;2,2,2,…]의 계수 패턴·근사분수·Fibonacci 수와의 연관성을 통해 구조적 특징을 제시함 |
||
|
[31강] 이차무리수와 순환연분수
|
1:
09:
43
|
|
|
이차무리수와 순환연분수의 동치성과 전개 방법 정리
• 이차무리수와 켤레·동치조건: 이차무리수 $\alpha = s + t\sqrt{d}$의 정의, 켤레 $\alpha' = s - t\sqrt{d}$, 그리고 $\dfrac{a+\sqrt{b}}{c}$ 꼴 표현·정수계수 이차방정식의 근과의 세 가지 동치 관계 정리 • 순환 단순연분수 개념과 이차무리수 동치성: 순환 단순연분수와 순수 순환연분수의 정의, 순환연분수 ⇒ 이차무리수, 이차무리수 ⇒ 순환 단순연분수(Lagrange 정리)를 통한 이차무리수와 순환연분수의 상호 동치 구조 제시 • Lagrange 전개 절차와 예제: $\alpha = \dfrac{P_0+\sqrt{d}}{Q_0}$에서 시작하는 점화식 $P_{k+1} = a_kQ_k - P_k$, $Q_{k+1} = \dfrac{d-P_{k+1}^2}{Q_k}$을 이용한 순환연분수 전개 알고리즘과 예제 $\dfrac{2+\sqrt{3}}{3} = [1;4,\overline{10,5}]$ 계산 과정 정리 |
||
|
[32강] 순수 순환연분수
|
1:
01:
29
|
|
|
순수 순환연분수와 이차무리수, √n의 연분수 전개 구조 요약
• 순수 순환연분수·이차무리수 대응 정리: 처음 항부터 주기가 반복되는 순수 순환연분수와 “이차무리수 ∧ α>1 ∧ 켤레 α'가 -1<α'<0” 조건의 동치, 근사분수 점화식 및 켤레 역수 변환 -1/α'가 계수열 역순 순환연분수 [\overline{a_n,…,a_0}]가 됨을 포함한 구조 정리 • √n 연분수 전개와 주기 대칭 구조: 비제곱 양의 정수 n에 대해 √n의 연분수 전개가 a₀ 뒤에서부터 순환하며 마지막 항 2a₀, 내부 계수 a₁,…,a_{r-1}가 팔린드롬 a_k = a_{r-k}을 이루는 형태 [a₀; \overline{a₁,…,a_{r-1},2a₀}]와 예시 √14 = [3; \overline{1,2,1,6}]의 일반화된 구조 정리 • 근사분수와 Pell형 방정식 연계: √n의 k번째 근사분수 p_k/q_k에 대해 p_k² - n q_k² = (-1)^{k+1}Q_{k+1} 관계를 이용해 Pell 방정식 x² - n y² = N의 해를 구성하는 방법과 연분수 전개·P_k,Q_k 점화식 기반 디오판토스 방정식 해 탐색 구조 정리 |
||
|
[33강] 무리수의 유리근사값
|
0:
38:
45
|
|
|
무리수의 유리 근사값과 연분수 근사분수의 성질
• 최상의 근사값 개념: 무리수 α에 대해 주어진 분모 이하의 모든 기약분수 중 |qα−p| 최소(또는 |α−p/q| 최소)를 만족하는 유리수 p/q를 최상의 근사값으로 정의하고, 분모 제한 하에서의 거리 최소 성질 정리 • 연분수 근사분수와 최상의 근사값: α의 연분수 전개에서 얻는 근사분수 c_k = p_k/q_k가 모두 α의 최상의 근사값이며, 반대로 임의의 최상의 근사값은 어떤 k에 대한 근사분수 c_k로 표현됨을 증명하고, π의 연분수 예시(22/7, 333/106, 355/113 등)가 각 분모 범위에서의 최상의 근사값이 됨을 설명 • 근사분수 판정 정리: 기약분수 a/b가 |α−a/b| < 1/(2b²)를 만족할 정도로 α에 매우 가깝다면 반드시 연분수 근사분수 p_k/q_k 중 하나가 됨을 보이는 정리로, 분모 제곱 역수 수준의 오차 조건을 이용해 가능한 유리 근사값·디오판틴 방정식 해 후보를 근사분수들로 한정하는 기준 제시 |
||
|
[34강] 피타고라스의 세 수. Fermat의 마지막 정리
|
1:
01:
37
|
|
|
피타고라스의 세 수와 n=4인 경우 페르마 마지막 정리 요약
• 피타고라스의 세 수 구조: 부정방정식 정의와 원시적 피타고라스 세 수의 성질, 곱이 제곱인 서로소 두 수의 구조, 원시적 피타고라스 세 수의 매개변수 표현 및 3·4·5에 대한 배수성 정리 • 곱이 제곱인 서로소 두 수 정리: rs=t²이고 (r,s)=1이면 r=m², s=n² 꼴로 표현됨을 소인수분해와 산술 기본 정리를 통해 증명하여 피타고라스 세 수 매개변수화 및 후속 정리에 활용 • n=4인 페르마 마지막 정리: 무한 강하법과 원시적 피타고라스 세 수 이론을 이용해 x⁴+y⁴=z²의 양의 정수해 부재를 증명하고, 이를 통해 x⁴+y⁴=z⁴의 양의 정수해도 존재하지 않음을 도출하며 정수해의 전체 형태를 제시 |
||
|
[35강] 제곱수의 합
|
1:
07:
36
|
|
|
두 제곱수와 네 제곱수의 합, 표현 가능 정수의 특징 정리
• 두 제곱수 합 표현 정수 조건: 소수 p의 두 제곱수 표현 성질(p=2 또는 p≡1 (mod 4))과 곱에 대한 닫힘성을 사용해, 일반 정수 n에서 p≡3 (mod 4) 소수의 지수가 모두 짝수일 때만 두 제곱수의 합으로 표현됨을 정리 • 두 제곱수·네 제곱수 합의 곱 닫힘성: (a²+b²)(c²+d²)와 네 제곱수 곱 공식으로, 두 제곱수·네 제곱수 합으로 표현되는 수들의 집합이 곱에 대해 닫혀 있음을 구조적으로 제시 • 네 제곱수 합 보편 표현 정리: 비둘기집 원리, 합동식, 최소성 논법을 이용해 모든 양의 정수가 네 제곱수의 합으로 표현됨을 증명하고, 소인수분해 및 곱 닫힘성과 연계해 전 범위 정수에 적용되는 표현 가능성 커리큘럼 구성 |
||
|
[36강] Pell의 방정식
|
1:
36:
04
|
|
|
Pell 방정식, 연분수와 기본해를 통한 해의 구조 정리
• Pell 방정식 구조 분류: $x^2-dy^2=N$에서 $d$의 부호·제곱수 여부에 따른 해의 존재성·개수 분류, $d\ge2$ 비제곱수일 때 무한해와 기본해 개념 정립 • 연분수와 근사분수 연계: $\sqrt d$의 순환단순연분수 전개·근사분수 점화식·$p_k^2-dq_k^2$ 공식으로 $|N|<\sqrt d$인 Pell 방정식 해를 근사분수와 일대일 대응 • $x^2-dy^2=\pm1$ 해 구조 및 생성: 주기 길이 짝·홀에 따른 $\pm1$ 방정식 해 존재성과 인덱스 분류를 정리하고, 기본해 $(x_1,y_1)$로부터 $(x_1+y_1\sqrt d)^n$ 꼴 거듭제곱으로 모든 정수해 생성 방법 제시 |
||
|
[37강] 기본적인 방법
|
0:
40:
33
|
|
|
소수 판정과 인수분해
• Trial division 소수 판정·소인수분해: 합성수의 소인수가 √n 이하에 존재함을 이용해 √n 이하 소수로 나눗셈 검사, 큰 수에서는 예비 인수 제거용으로 사용 • Fermat 인수분해: 홀수 n에 대해 n=ab 표현과 n=x²−y² 표현의 1:1 대응을 이용해 x²−n이 제곱수가 되도록 x≥⌈√n⌉을 증가시키며 찾고, 인수를 (x−y)(x+y)로 구성 • Euler 인수분해: 홀수 n이 n=a²+b²=c²+d² (서로 다른 두 표현)일 때 u=gcd(a−c,d−b), v=gcd(a+c,b+d), r=(a−c)/u, s=(d−b)/u를 정의하고 n=[(u/2)²+(v/2)²](r²+s²)로 인수분해하는 두 제곱수의 합 기반 기법 |
||
|
[38강] 인수분해 - Pollard Rho Method. Pollard p-1 Method
|
0:
36:
29
|
|
|
폴라드 rho, Pollard p-1를 이용한 큰 수 인수분해 개념 정리
• 인수분해 문제와 최대공약수 활용: 합성수 N의 비자명한 약수를 찾는 문제로 정식화하고, 임의 수열에서 얻은 차이와 N의 gcd 계산(Euclidean algorithm)을 통해 인수를 추출하는 구조 정리 • Pollard rho method: 단순 다항식 점화식으로 생성한 수열에서 약수 d에 대한 모듈러 주기성과 버스데이 패러독스를 이용해 반복적으로 g_k = gcd(x_{2k}−x_k, N)을 계산하여 중간 크기 인수를 찾는 확률적 알고리즘 • Pollard p-1 method: Fermat 소정리와 소인수 p에 대해 p−1이 작은 소수들로 이루어진 smooth 수라는 전제를 활용해 a^{k!}−1과 N의 gcd를 단계적으로 계산하여 비자명한 인수를 찾는 확률적 알고리즘 |
||
|
[39강] 소수판정 - 원시근과 위수 이용
|
1:
02:
11
|
|
|
루카스·포클링턴·Proth·페팽 소수 판정법 정리 요약
• Fermat·Lucas 계열 소수 판정법: Fermat 소정리와 위수(ord)·오일러 피 함수 φ(n)을 이용해 $n-1$의 모든(또는 지정된) 소인수 $q$에 대해 $a^{n-1}\equiv1$, $a^{(n-1)/q}\not\equiv1\pmod n$을 만족하는 밑을 구성하여 Lucas 단일·다중 밑 판정법과 그 변형으로 소수의 충분조건 제시 • Pepin·Proth 판정법: Fermat 수 $F_m=2^{2^m}+1$과 Proth 수 $n=k2^m+1$에 대해 $a^{(n-1)/2}\equiv-1\pmod n$ 형태의 조건을 사용해 $n-1$의 소인수가 사실상 2뿐이거나 $2^m$이 큰 경우에 특화된 빠른 소수 판정법을 제공하며, Pepin 판정은 Proth 판정의 특수한 경우로 해석 • Pocklington 계열 소수 판정법: $n-1=FR$, $(F,R)=1$, $F>R$ 구조에서 $F$의 소인수만 알고도 $a^{n-1}\equiv1\pmod n$ 및 각 $q\mid F$에 대해 $\gcd(a^{(n-1)/q}-1,n)=1$ (또는 다중 밑 버전)을 만족시키게 하여 모든 소인수가 $\sqrt n$보다 큼을 보이고, $n$의 합성 가능성을 배제함으로써 부분 소인수분해 기반 소수 판정을 수행 |
||
|
[40강] 소수판정 - 유사소수 이용(Miller-Rabin test)
|
0:
37:
05
|
|
|
밀러-라빈 소수 판정과 강한 유사소수 개념 정리
• Fermat 소정리·유사소수·카마이클 수: Fermat 소정리를 기반으로 합성수가 특정 밑에 대해 $b^{n-1}\equiv1\pmod n$을 만족하는 유사소수와 모든 서로소 밑에 대해 성립하는 카마이클 수 개념 정리 • Miller test·강한 유사소수: $n-1=2^s t$ 분해 후 $b^t\equiv1$ 또는 $b^{2^i t}\equiv-1\pmod n$ 조건으로 합성수 배제하는 Miller test 정의, 소수는 항상 통과함을 보이는 정리와 이를 통과하는 합성수를 강한 유사소수로 정의, 2에 관한 강한 유사소수의 무한 존재와 작은 밑 조합별 결정적 소수 판정 범위 제시 • Miller–Rabin 확률적 소수 판정: 합성수에 대해 Miller test를 통과하는 밑의 비율이 최대 1/4임을 이용해 서로 다른 k개의 밑에 대한 연속 통과 확률 상계 $(1/4)^k$를 주는 Rabin test 정리와, 이를 통한 고신뢰도 확률적 소수 판정 원리 및 합성수 오판 확률 계산 구조 정리 |
||
|
[41강] 소수판정 - Euler 유사소수 이용
|
1:
16:
17
|
|
|
오일러 유사소수와 Solovay–Strassen 소수 판정 요약
• 오일러 유사소수와 관련 개념: 오일러 표준, Jacobi 기호를 이용한 오일러 유사소수 정의와 성질, 유사소수·오일러 유사소수·강한 유사소수의 포함 관계 및 강한 유사소수 ⇒ 오일러 유사소수 정리와 역이 성립하지 않는 예시 정리 • Jacobi 기호와 밑의 존재, 오일러 유사소수 개수 상한: 제곱수가 아닌 홀수에 대해 Jacobi 기호가 -1인 밑의 존재 정리, Carmichael 수와의 연관, 합성수 n에 대해 오일러 유사소수가 되는 밑의 개수가 최대 (1/2)φ(n)임을 보이는 구조 및 확률적 해석 정리 • Solovay–Strassen 소수 판정법: Euler 표준과 Jacobi 기호를 이용한 확률적 소수 판정 알고리즘 절차, 소수·합성수일 때의 판정 특성, 한 번 테스트의 실패 확률 상한과 k회 반복 시 오판 확률 2^{-k}로 감소하는 원리 정리 |
||
|
[42강] 인수분해 - 연분수 이용
|
0:
26:
46
|
|
|
연분수 이용 정수의 인수분해 알고리즘 핵심 정리
• Fermat 인수분해 일반화: $x^2 - y^2 = n$ 또는 $x^2 \equiv y^2 \pmod n$ 관계를 이용해 $(x-y)(x+y)$에서 $\gcd(n, x-y)$, $\gcd(n, x+y)$로 비자명한 약수 도출 • √n의 연분수·근사분수 구조: $\sqrt{n}=[a_0;\overline{a_1,\dots,a_l}]$의 주기성과 $\alpha_k=\dfrac{P_k+\sqrt n}{Q_k}$, 근사분수 $c_k=p_k/q_k$의 점화식, 그리고 핵심 등식 $p_k^2 - n q_k^2 = (-1)^{k+1} Q_{k+1}$을 통한 $p_k^2 \equiv Q_{k+1} \pmod n$ 관계 정립 • 연분수 기반 인수분해 알고리즘: √n의 연분수를 전개하며 $P_k,Q_k,a_k,p_k,q_k$를 계산하고 짝수 인덱스에서 $Q_{k+1}=s^2$인 경우 $p_k^2 \equiv s^2 \pmod n$을 이용해 gcd로 약수를 찾는 절차와, $p_k \equiv \pm s \pmod n$일 때 실패·다른 k 탐색 전략을 포함한 알고리즘 설계 및 예제(1037, 1,000,099) 적용 |
||
|
[43강] RSA 암호 체계와 Rabin 암호 체계
|
0:
52:
36
|
|
|
RSA 암호 체계와 Rabin 암호 체계의 구조와 정수론적 원리 요약
• 공개 열쇠 암호체계 구조: 비밀 열쇠/공개 열쇠 개념, 모듈러 연산 기반 암·복호, 인수분해 난이도에 의존한 안전성 비교 • RSA 암호 체계: $n=pq$, $\varphi(n)$, 공개키 $(e,n)$·개인키 $d$ 생성, $C\equiv P^e\pmod n$, $P\equiv C^d\pmod n$ 구조와 Euler 정리·Fermat 정리·중국인의 나머지 정리에 따른 정당성 및 단사 매핑 • Rabin 암호 체계: $p\equiv q\equiv 3\pmod 4$, $n=pq$, 공개키 $(b,n)$·개인키 $(p,q)$, $C\equiv P(P+b)\pmod n$의 4대1 매핑, $t^2\equiv1\pmod n$·이차합동 공식·CRT를 이용한 복호 알고리즘 구조 |
||
|
[44강] ElGamal 암호체계 및 전자서명
|
0:
38:
55
|
|
|
엘가말 암호체계, Diffie-Hellman 열쇠교환, ElGamal·RSA 전자서명 핵심 정리
• ElGamal·Diffie-Hellman 구조: 소수 p와 원시근 g, 이산로그 문제 난해성을 기반으로 한 공개키 암호(ElGamal)와 공유 비밀키 합의 프로토콜(Diffie-Hellman)의 설정·암호화·복호화·공유키 생성 절차 정리 • ElGamal 전자서명: ElGamal 설정, k와 p−1의 서로소 조건, 서명값 (c,s) 생성식 s ≡ (P−ac)k⁻¹ (mod p−1)과 검증식 c^s b^c ≡ g^P (mod p) 유도 및 서명 정당성 구조 정리 • RSA 전자서명: n=pq, φ(n)=(p−1)(q−1), ed≡1 (mod φ(n))을 이용한 키 생성, 서명 s≡P^d (mod n)와 검증 s^e≡P (mod n) 구조 및 소인수분해 난이도 기반 보안성 정리 |
||
|
[45강] 비밀분산
|
0:
46:
50
|
|
|
비밀분산과 중국인의 나머지 정리, Shamir 비밀배분법 핵심 정리
• (t,n)-비밀분산법 개념: 임계값 t 이상 참여 시에만 비밀키를 복원하고 t−1 이하에서는 법 p에서 균일 분포 수준의 정보만 제공하는 threshold 구조의 비밀 공유 방식 • CRT 기반 비밀분산: 서로 소 정수열 {m_i}와 곱 M, 부등식 M > p·(큰 쪽 t−1개 곱) 조건 및 K_0=K+sp 구성으로 t명일 때는 중국인의 나머지 정리로 K 복원, t−1명일 때는 후보가 법 p에서 거의 균일하여 최대 1/p 수준의 노출만 허용하는 구조 • Shamir 비밀배분법: 소수 p 위에서 비밀키를 상수항으로 갖는 차수 t−1 다항식을 정의하고 각 참여자에게 점 (x_i,f(x_i))를 배분하여, Lagrange 보간·Vandermonde 행렬 유일성을 통해 t명 이상에서만 다항식과 상수항 K를 결정 가능하게 하고 t−1명 이하에서는 K가 0,…,p−1 전체에 걸쳐 동일한 가능성을 갖도록 설계한 정보이론적 완전 보안 방식 |
||
|
[46강] 영지식 증명
|
1:
16:
53
|
|
|
동전 던지기와 영지식 증명, 제곱근·신원확인·정보증명 요약
• 전자적 동전 던지기·수 이론 도구: 합성수 n=pq에서 제곱근 4개 구조, 이차잉여·Legendre symbol·중국인의 나머지 정리·gcd를 이용한 인수분해 가능/불가능 분류로 공정 확률 1/2 동전 던지기 구현 • 영지식 증명 프로토콜군: Prover/Verifier 상호작용, “소인수분해 가능성”을 노출 없이 입증하는 제곱근 기반 영지식 증명과 Fiat–Shamir 유형 신원 확인(공개값 n,v, 비밀 u, 도전 비트와 r,s 응답 구조) 설계 • 다수 정보 보유 영지식 증명: 여러 비밀 v_j에 대해 역원의 제곱 s_j 공개, r^2=x, y=r∏v_j, 검증식 x≡y²z(mod n) 구조로 구체 값 노출 없이 지식 보유 증명, 부분집합 도전으로 속임수 성공 확률을 2^{-mk}로 지수 감소시키는 보안 구조 정리 |
||
이석민 교수님
정수론
;)
|
|
| 오늘 팝업 보이지 않기 | 닫기 |
