기계 번역 안내
이 글의 일부 내용은 DeepSeek 의 도움을 받아 번역되었습니다. 번역문에는 부정확한 부분이 있을 수 있으며, 언어와 문화적 배경의 차이로 인해 일부 고유한 용어나 문화적 맥락을 이해하기 어려울 수 있습니다. 정확한 표현을 확인하려면 원문을 읽어 주세요. 문화적 배경이나 내용에 궁금한 점이 있다면 사이드바의 연락 방법을 통해 문의해 주세요. 설명해 드리겠습니다.
숫자 맞히기 게임
셋이 동행하면 칠십이 드물고, 오(五)나무 매화에는 스물한 가지, 일곱 아들이 단결하면 정확히 보름, 백다섯을 빼면 바로 알 수 있다.
——— (명나라) 정대위(程大位) 《산법통종》
내가 처음 “중국인의 나머지 정리“에 흥미를 느낀 것은, 이 이름이 수많은 정리들 중에서도 유독 독특했기 때문이다. 그 해법인 “진구소 대연 구일술” 또한 매우 우아하고 중학생의 무한한 상상력을 불러일으키는 신성한 이름이다. 이 신성한 것은 남북조 시대의 《손자산경》에 나오는데, 춘추 시대 오나라에서 병사를 이끌던 손자가 아니라 남북조 시대의 수학자 손 선생님이다. “닭과 토끼가 같은 우리에 있다"는 문제도 이 책에서 나왔다.
요즘 우리는 방과 후나 퇴근 후에 추리 퍼즐이나 방탈출 게임을 즐기지만, 옛날 사람들은 손 선생님의 산경(算經)을 한 권 사서, 매일 농사일을 마치거나 전쟁을 치르고(살아서 돌아올 수 있다면) 집에 돌아와 책을 펼쳐 토끼가 몇 마리인지, 군대가 몇 명인지 계산하곤 했다. 현대인이 기묘한 구결로 요점을 외우듯, 시작 시에 나오는 이 시는 명나라의 수수께끼 고수가 손 선생님의 이 게임을 익힌 후 정리한 구결이니, 이제 우리도 한번 해보자.
만약 당신이 시간 여행을 해서 남북조 시대로 갔는데, 장교에게 간첩으로 오해받아 붙잡혔다고 치자. 장교가 말하길, 만약 당신이 병영 안에 몇 명이 있는지 알면 한족(漢族)임을 증명하는 것이니 풀어주고, 그렇지 않으면 오랑캐가 보낸 세작(細作)이라고 말한다. 하지만 당신은 오직 세 가지만 볼 수 있다.
- 호위병을 세 줄로 세우면 두 명이 남는다;
- 다섯 줄로 세우면 세 명이 남는다;
- 일곱 줄로 세우면 다시 두 명이 남는다.
당신은 어떻게 추측할 것인가?
대부분 사람의 첫 반응은 아마 이럴 것이다: 하나하나 시험해보자. 13을 시험해보고, 아니면 17, 아니면 19…… 계속 시험해서 세 조건을 동시에 만족하는 수를 찾는다.
물론 그렇게 해도 되지만, 그건 불가능에 가깝다. 세 번 시험하고 머리가 날아갈지도 모른다. 그것보다도 이 조건들을 만족하는 해가 무수히 많다면 어떡하겠는가. 세상에는 3으로 나누어 나머지가 2인 수가 무수히 많고, 또 5로 나누어 나머지가 3인 수도 무수히 많다……
이 문제는 애당초 당신을 괴롭히려고 나온 것이다. 하지만 당신의 머릿속 연산을 거쳐 보면, 조건들이 산만해 보여 해가 하나가 아닐 것 같지만, 결국에는 정확히 하나의 정수로 귀결된다. 하나의 덩어리도 아니고, 어렴풋한 구간도 아니고, 분명한 하나의 수로 말이다.
정말로 시험해보자.
1부터 찾기 시작하여, “3으로 나누어 나머지가 2"인 수는 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32……
이 수들 중에서 “5로 나누어 나머지가 3"인 것은 8, 23, 38……
그중에서 “7로 나누어 나머지가 2"인 수: 23.
바로 23이다.
（저작자：Cmglee，위키미디어 공용，CC BY-SA 4.0）
이 답에는 기쁜 불확실함이 있다. 마침내 찾았지만, 더 이상 뒤에 없다는 걸 어떻게 아는가.
하나하나 시험하지 마라
우리는 정수를 “하나 다음 하나"의 것으로 보는 데 너무 익숙해져 있기 때문이다.
1, 2, 3, 4, 5…… 마치 계단을 한 계단씩 올라가는 것과 같다. 그래서 “3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는다"라는 조건을 만나면, 직감도 말할 것이다: 그럼 처음부터 전수 조사해보자.
하지만 이 방법의 문제는 분명하다: 계단이 너무 길다.
당신이 요구하는 것은 여러 조건을 동시에 만족하는 수이지, 어느 한 조건이 아니다. 조건이 많아지면, 직접 시험하는 것은 매우 소박하지만 몹시 힘든 노동이 된다. 특히 숫자가 커지면, 이 노동은 즉시 체면을 잃게 만든다. 당신이 100개의 수를 시험해도 정답의 변두리조차 건드리지 못할 수도 있다. 수를 시험하는 이 일은 애초부터 “전체 탐색"의 냄새를 지닌다. 그것은 당신이 긴 선 안에서 목표를 찾으리라고 기본적으로 가정한다.
이 일은 날짜를 계산하는 것과 매우 닮았다.
오늘이 금요일이라면, 1일 후는 토요일, 2일 후는 일요일, 100일 후는 무슨 요일일까? 뒤로 밀어라, 백 일이나 뒤로 밀어라, 하루하루 세어라, 틀리면 다시 처음부터 세어라.
나머지는 그 옆에서 슬프게 당신을 쳐다보고 있다.
나머지는 당신이 100일 후가 무슨 요일인지 아는 데 도움을 줄 수 없지만, 이 정수가 어떤 순환 체계 속의 어떤 위치에 있는지 알려줄 수는 있다.
나머지는 어떻게 우리를 돕는가?
나는 모듈러 연산이라는 개념을 무척 좋아한다. 어떤 수를 다른 수로 나눈 뒤 나머지를 취하는 것. 그것은 아주 일상적인 기품을 지니고 있다.
아까의 요일 문제로 돌아가자.
오늘이 금요일이면, 7일 후도 금요일, 14일 후도 금요일, 15일 후면 하루가 남으니, 뒤로 하루 밀면 토요일이다. 20일 후, 삼칠이십일이니 하루 모자라면 앞으로 하루 당기면 목요일이다. 100일은, 14번 온전하게 지나고 2가 남으니 일요일이다. 그래서 요일이라는 시스템은 본질적으로 순환이다. 당신은 며칠이 지났는지 알 필요가 없고, 오직 “7로 나눈 나머지"만 알면 충분하다.
또 시계를 예로 들어보자.
지금이 3시라면, 12시간 후도 3시다. 시계는 무한히 뻗는 직선이 아니라 하나의 원이다. 시간은 그 위를 걸으며, 마침내는 다시 원점으로 돌아온다. 시간을 알고 싶다면, 시계를 한 번 보라. 나는 믿는다. 정상적인 인간이라면 누구도 첫눈에 12를 보고는 그 다음부터 한 시간씩 세어 올라가며 지금이 몇 시인지 판단하지는 않을 것이다. 오히려 단번에 바늘이 지금 시계판의 어느 위치를 가리키는지 포착할 것이다. 시계판에 숫자가 적혀 있지 않아도 그렇다.
달력도 마찬가지다. 한 달은 30일, 31일, 28일, 심지어 윤년까지. 당신은 시간이 앞으로 나아간다고 생각하지만, 사실 그것은 계속 어떤 패턴을 데리고 반복해서 나타난다.
수학은 이 사실을 추상화하여 “모드(mod)“라고 부른다. 하나의 “모드"는 하나의 순환이다. 예를 들어 “7로 나눈 나머지를 취한다"는 것을 우리는 “mod 7 ( $mod$ $7$ )“이라고 부르며, 이것은 요일의 세계에서 말하는 것이다; “12로 나눈 나머지를 취한다"는 것은 시계의 세계에서 말하는 것이다. 하루가 24시간이므로, 다음 날 새벽 1시는 우리 같은 밤샘족에게 오늘의 25시나 다름없다. 실제로 “25시 ≡ 1시 (mod 24)“이다.
그러므로, 하나의 수는 더 이상 그 자체만이 아니다. 그것은 다른 모드 안에서 다른 측면을 드러낸다.
이것은 마치 한 사람과 매우 닮았다.
집에서, 학교에서, 친구들 앞에서, 사랑하는 사람 앞에서, 보여주는 모습이 전부 완전히 같지는 않다. 단 한 번의 스냅숏만으로는 당신이 그 사람을 정확히 알지 못할 수도 있다. 하지만 만약 당신이 많은 측면을 보았다면, 진실에 더 가까워질 것이다.
어떤 정수가 mod 3에서는 어떤 모습이고, mod 5에서는 어떤 모습이며, mod 7에서는 어떤 모습인지, 이 “나머지들"이 그 정수를 고정시켜 준다.
여기서 정수론을 도입하다
가우스가 말했다:
수학은 과학의 여왕이며, 정수론은 수학의 여왕이다.
정수론은 사실 정수를 연구하는 학문이다.
정수라는 이 세계는 겉보기에는 조용하고, 심지어 소박해 보이지만, 그 내부의 질서는 믿을 수 없을 정도로 깊다. 많은 현대 수학, 현대 컴퓨터 과학, 현대 암호학은 마지막에 정수로, 나머지로, 나눗셈의 잔영으로 돌아가야 한다. 아주 신기하다.
모듈러 연산은 정수론에서 가장 중요한 도구 중 하나이다. 미적분학에는 도함수가 있고, 선형대수학에는 행렬이 있으며, 기하학에는 좌표가 있다.
그리고 정수론에서 가장 흔한 도구 중 하나가 바로 모드이다. 서로 다른 숫자들이 모듈러 연산의 세계에서는 같은 숫자로 간주된다. 마치 25시 ≡ 1시 (mod 24)와 같고, 요일 여덟 ≡ 월요일 (mod 7)과 같다. 이러한 등가 관계를 합동(Congruence) 이라고 부른다.
graph TD M["수학"] M --> N["정수론"] M --> FF["미적분학"] N --> A["정수"] A --> B["나누어떨어짐"] B --> B1["최대공약수 (GCD)"] B --> B2["최소공배수 (LCM)"] A --> C["소수"] C --> C1["소인수분해"] B --> D["합동 (모듈러 연산)"] D --> E["유클리드 호제법"] E --> E1["확장된 유클리드 호제법"] D --> F["오일러의 정리"] D --> G["페르마의 소정리"] D --> H["중국인의 나머지 정리"] E1 --> H H --> I["현대 암호학"] I --> I1["RSA"] I --> I2["ECC (타원곡선 암호)"] I --> I3["디지털 서명"] I3 --> I4["블록체인"]
수수께끼로 돌아와서, 마침내 공식이 등장하다
위에서 이렇게 많이 말한 것은 완전히 사전 포석이며, 사실은 여러분이 이 영어 글자들과 세 줄짜리 작대기가 무엇을 나타내는지 알게 하려는 것이다. 여기까지 쓰고도 공식을 쓰지 않는다면, 현대 수학에 조금 미안해질 것이다.
그래서 이제 공식을 등장시키되, 천천히 등장시키자.
우리가 찾고자 하는 정수 (x)가 있다고 하자. 이 정수는 다음을 만족한다:
$$x \equiv a_1 \pmod{m_1}$$$$x \equiv a_2 \pmod{m_2}$$$$\cdots$$$$x \equiv a_n \pmod{m_n}$$즉, $x$ 를 $m_1$ 으로 나누면 나머지가 $a_1$ 이고, $m_2$ 로 나누면 나머지가 $a_2$ 이며, …… $m_n$ 으로 나누면 나머지가 $a_n$ 이다.
중국인의 나머지 정리는 우리에게 말해준다: 만약 이 모듈러스 $m_1,m_2,\dots,m_n$ 들이 쌍마다 서로 소라면, 이 연립 합동 방정식은 반드시 해가 존재하며, 다음의 법(mod)에서:
$$ M = m_1,m_2,\cdots,m_n $$이 해는 유일하다.
“쌍마다 서로 소"라는 것은 무엇인가?
우리는 이 모듈러스들이 최대한 독립적이길 바란다. 왜냐하면 우리가 특정 수를 찾아내려면, 만약 당신이 6과 9를 모듈러스로 사용한다면, 그것들은 공통 인수 3을 포함하게 된다. 이때 나머지들 사이에 중첩이 발생하니, 이건 말도 안 되지 않는가.
그러므로 우리가 나누는 숫자들 임의의 두 수 간에 공통 인수가 없어야 한다. 예를 들어 3과 5는 서로 소이고 (서로를 구성하는 인수가 없음), 3과 7은 서로 소이며, 5와 7도 서로 소이다. 그것들 사이에 공통 인수가 없어서, 위치를 특정할 기회를 낭비하지 않는다.
그래서 중국인의 나머지 정리는 모든 모듈러스에 대해 조건 없이 성립하는 것이 아니라, 분명한 경계를 가지고 있다. 수학에서 가장 매력적인 지점 중 하나가 바로 여기에 있다: 수학은 결코 함부로 큰소리치지 않는다. 그것은 언제나 조건을 확실하게 적어둔다.
왜 해가 “유일"한가?
이 “유일"이란 오직 하나의 정수만 영원히 만족한다는 뜻이 아니라, 법 (M) 의 의미에서 유일하다는 것이다.
다시 말해, 아마도 무수히 많은 정수가 동일한 나머지 조건들을 만족시키지만, 그것들은 서로 (M) 의 배수만큼 차이가 난다. 모드 (M) 의 세계에서는, 그것들은 사실상 같은 답이다. 즉, 합동이다.
이 또한 내가 모듈러 연산을 매우 좋아하는 이유이다. 그것은 “무한히 많은 유사한 객체들"을 하나의 명료한 범주로 압축해버린다. 마치 해면의 물결처럼, 각 고리가 움직이지만 당신은 그것들이 동일한 리듬에 속해 있음을 안다.
구성 사상이란 무엇인가?
수학은 당신에게 단지 결론만 주는 것이 아니라, 다리를 놓는 길을 준다. 다음을 정의하자:
$$ M_i = \frac{M}{m_i} $$즉, 총곱 (M) 을 i번째 모듈러스로 나눈 뒤 얻는 그 조각이다. $M_i$ 와 $m_i$ 가 서로 소이기 때문에, 다음을 만족하는 정수 $y_i$ 를 찾을 수 있다:
$$ M_i y_i \equiv 1 \pmod{m_i} $$뜻은 이렇다: 우리는 ($M_i$) 가 모드 ($m_i$) 의 세계에서 1이 되길 바라며, 적절한 수 ($y_i$) 를 하나 더 곱하기만 하면 된다. 이때, 해는 다음과 같이 쓸 수 있다:
$$ x \equiv \sum_{i=1}^n a_i M_i y_i \pmod{M} $$실제로 논리는 매우 소박하다. 왜냐하면 당신이 ($M_i$) 를 모드 ($m_j$) 의 세계에 놓을 때, ($j=i$) 인 그 항을 제외한 다른 항들은 모두 ($m_j$) 에 의해 나누어떨어져 0이 되기 때문이다. 오직 대응하는 그 항만 남아서 정확히 ($a_i$) 와 같게 된다.
이것은 아주 아름다운 “방향성” 구조이다: 각 항목은 오직 자신의 모듈러스에게만 말하고, 다른 모듈러스에게는 침묵한다.
확장된 유클리드 호제법이란 무엇인가?
당신은 알아차렸을 것이다, 위의 구성 안에서 ($y_i$) 를 찾을 필요가 있다. 바로 곱셈에 대한 역원을 구하는 것이다(즉, 원래 수와 곱했을 때 결과가 1이 되는 수를 찾는 것. 예를 들어 $2\times\frac12=1$ 이므로 $\frac12$ 은 2의 곱셈 역원이다). 어떻게 찾을까? 이때 확장된 유클리드 호제법이 등장한다. 간단히 말해, 유클리드 호제법은 원래 최대공약수를 구하는 데 사용된다. 확장판은 더 나아가 우리에게 말해준다: 만약 두 수가 서로 소라면, 1을 그것들의 정수 조합으로 쓸 수 있다. 즉, 정수 $u,v$ 를 찾을 수 있으며, 다음을 만족한다:
$$ au + bv = 1 $$일단 1을 이렇게 표현할 수 있게 되면, 역원도 따라 나온다. 유클리드 호제법은 아주 좋은 기질을 지녔다: 성실하게 나눗셈을 해나가다 보면, 하는 사이에 구조가 나타난다.
현대적 본질: 23을 실제로 계산해내기
이제 우리가 앞서 마주한 문제를 풀어보자:
$$ x \equiv 2 \pmod{3} $$$$ x \equiv 3 \pmod{5} $$$$ x \equiv 2 \pmod{7} $$모듈러스는 각각 3, 5, 7이며, 이들은 쌍마다 서로 소이므로, 중국인의 나머지 정리를 사용할 수 있다. 먼저 총곱을 계산하자:
$$ M = 3 \times 5 \times 7 = 105 $$그런 다음 각각 계산한다:
$$ M_1 = \frac{105}{3} = 35,\quad M_2 = \frac{105}{5} = 21,\quad M_3 = \frac{105}{7} = 15 $$이제, 각 $M_i$ 가 해당 모듈러스에서 1이 되도록 만들어야 한다. $m_1=3$ 에 대해 우리는 $y_1$ 을 찾기를 원하며, 다음을 만족한다:
$$ 35y_1 \equiv 1 \pmod{3} $$먼저 35를 3으로 나눈 나머지는 2이므로, 실제로는 다음을 구하는 중이다:
$$ 2y_1 \equiv 1 \pmod{3} $$시험해보면, $y_1=2$일 때, $2\times 2=4\equiv 1 \pmod{3}$. 따라서 $y_1=2$. $m_2=5$ 에 대해 우리는 $y_2$ 를 찾기를 원하며, 다음을 만족한다:
$$ 21y_2 \equiv 1 \pmod{5} $$21을 5로 나눈 나머지는 1이므로:
$$ y_2 \equiv 1 \pmod{5} $$가장 간단하게 $y_2=1$ 로 취한다. $m_3=7$ 에 대해 우리는 $y_3$ 를 찾기를 원하며, 다음을 만족한다:
$$ 15y_3 \equiv 1 \pmod{7} $$15를 7로 나눈 나머지는 1이므로:
$$ y_3 \equiv 1 \pmod{7} $$가장 간단하게 $y_3=1$ 로 취한다. 그러면 공식은 다음을 제시한다:
$$ x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105} $$항별로 계산한다:
$$ 2 \cdot 35 \cdot 2 = 140 $$$$ 3 \cdot 21 = 63 $$$$ 2 \cdot 15 = 30 $$합하면: $ 140+63+30=233 $ 다시 105로 모듈로를 취한다:
$$ 233 \equiv 23 \pmod{105} $$따라서 해는:
$$ x \equiv 23 \pmod{105} $$즉, 23, 128, 233, 338……이 모두 이 나머지 조건들을 만족시키지만, 모듈로 105의 의미에서는 그것들은 모두 같은 답이다.
flowchart LR A["x ≡ 2 (mod 3)"] B["x ≡ 3 (mod 5)"] C["x ≡ 2 (mod 7)"] A --> D["35 × 역원 × 2"] B --> E["21 × 역원 × 3"] C --> F["15 × 역원 × 2"] D --> G["합하기"] E --> G F --> G G --> H["x = 23"]
옛사람의 방법: 다시 머리말 시로
이제 다시 처음의 구결 시를 보자. 이것은 정대위가 진구소의 해법을 정리한 것이다:
셋이 동행하면 칠십이 드물다.
3으로 나눈 나머지에 70을 곱한다.
왜냐하면 $70≡35=5\times7$ 을 동시에 만족시키고 $70\equiv1\pmod3$, $70\equiv0\pmod5$, $70\equiv0\pmod7$ 이기 때문이다.
이것은 70을 곱한 뒤에, 그것이 mod 3의 세계에서는 원래 나머지를 유지하고, mod 5와 mod 7의 세계에서는 완전히 “사라진다"는 것을 의미한다.
오나무 매화에는 스물한 가지.
“입일(廿一)“은 이십일이다.
5로 나눈 나머지에 21을 곱한다.
왜냐하면 $21=3\times7$ 이고, 또한 $21\equiv1\pmod5$ 이며, 동시에 $21\equiv0\pmod3, 21\equiv0\pmod7$ 이기 때문이다. 그래서 그것은 오직 mod 5의 조건에만 영향을 주고, 다른 두 조건을 간섭하지 않는다.
일곱 아들이 단결하면 정확히 보름.
옛사람이 말한 “보름(半月)“은 십오(十五)이다.
7로 나눈 나머지에 15를 곱한다.
왜냐하면 $15=3\times5$ 로, $15\equiv1\pmod7$ 을 만족하며, 동시에 $15\equiv0\pmod3,15\equiv0\pmod5$ 이기 때문이다.
그것 역시 오직 자기 자신의 조건만 책임진다. 그러하여 우리는 세 개의 아주 신기한 숫자들을 얻게 된다:
| 계수 | mod 3 | mod 5 | mod 7 |
|---|---|---|---|
| 70 | 1 | 0 | 0 |
| 21 | 0 | 1 | 0 |
| 15 | 0 | 0 | 1 |
- 70은 오직 mod 3만 책임진다;
- 21은 오직 mod 5만 책임진다;
- 15는 오직 mod 7만 책임진다.
이것들이 어떻게 더해지든, 서로 영향을 주지 않는다.
백다섯을 빼면 바로 알 수 있다.
여기의 “백다섯(百零五)“은 바로 $105=3\times5\times7$ 이다.
앞의 세 항을 전부 더한 뒤, 거듭해서 105를 빼면(오늘날의 말로는 105로 모듈로를 취하면), 가장 작은 양의 정수를 얻을 수 있으며, 이것이 최종 답이다.
이쯤 보면, 당신은 이것이 앞서 소개한 현대적 방법과 어딘가 다른 것 같다고 느낄지도 모른다. 우리가 방금 배운 공식에서는 “곱셈에 대한 역원"을 계산해야 했는데, 어째서 이 구결에는 묘사되어 있지 않은가?
그 이유는, 이것이 지극히 운이 좋은 특례이기 때문이다.
모듈러스 (3, 5, 7)에 대하여,
$$ 70\equiv1\pmod3, $$$$ 21\equiv1\pmod5, $$$$ 15\equiv1\pmod7. $$세 계수들은 본래부터 각자 곱셈에 대한 역원이므로, 근본적으로 추가 계산이 필요하지 않다.
반면 일반적인 중국인의 나머지 정리 문제에서는 이런 행운이 보통 일어나지 않는다. 예를 들어 모듈러스가 (4, 9, 11)이나 (5, 7, 11)로 바뀌면, 단순히 $M_i=\frac{M}{m_i}$ 만 사용하는 것으로는 조건을 만족시킬 수 없으며, 반드시 거기에 대응하는 곱셈 역원을 다시 곱해주어야 한다. 이것이 바로 현대 교재 속의 일반 공식이다:
$$ x\equiv\sum a_iM_iN_i\pmod M, $$여기서 ($N_i$) 가 바로 ($M_i$) 의 해당 모듈러스에서의 곱셈 역원이다.
바꾸어 말하면, 이 구결은 전혀 다른 알고리즘이 아니라, 현대의 중국인의 나머지 정리 공식이 모듈러스가 정확히 3, 5, 7일 때의 우아한 풀이이며, “구고의 정리"에서의 구삼, 고사, 현오와 같이, 모두 고대 중국 수학자들이 발견한 정리 중의 특례이다.
천 년 전의 옛사람들은 “곱셈의 역원"이 무엇인지 몰랐고, 현대의 합동 공식을 적지도 않았다. 그러나 그들은 이미 이 세 개의 신기한 숫자—70, 21, 15—를 발견했고, 그것들을 스물여덟 자의 구결 속에 농축시켰다. 오늘날 우리가 현대 대수학으로 그것을 다시 살펴볼 때에도, 이것이 중국인의 나머지 정리의 가장 핵심적인 사상임을 발견할 수 있다.
인터넷은 어떻게 응용하는가
당신이 HTTPS 웹사이트에 접속할 때
예를 들어 본 사이트에 진입한다:
당신의 브라우저와 내 서버 사이에 한 번의 핸드셰이크가 수행된다.
그중에서 서버는 다음을 증명해야 한다:
“내가 바로 hpu.edu.kg이다.”
그 방법은 다음과 같다:
자신의 RSA 개인 키로 한 데이터 조각에 대해 디지털 서명을 수행한다.
여기서 문제가 생긴다.
RSA의 개인 키 연산은 매우 느리다.
왜냐하면 그것은 대체로 다음과 같은 계산이 필요하기 때문이다.
$$ m^d \bmod n $$이때
- (n=pq)
- (p,q) 모두 수백 자릿수의 큰 소수이다.
이러한 거듭제곱 연산을 한 번 직접 계산하려면, 천 자릿수가 넘는 큰 정수를 처리해야 한다.
중국인의 나머지 정리는 어떻게 가속하는가?
RSA 개인 키는 다른 사람이 가지지 못한 정보를 가지고 있다:
서버는 알고 있다
$$ n=pq $$그러므로, 직접
$$ m^d\bmod n $$을 계산하지 않고,
두 개의 더 작은 문제로 분해할 수 있다.
먼저 계산한다
$$ m^d\bmod p $$다음으로 계산한다
$$ m^d\bmod q $$이 두 모듈러스는 원래 길이의 절반밖에 되지 않는다.
계산 속도가 훨씬 빠르다.
마지막으로, 다시 중국인의 나머지 정리를 이용하여:
두 답을 다시 합쳐서
$$ m^d\bmod n $$으로 만든다.
전체 과정은 바로 이것이다:
flowchart LR A["RSA 개인 키 연산
m^d mod n"] A --> B["분할"] B --> C["mod p 연산"] B --> D["mod q 연산"] C --> E["CRT 재조합"] D --> E E --> F["최종 서명/복호화 결과"] F --> G["HTTPS / SSH / VPN"]
이것이 RSA에서 CRT의 가장 저명한 응용이다.
왜 훨씬 빨라지는가?
가정해보자:
RSA가 2048비트이다.
그렇다면
- p는 대략 1024비트
- q는 대략 1024비트
현대의 곱셈 복잡도는 선형적이지 않다.
정수 길이가 반으로 줄면,
계산량은 보통 원래의 1/4 정도로 떨어진다.
두 개의 1/4을 합치면
대략
원래의 1/2이 된다.
여기에 빠른 거듭제곱 같은 알고리즘을 더 고려하면,
실제로는:
CRT-RSA는 보통 직접적인 RSA 개인 키 연산보다 약 3~4배 빠르다.
따라서 거의 모든 RSA 구현이 CRT를 사용한다.
만약 CRT를 사용하지 않는다면,
서버 성능이 크게 저하될 것이다.
그러면 그것은 무엇에 영향을 미쳤는가?
RSA 개인 키를 사용하는 거의 모든 곳이다.
예를 들어:
- HTTPS 웹사이트 인증서
- SSH 로그인
- VPN 신원 인증
- 소프트웨어 디지털 서명
- PDF 디지털 서명
- 이메일 암호화 (S/MIME)
서버가 RSA 개인 키 연산을 해야 하기만 하면,
CRT는 기본적으로 관여한다.
그럼 블록체인은?
블록체인 하면, 모두가 우선 암호화폐를 떠올릴 것이다, 비트코인(Bitcoin), 이더리움(Ethereum) 등. 하지만 이것들은 거의 CRT와 관련되지 않는다. 왜냐하면 그것들이 주로 채택하는 것은 ECDSA(타원곡선 디지털 서명) 이고, RSA가 아니기 때문에, CRT가 핵심이 아니다.
그러나 블록체인 기술은 디지털 서명에 의존하며, 디지털 서명에는 다양한 구현이 존재한다.
flowchart LR A["중국인의 나머지 정리"] A --> B["RSA"] B --> C["디지털 서명"] C --> D["HTTPS"] C --> E["소프트웨어 서명"] C --> F["신원 인증"] C -. "현대 블록체인은 더 많이\n타원곡선 디지털 서명을 채택한다" .-> G["블록체인"]
맺음말
당신은 가까스로 장교의 질문에 답했고, 당신의 신분을 증명했으며, 무사히 현대로 돌아왔다.
당신이 자신의 신분을 증명해야 할 때, 서버는 개인 키를 사용하여 디지털 서명을 수행한다. 그리고 중국인의 나머지 정리는 한 번의 거대한 모듈러 연산을 두 개의 더 작은 계산으로 분해할 수 있고, 다시 결과를 합쳐준다. 거의 모든 RSA 구현에서 CRT-RSA라고 불리는 이 최적화는 이미 표준 관행으로 자리 잡아, 개인 키 연산 속도를 약 3~4배 향상시킨다. 바로 그렇기 때문에, 2천 년 전에 탄생한 하나의 수학 정리가 오늘날에도 HTTPS, SSH, VPN, 소프트웨어 서명 등 현대 인터넷 인프라의 저변에서 묵묵히 작동하고 있는 것이다. 우리가 VPN을 통해 Google, Youtube, ChatGPT에 접속할 수 있는 것 또한, 종이에 적힌 이 오래된 계산식들 덕분이다.
《손자산경》 속 그 문제를 다시 보면, 그것은 사실 “옛사람이 계산할 줄 안다"가 아니다. 인류는 아주 일찍이, 어떤 문제들은 굳이 정면으로 부딪칠 필요가 없다는 것을 깨달았다. 당신은 한 바퀴 돌아서, 다른 각도에서 그것을 볼 수 있다. 당신은 보이지 않는 전체를, 보이는 부분들로 분해할 수 있으며; 또한 부분으로부터 다시 전체를 조립할 수도 있다.
나는 인류가 날짜를 기록하기 시작한 그날부터 오늘까지, 총 며칠이 지났는지 모른다. 이 숫자는 너무 크지만, 만약 내가 이 수를 7로 나누어 나머지를 얻으면, 나는 오늘이 무슨 요일인지 알게 된다; 그것을 12로 나누어 나머지를 얻으면, 나는 그것이 어느 달에 대응하는지 알게 된다; 그것을 365로 나누어 나머지를 얻으면, 나는 그것이 한 해 중 며칠째인지 알게 된다.
