정수론

정수론은 이름 그대로 정수의 성질과 관계에 대한 연구로, 수학이라는 것이 태동할 때부터 역사를 써내려온 유서 깊은 분야다. 가우스는 정수론에 대해 다음과 같은 말을 남겼다.

“수학은 과학의 여왕이고, 수론은 수학의 여왕이다.”

초등 정수론

초등^Elemantary은 해석적 정수론, 대수적 정수론과 대비되는 표현으로써, 그러한 툴을 사용하지 않는 것일 뿐 초등학생 수준으로 쉽다는 뜻은 아니다. 물론 명제를 읽는 것 자체는 가장 학식이 필요 없기 때문에 ‘일단은’ 쉽다고 할 수도 있겠다. 수학에 흥미가 많은 영재들은 어릴때부터 이러한 정수론을 접한다.

배수와 약수

• 최대공약수와 서로소 $\gcd$
  • 짝수의 정의
• 몫과 나머지
  • 유클리드 호제법
• 확장된 유클리드 정리
• 3의 배수판정법과 9의 배수판정법
• 7의 배수판정법과 13의 배수판정법
• 11의 배수판정법

소수

• 소수와 합성수
  • 1만번째까지의 소수 목록
  • 소수 분해 원리
  • 산술의 기본정리
  • 유클리드의 증명: 소수는 무한히 존재한다
  • 오일러의 증명: 소수는 무한히 존재한다
• 메르센 소수
• 스무스 소수
• 준소수

모듈러 연산

• 정수론에서의 합동
• 합동방정식에 대한 대수학의 기본정리
• 페르마의 소정리
  • 카마이클 수
  • 코셀트 판정법
  • 밀러-라빈 판정법
• 윌슨의 정리
• 중국인의 나머지 정리
• 연속제곱법
• 정수론에서의 위수
  • 원시근 정리
  • $p$-진수
  • 지수승강 보조정리

완전수

• 토션트 함수 $\phi$
  • 토션트 함수의 곱셈적 성질
  • 오일러의 토션트 정리
  • 오일러의 토션트 합 공식
• 합동방정식의 거듭제곱근
• 정수론에서의 시그마 함수 $\sigma$
• 유클리드의 완전수 공식
• 오일러의 완전수 정리

이차상호 법칙

• 이차잉여와 비이차잉여 QR, NR
• 르장드르 기호의 곱셈적 성질
• 오일러 판정법
• 가우스의 이차상호 법칙
• 소수를 4로 나눈 나머지가 1이 되는 필요충분조건
• 소수를 3으로 나눈 나머지가 1이 되는 필요충분조건

타원곡선

• 피타고라스 트리플
  • 피타고리스 수 중 하나는 반드시 짝수여야한다
  • 피타고리스 수 중 하나는 반드시 3의 배수여야한다
  • 원시 피타고라스 트리플은 두 홀수만으로 표현할 수 있다
  • 원시 피타고라스 수끼리는 서로소다
• 펠 방정식

암호론

초기 암호론은 대표적인 정수론의 응용이었다. 수천년동안 순수수학이었던 정수론은 암호에 대한 응용을 통해 실용적인 학문으로 탈바꿈하게 되었으며, 최근에는 추상대수학이 응용되고 있다.

• 암호화와 복호화

이산로그

• 이산로그
• 디피-헬만 키 교환 알고리즘
• 엘가말 공개 키 암호체계
• 샹크스 알고리즘
• 폴리그-헬맨 알고리즘
• 이산로그 문제가 쉽게 풀리는 조건

소인수분해

• 소인수분해
• RSA 공개 키 암호체계
• 골드바서-미칼리 확률 키 암호체계
• 폴라드 $p-1$ 소인수분해 알고리즘
• 준소수의 소인수분해 문제가 쉽게 풀리는 조건

대수적 정수론

확장환

• 가우스 정수 $\mathbb{Z} [i]$
• 가우시안 링의 놈
• 가우스 소수 정리
• 아이젠슈타인 정수 $\mathbb{Z} [\omega]$
• 아이젠슈타인 링의 놈
• 아이젠슈타인 소수 정리

해석적 정수론

산술함수

• 산술 함수 $f$
  • 뫼비우스 함수 $\mu$
  • 오일러 토션트 함수 $\varphi$
  • 놈 $N$
  • 유닛 함수 $u$
  • 망골트 함수 $\Lambda$
  • 리우빌 함수 $\lambda$
  • 디바이저 함수 $\sigma_{\alpha}$
• 산술 함수의 승법적 성질
• 산술 함수의 디리클레 곱 $\ast$
  • 디리클레 곱에 대한 아이덴터티 $I$
  • 디리클레 곱에 대한 인버스 $f^{-1}$
  • 디리클레 곱과 승법적 성질
  • 산술 함수의 아벨리안 그룹 $\left( A, \ast \right)$
  • 승법적 함수의 아벨리안 그룹 $\left( M, \ast \right)$
• 뫼비우스 역 공식
• 벨 급수 $f_{p}(x)$
• 산술 함수의 미분 $f '$
• 셀버그 항등식
• 일반화된 디리클레 곱 $\circ$
  • 산술 함수의 부분합에 대한 일반화된 디리클레 곱 표현

주요 참고문헌

• Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition)
• Apostol. (1976). Introduction to Analytic Number Theory
• Hoffstein. (2008). An Introduction to Mathematical Cryptography