본문 바로가기

수학/정수론

정수론 (8) - RSA 암호 저번에 오일러 공식에 대해 알아보았습니다. 이번에는 오일러 공식의 가장 유용한 응용인 RSA 암호에 대해서 알아보도록 하겠습니다. RSA 암호의 개요 다음과 같은 시나리오를 생각해봅시다. 두 명의 사람 A, B가 있습니다. A는 B에게 보석을 배달받아야 합니다. 그런데 A, B 사이에는 보석을 노리는 사람들이 너무 많습니다. 어떻게 하면 중간에 보석을 뺏길 일 없이 안전하게 배달을 완료할 수 있을까요? 한 가지 훌륭한 방법은 다음과 같습니다 먼저 A는 집에 있는 자물쇠와 상자를 B에게 보냅니다. (A는 자물쇠의 열쇠도 가지고 있습니다) B는 보석을 상자 안에 넣고 자물쇠로 잠군 뒤, A에게 보냅니다. A는 자물쇠를 풀고 보석을 얻습니다. 이 방식은, 자물쇠는 누구나 잠굴 수 있으나 푸는 것은 열쇠가 있는.. 더보기
정수론 (7) - 확장 유클리드 알고리즘 RSA 암호 얘기로 넘어가기 전에 한 가지 더 알아야 할 것이 있습니다. 바로 확장 유클리드 알고리즘입니다. 확장 유클리드 알고리즘 정수론 (2) - 베주 항등식 에서 베주 항등식에 대해서 알아봤습니다. 베주 항등식의 내용은 다음과 같았습니다. $a, b$에 대하여 $ax + by = \text{gcd}(a, b)$를 만족하는 정수 $x, y$가 존재한다. 그런데 베주 항등식은 이러한 $x, y$의 존재성에 대해서만 얘기하고 실제로 $x, y$를 어떻게 구하는지에 대해서는 언급하지 않습니다. 하지만 확장 유클리드 알고리즘을 활용하면 구할 수 있습니다. 사실 확장 유클리드 알고리즘은 유클리드 알고리즘을 거꾸로 하면 됩니다. 단계는 아래와 같습니다. 먼저 유클리드 호제법을 통해 $a, b$의 최대공약수를 구.. 더보기
정수론 (6) - 오일러의 정리와 오일러 파이 함수 저번에는 페르마 소정리에 대해서 알아보았습니다. $$ a^{p-1} \equiv 1 \mod p \quad \text{(단, $a$와 $p$는 서로소)} $$ 이번엔 페르마 소정리의 일반화 버전인 오일러 정리를 보도록 하겠습니다. 오일러 정리는 아래와 같습니다. $$ a^{\varphi(n)} \equiv 1 \mod n \quad \text{(단, $a$와 $n$은 서로소)} $$ 여기서 $\varphi(n)$ 은 오일러 파이 함수 (Euler Phi Function) 으로 불리는 함수로, 1부터 $n$ 까지 $n$ 과 서로소인 수들의 개수입니다. 예를 들어서 $\varphi (10)$ 을 구하면, 10과 서로소인 수는 1, 3, 7, 9이므로, $\varphi(10) = 4$ 입니다. 눈치 좋은 분들.. 더보기
정수론 (5) - 페르마의 소정리 저번에 합동식에서 나눗셈을 하기 위한 조건에 대해서 알아보았습니다. 이 내용을 바탕으로 정수론에서 매우 중요하게 다뤄지는 정리인 페르마 소정리에 대해서 알아보겠습니다. 페르마 소정리는 아래와 같습니다. (단, $p$는 소수, $a$는 $p$의 배수가 아닌 정수) $$ a^{p-1} \equiv 1 \mod p $$ 예를 들어서 $p = 7, a = 12$ 라고 하면, $$ 12^{7-1} = 12^{6} = 2985984 \equiv 1 \mod 7 $$ 이 됩니다. 암호학의 핵심이 되는 정리라고 할 수 있죠. 이 정리가 어떻게 응용될 수 있는지는 나중에 더 보기로 하고, 이번 글에서는 이 정리의 증명에 집중하겠습니다. 페르마 소정리의 증명 다음과 같은 크기 $p-1$의 집합을 살펴보겠습니다. (단, $.. 더보기
정수론 (4) - 합동식에서의 나눗셈 저번에 우리는 합동식의 나눗셈에 대해 살펴보던 중 어떨 때는 합동식의 양변을 나누는 것이 안되고 어떨 때는 된다는 것을 관찰했습니다. 아래의 합동식은 안되는 예시이며, $$ \begin{align} 15 \equiv 27 &\mod 12 \\ 5 \equiv 9 &\mod 12 \end{align} $$ 아래는 되는 예시입니다. $$ \begin{align} 24 &\equiv 66 \mod 7 \\ 12 &\equiv 33 \mod 7 \\ 8 &\equiv 22 \mod 7 \\ 4 &\equiv 11 \mod 7 \end{align} $$ 이제부터 언제 합동식의 양변을 나눌 수 있는지 알아보고자 합니다. 항등원과 역원 얘기를 시작하기 전에 두 가지 용어를 알아야 합니다. 먼저 항등원이란, 임의의 원.. 더보기
정수론 (3) - 합동식 드디어 정수론의 꽃이라고 볼 수 있는 합동식에 대해 알아볼 때가 되었습니다. 보통 합동 하면, 도형의 합동을 생각하는데요, 정수론에서도 합동이라는 개념이 있습니다. 먼저, 도형의 합동을 다시 한변 살펴보고, 정수론의 합동에 대해서 얘기해 보겠습니다. 기하학에서의 합동 기하학에서 합동이란, 두 도형의 모양과 크기가 같음을 나타내는 관계입니다. 때문에 합동인 두 도형은 _정확히 똑같다_고 흔히들 생각합니다. 하지만 실제로 두 도형이 정확히 똑같지는 않습니다. 예를 들어 아래 그림을 볼까요? 이 두 도형은 합동입니다. 모양과 크기가 모두 같지만 한 가지 중요한 차이점이 있습니다. 바로 두 도형의 위치와 회전이 다르다는 점입니다. 뭐 사소한 것 가지고 그러겠냐고 그럴 수 있지만 사실 이는 매우 큰 차이입니다. .. 더보기
정수론 (2) - 베주 항등식 저번에 최대공약수, 최소공배수, 그리고 유클리드 호제법에 대해 알아보았습니다. 저번 시간에 배운 내용을 바탕으로 이번에는 정수론의 가장 중요한 정리 중 하나인 베주 항등식에 대해 알아보겠습니다. 별 그리기 다음과 같이 12개의 점이 원형으로 찍혀 있습니다. 여기서 0부터 시작해 두 칸씩 건너 뛰어서 점을 이어보도록 하겠습니다. 위와 같은 육각형이 나오네요! 이 도형은 열 칸씩 건너 뛰어도 나옵니다. 한편 세 칸씩, 또는 아홉 칸씩 건너 뛰면 각각 아래와 같은 도형이 그려집니다. 한 칸, 다섯 칸, 일곱 칸, 또는 열한 칸씩 건너 뛰면 아래와 같은 도형이 나옵니다. 아래 표는 $a$칸씩 건너 뛰었을 때 나오는 도형을 정리한 표입니다. $a$칸 건너뛰었을 때 도달하는 점의 위치 1, 5, 7, 11 0, 1.. 더보기
정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법 안녕하세요, Dimen입니다! 오늘부터 정수론에 대한 글을 써보고자 합니다. 정수론은 정규 수학 교육과정에서 잘 다루지 않기 때문에 많은 분들에게 생소한 분야입니다. 그런 만큼 많은 분들에게 도움이 될 것 같기 때문에 한 번 써보겠습니다. 정수론이란? 정수론은 말 그래도 정수를 다르는 학문입니다. 구체적으로 다른 수(유리수, 실수, 복소수)들은 가지지 않는, 정수의 독특한 특징인 약수와 배수, 몫과 나머지에 대해 탐구하는 학문입니다. 물론 고등정수론에서는 훨씬 더 깊은 정수론(여러분도 들어보셨을법한 리만 가설도 정수론의 영역입니다)도 다루지만, 이 시리즈에서는 기초정수론만 다루겠습니다. 그러면 정수론은 왜 필요할까요? 사실 19세기까지만 해도 정수론은 좋게 말해 순수학문, 나쁘게 말해 쓸모없는 학문으로 .. 더보기

티스토리툴바