세연이 공부방수학 과목 ▾

개념지도 / 대학 맛보기 / 이산수학·컴퓨터

정수론과 암호(RSA)

number theory and RSA cryptography 대학 앞으로

나머지 연산(시계 산술). 큰 수 소인수분해가 어렵다는 것이 인터넷 보안

한 문장 직관 — 이것만 남으면 성공

정수론은 "가장 순수해서 쓸모없다"고 여겨졌지만, 지금 인터넷 보안 전체가 그 위에 서 있다.

소수 찾기 — 배수를 지우면 남는 것소수가 인터넷 보안의 기반이다.
1~100123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100아직 아무것도 안 지웠다

2의 배수, 3의 배수… 차례로 지우면 더 이상 쪼개지지 않는 수만 남는다.

왜 중요한가

초등 소수가 은행 보안이 되는 놀라움

예시

시계: 9+5=2 (mod 12). 두 소수 곱은 쉽고, 되돌리기는 어려움

백지에 해볼 것 A4 한 장

시계 산술 표 만들기. 작은 RSA(p=3,q=11)로 메시지 암호화·복호화 손계산

핵심 식

페르마의 소정리 — RSA의 뼈대

확인 질문 — 답하면 통과

발견의 순서 — 왜 이게 필요했나

수학자 하디는 1940년에 "정수론은 어떤 실용적 목적에도 쓰이지 않는다"고 자랑스럽게 썼다. 30년 뒤 RSA 암호가 나왔다.

어디에 쓰이나

  • RSA 암호
  • 비트코인
  • 전자서명
  • 오류정정부호

다음으로 어떻게 이어지는가

순수수학이 언제 응용될지 아무도 모른다는 대표 사례.

먼저 알아야 할 것 약수·배수·소수(prime)소인수분해알고리즘과 계산 복잡도