|
정수론 Number Theory |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수· 배수 | 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론( 국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
楕 圓 曲 線 / elliptic curve타원곡선이란 아주 간단히 말하면 [math(y^2 = x^3 + Ax + B )] 꼴의 방정식으로 나타나는 곡선을 의미한다. 엄밀히 말하면 위 형태는 바이어슈트라스 표준형[1](Weierstrass normal form)으로, x와 y에 대한 삼차식은 대부분의 경우 대수적 변형을 통해 위 표준형으로 만들 수 있다고 한다. 더 정확히 말하자면 A나 B에 자질구레한 조건이 붙어있어야 하지만 그런 건 전공자들이나 생각하도록 하자. 보통 y좌표가 무한대라는 설정인 무한점을 추가하는데, 쌩뚱맞아 보이지만 이 무한점은 매우 중요하다.[2]
흔히 오해되는 부분이지만 일단 타원곡선 자체의 형태만 놓고 봐서는 도무지 타원을 연상하기 어렵다. 삼각함수가 삼각형 모양이 아닌 것과 마찬가지다. 형태상으로는 타원보다는 중괄호 내지는 젖꼭지에 가까운 모양[3]이다. 이 곡선에 '타원곡선'이란 이름이 붙은 이유는 타원의 둘레를 구하기 위한 적분의 역함수에서 유래했던 역사적 이유이지만, 지금은 그것과 전혀 상관 없이 사용되고 있다. 물론 이 마이너해 보이는 문서가 등재된 이유는 이름이 혼동스러워서인 것은 당연히 아니고, 수학 전반에서 엄청난 중요성을 갖고 있기 때문이다. 같은 대상을 실해석학에서, 복소해석학에서, 대수기하학에서, 정수론에서 모두 이야기할 수 있는 경우는 그렇게 많지 않다.
타원곡선은 일부 일반인들에게도 페르마의 마지막 정리의 증명의 중간 과정이나 또는 타원곡선 암호 등으로 친숙하겠지만, 이걸 제대로 배우려면 보통 수학과 대학원 과목인 대수기하학을 배워야 한다. 각 절에서 첫 번째 문단만 읽고 넘어가는 것을 추천한다.
2. 타원 적분
타원의 둘레를 구하기 위한 적분 계산에서 나왔다고 한다. 타원의 둘레를 구하기 위해 적분을 해보면 삼차식의 제곱근호를 동반한 유리식이 튀어나오는데, 이것이 타원적분이란 이름이 붙은 유래.더 자세히 알기 위해서는 다음 링크 수학노트:타원적분론 입문, 수학노트:타원적분, 영문위키:Elliptic Integral 등을 참고하거나, 타원 문서를 참고.
타원적분은 생각 외로 단순한 곳에서도 발견되는데, 대표적으로 단진자의 주기를 구하기 위해 필요하다. 단진자의 운동을 나타내는 미분방정식이 비선형이므로 고등학교나 일반물리 정도의 수준에서는 이를 선형으로 근사하여 단진동처럼 풀이하지만, 비선형인 채로 제대로 문제를 풀면 타원적분이 나타나게 된다.
3. 성질
기본적으로 [math(x)]축에 대칭인 음함수이다. 이를 양함수 형태로 바꾸면 다음과 같다.[math(y = \pm \sqrt{x^3+Ax+B} )]
도함수는 음함수의 미분법을 사용해 다음과 같이 나타낼 수 있다.
[math(\begin{aligned} \dfrac{\mathrm{d}y}{\mathrm{d}x} &= -\dfrac{\dfrac{\partial}{\partial x} (x^3 - \cancel{y^2} + Ax + \cancel{B})}{\dfrac{\partial}{\partial y} (\cancel{x^3} - y^2 + \cancel{Ax} + \cancel{B})} \\ &= \dfrac{3x^2 + A}{2y} \end{aligned})]
4. 복소타원곡선과 리만 곡면
미지수 [math(x)]와 [math(y)]가 복소수일 때에 생각하는 타원곡선은 곡면이 되는데, 이는 복소수가 두 개의 차원을 갖기 때문이다. 엄밀하게 말하면 리만 곡면(Riemannsche Fläche), 즉 복소평면의 구조가 주어진 곡면으로 이해할 수 있다. 타원곡선이 나타내는 리만 곡면의 모양은 원환면, 즉 도넛의 표면처럼 생겼다. 도저히 이해가 불가능하지만 그렇단다.이를 수학적으로 이해하려면 다음의 과정이 필요하다. 원환면 문서에서도 알 수 있듯이, 원환면은 복소수 집합 [math(\mathbb C)]를 복소수의 격자(lattice) [math(\Lambda)]에 대해 잉여군을 취한 것이라 할 수 있다.[4] 이제 바이어슈트라스 타원 함수
[math(\displaystyle \wp(z) = z^{-2} + \sum_{w \in \Lambda - \{0\} } ((z-w)^{-2} - w^{-2} ))]
는 [math(\Lambda)]에 대한 주기함수, 즉 임의의 [math(w \in \Lambda)]에 대해 [math(\wp(z+w) = \wp(z))]를 만족시킨다. 따라서 이는 [math(\mathbb{C}/\Lambda)] 위의 함수로 생각할 수 있다. 한편 [math(\wp(z))]와 그 도함수 [math(\wp'(z))]는 [math(\Lambda)]에 대해 주어지는 상수 [math(A)]와 [math(B)]에 대해 방정식
[math([ \wp'(z) ]^2 = [ \wp(z) ]^3 + A \wp(z) + B)]
를 만족시키는데, 이것은 타원곡선의 방정식이다. 타원곡선 [math(E)]가 하나 있으면 적절한 격자 [math(\Lambda)]가 존재해 이 방정식이 [math(E)]가 되게 할 수 있고, 그러면 [math((x,\,y) = (\wp(z),\, \wp'(z)))]로 주어진 함수 [math(\mathbb{C}/\Lambda \mapsto E)]가 일대일대응이 되는 것.
5. 타원곡선의 군
모든 타원곡선에는 다음과 같은 두 점을 더하는 매우 신기한 연산이 있다. 두 점 [math({\rm P}=(x_{1},\,y_{1}))]와 [math({\rm Q}=(x_{2},\,y_{2}))]가 있다고 할 때, 이들의 합 [math(\rm{P+Q})]는 다음과 같이 정의한다.- [math(\rm P)]와 [math(\rm Q)]를 잇는 직선 [math(l)]은 타원곡선과 다른 한 점 [math({\rm R}=(x_{3},\,y_{3}))]에서 만난다.
- [math(\rm R)]을 [math(x)]축에 대칭시킨 [math({\rm S}=(x_{3},\,-y_{3}))]가 [math(\rm{P+Q})]가 된다.
- 예외 규칙
- 무한점 [math(\infty)]에 대해서는 "[math(\infty)]을 지나는 직선은 [math(y)]축과 평행한 직선이다" 라는 규칙을 적용시킨다. 예를 들어 [math(l)]이 [math(y)]축에 평행해서 다른 일반 점하고 안 만날 때는, R은 [math(\infty)]로 정의한다. 만약 [math(\rm{P}=\infty)]일 때는, [math(l)]은 '[math(\rm Q)]를 지나고 [math(y)]축에 평행한 직선'이 된다.
- 만약 [math(l)]이 다른 한 점 [math(\rm R)]에서 만나지 않을 경우에는, [math(l)]은 [math(\rm P)] 또는 [math(\rm Q)]에서 접할 것이다. 이 때 [math(\rm R)]은 [math(l)]이 접하는 점이 된다.
- [math(\rm{P=Q})]인 경우에는 [math(l)]은 '[math(\rm P)]에서 그은 접선'으로 정의한다. 이 때 [math(l)]이 다른 한 점 [math(\rm{R})]에서 만나지 않는다면 [math(l)]은 [math(\rm P)]에서 변곡점을 가져야 하며, 이 때 [math(\rm R)]은 [math(\rm P)]로 생각한다.
- [math(\infty)]에서 그은 접선은 [math(\infty)]에서 변곡점을 가진다. [math(\infty)]를 [math(x)]축에 대칭시키면 [math(\infty)]이다.
예외규칙이 많아서 복잡해보이지만, 사실 첫 두 개만 중요하다. 더 귀찮은 사람은 세 점이 나란히 직선 위에 있으면 더해서 0이라고 기억하자. 어쨌든 이렇게 정의한 연산은 무려 교환법칙과 결합법칙[5] 을 만족시키며, [math(\infty)]을 항등원으로 갖고, '[math(x)]축에 대한 대칭점'을 역원으로 갖는 신기한 성질들을 지닌다. 한 마디로 말해서 군, 그 중에서도 교환법칙을 성립하는 군인 아벨 군이 된다.
[math(l)]이 타원곡선과 두 점에서 만나면 다른 한 점에서도 만나야 한다는 것은, '삼차식이 두 개의 근을 가지면 하나의 근을 더 가져야 한다'는 이유로 설명할 수 있다. 무한점의 경우에는 ([math(x)]와 [math(y)]가 실수인 경우에) [math(y)]가 무한대로 갈 때의 극한, 접선 예외 규칙의 경우에는 [math(\rm Q)]가 [math(\rm P)]로 접근할 때의 극한 이런 식으로 억지로 납득할 수 있을 것이다. 물론 이게 올바른 이해 방법이란 건 아니다. 사실 교환법칙, 항등원, 역원에 대한 내용은 위 예외 규칙들을 잘 숙지했다면 증명하기는 쉬운 내용이긴 하다. 문제는 결합법칙인데, 이것은 다소 어렵다.
교점 좌표는 다음과 같이 구할 수 있다.
|
타원곡선 [math(y^2=x^3+ax+b)] 위에 주어진 점 [math({\rm P}(x_P, \,y_P))]와 [math({\rm Q}(x_Q,\, y_Q))]사이를 잇는 직선 [math(\displaystyle y=\frac{y_Q-y_P}{x_Q-x_P}(x-x_P)+y_P)] 을 타원곡선에 대입한 뒤 정리하면 삼차방정식 [math(\displaystyle x^3-\left(\frac{y_Q-y_P}{x_Q-x_P}\right)^2x^2+(일차식)=0)] 을 얻는데, 직선이랑 타원곡선이 교차하는 또다른 점을 R(xR, yR)이라고 하면 근과 계수의 관계 [math(x_P+x_Q+x_R=\left(\frac{y_Q-y_P}{x_Q-x_P}\right)^2)]에 따라 [math(\therefore x_R=\left(\dfrac{y_Q-y_P}{x_Q-x_P}\right)^2-x_P-x_Q)] 임을 알 수 있다. 그다음 구한 [math(x_R)]값을 [math(y_R=\dfrac{y_Q-y_P}{x_Q-x_P}(x_R-x_P)+y_P)] 에 대입하고 정리하면 [math(y_R=\dfrac{y_Q-y_P}{x_Q-x_P}\left(x_R-\dfrac{x_Q+x_P}{2}\right)+\dfrac{y_P+y_Q}{2})] 를 얻는다. 이제 이 연산이 어떤건지 한번 보자. 타원곡선 위 점 X(xX, yX)을 미분방정식 [math((f'(x))^2=(f(x))^3+af(x)+b)]를 만족하는 함수를 써서 각각 xX=f(x), yX=f'(x)로 놓으면 점 P~R에 대해서도 [math(\displaystyle f(r)=\left(\frac{f'(q)-f'(p)}{f(q)-f(p)}\right)^2-f(q)-f(p))] [math(\displaystyle f'(r)=\frac{f'(q)-f'(p)}{f(q)-f(p)}\left(f(r)-\dfrac{f(p)+f(q)}{2}\right)+\dfrac{f'(p)+f'(q)}{2})] 로 놓을 수 있다. 이 r값을 구하기 위해 [math(\frac {dp}{dx}=\frac {dq}{dx}=1)]로 놓고 f(r)을 미분하면 [math(\displaystyle f'(r)\frac {dr}{dx})] [math(\displaystyle =-2\left(\frac{f'(q)-f'(p)}{f(q)-f(p)}\right)^3~(분자미분)+2\frac{(f(q)-f(p))(f'(q)-f'(p))}{(f(q)-f(p))^2}~(분모미분)-f'(q)-f'(p))] [math(\displaystyle =-2\frac{f'(q)-f'(p)}{f(q)-f(p)}(f(r)+f(p)+f(q))+2×\frac32\frac{(f(q)^2-f(p)^2)(f'(q)-f'(p))}{(f(q)-f(p))^2}-f'(q)-f'(p))] [math(\displaystyle =\frac{f'(q)-f'(p)}{f(q)-f(p)}(f(p)+f(q)-2f(r))-f'(q)-f'(p))] [math(\displaystyle =-2f'(r))] 이고, r에 대한 식이 대칭식이므로 r=-p-q임을 알 수 있다. 여기서 f(x)가 짝함수, f'(x)가 홀함수이므로 R=(f(p+q), -f'(p+q))이니 교점 R을 y축에 대칭시킨 R'(xR, -yR)=(f(p+q), f'(p+q))을 점 P와 점 Q를 더한 것으로 정할 수 있으며, 이 연산은 결합법칙 등 또다른 성질도 만족시킴을 알 수 있다. |
6. 타원곡선과 정수론
보통 정수론에서는 두 가지 상황에서 타원곡선을 생각한다. 하나는 x와 y가 유리수일 때, 즉 타원곡선의 유리수점의 집합 E(Q)를 생각하는 것이다.[6] 이 유리수점은 위의 군 연산에 대해 닫혀 있고, 모델-베유 정리(Mordell-Weil theorem)에 의해 모든 유리수점은 유한 개의 유리수점의 합으로 나타낼 수 있다.[7][8] 또 다른 하나는 x와 y가 정수이고, 이를 N으로 나눈 나머지를 생각하는 것이다. 즉 합동방정식
E: [math(y^2 \equiv x^3 + Ax + B \pmod N)]
의 해들의 집합 E(N)을 생각하는 것.[9] 보통 N이 소수일 때를 생각한다. 예를 들어서
E: [math(y^2 = x^3 + x + 1)]
에서
E(3) = {(0,1), (0,2), (1,0), [math(\infty)]}
E(5) = {(0,1), (0,4), (2,1), (2,4), (3,1), (3,4), (2,4), (3,4), [math(\infty)]}
정도가 되겠다.E(5) = {(0,1), (0,4), (2,1), (2,4), (3,1), (3,4), (2,4), (3,4), [math(\infty)]}
보다 고급 과정에서는 |E(p)|의 정보들을 모두 모아 L-함수(L-function)란 매우 중요한 대상을 만들고 연구한다. 이 L-함수의 정의에 대해선 버치-스위너턴다이어 추측을 참고하도록 하자. 이 L-함수는 E(Q)의 크기를 어림하는 추정치로 생각되고, 이 추정이 맞는지 틀리는지가 바로 버치-스위너턴다이어 추측의 내용.[10]
한편 이 타원곡선의 L-함수와 보형형식(modular form)의 L-함수는 매우 성질이 비슷해서, 수학자들은 '모든 타원곡선의 L-함수는 어떤 보형형식의 L-함수로 나타낼 수 있다'라는 생각을 하게 되었다. 이것이 바로 그 유명한 타니야마-시무라 추측(Taniyama-Shimura conjecture), 페르마의 마지막 정리 증명의 핵심 내용이다. 참고로 이 타니야마-시무라 추측과 페르마의 마지막 정리를 연결짓는 엡실론 추측(epsilon conjecture)의 내용은, 만약 다음의 정수해
[math(a^p + b^p = c^p)]
가 있다고 가정한다면, 다음의 타원곡선
[math(y^2 = x(x+a^p )(x-b^p))]
의 L-함수는 어떤 보형형식의 L-함수로 나타낼 수 없다는 것이다.[11]이런 식으로 정수론에서의 타원곡선은 특이한 성질들을 매우 많이 갖고 있을 뿐만이 아니라 수학의 굵직한 문제들을 푸는 강력한 도구가 되었고, 덕분에 주목 받게 되었다. 사실상 타원곡선만을 위한 문제인 버치-스위너턴다이어 추측이 밀레니엄 문제로 설정된 것을 생각해보자. 물론 주목을 받고 있다 뿐이지, 여전히 수학자들은 타원곡선에 대해 아는 것보다 모르는 것이 훨씬 많다. 어찌 보면 정수론에서의 소수와 대단히 비슷한 포지션을 갖고 있다. 심지어는 이 타원곡선마저도 RSA로 실생활에 응용이 되고 있는 것과 똑같다.
여담으로, 레딧에서 퍼져 유행했던 디오판토스 방정식의 일종인 과일 문제를 타원곡선을 이용해 풀 수 있다. 주어진 문제를 타원곡선으로 변형한 후, 그 위의 유리수점들을 찾아서 (🍎, 🍌, 🍍)가 양수인 경우를 모두 찾아보는 것이다. 한국어 영상 버전. 위 식을 다음처럼 바꾸고
[math(\begin{cases} 🍎=tu \\ 🍌=t(v+y) \\ 🍍=t(v-y) \end{cases})]
양 변에다 분모를 곱한 뒤에 u, v를 x에 대한 적절한 1차식으로 놓아 주어진 식을 타원곡선으로 만드는 게 핵심이다.
계산이 끝나면 비례상수 t를 곱하여 🍎, 🍌, 🍍를 자연수로 만들어주면 된다. 그러면 저 간단한 방정식의 80자릿수를 넘어가는 자연수해를 확인할 수 있다.
{{{#!folding [자연수해 펼치기 · 접기 ]
자연수해가 아닌 정수해를 구한다면 🍎=4, 🍌=-11, 🍍=1이라는 비교적 단순한 해가 도출된다.
6.1. 타원곡선 암호
|
'''
이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' |
|||||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
타원곡선 암호는 RSA 암호화처럼 공개키 암호화 방식으로, 위에 말한 타원곡선의 합동방정식의 해인 [math(E(p))]를 이용한다. RSA가 [math(e)]와 [math(M=pq)]를 공개하고 마치 평서문 a를 (ae mod m)으로 암호하는 것처럼, 비슷하게 타원곡선 암호는 [math(e)]와 [math(E(p))]를 공개하고, 보내려는 평서문을 타원곡선의 점 [math(X)]에 대응시키고 [math(X)]를 위에 소개한 군 연산을 이용해 [math(e)]번 더한 점 [math(eX)]로 보내는 것이다. 물론 여기서 당연히 [math( p)]는 RSA에서처럼 적기도 힘든 수가 되고, [math(E(p))]의 구조는 고사하고 원소의 개수가 무엇인지조차 감을 잡을 수 없게 된다.
여기선 잘 알려진 RSA를 예로 들었지만, 타원곡선 암호는 소인수분해의 어려움을 이용한 RSA보다는 이산 로그 문제의 어려움을 이용한 암호 체계에 탑재되기에 더 적합하다. 디피-헬만 키 교환 알고리즘이 대표적인 예이다. 사실 법 [math(p)] 위에서의 0이 아닌 정수와 그 곱 연산은 유한 순환군(finite cyclic group)으로 간단하게 일반화할 수 있으며[12], 이는 곧 충분히 크고 복잡한 유한 순환군을 가지고 있으면 이걸로 새로운 디피-헬만 키 교환 알고리즘을 만들 수 있다는 것을 시사한다. 그렇게 해서 나온 물건이 바로 타원곡선 디피-헬만 (Elliptic Curve Diffie-Hellman; ECDH) 키 교환 알고리즘이다.[13] 다만 알려져 있다시피 디피-헬만은 키 교환 과정을 위한 전자서명 기능을 제공해 주지 않으며[14], 이는 타원곡선이든 일반화이든 마찬가지이다. 따라서 ECDH 단독으로는 쓰지 않고 다른 전자서명 알고리즘을 같이 쓰는 것이 보통이다. 여기서 또 타원곡선이 쓰이는데, DSA (Digital Signature Algorithm) 중 한 종류이자 타원곡선 기반의 알고리즘인 ECDSA(Elliptic Curve Digital Siganture Algorithm)가 흔히 ECDH와 같이 쓰인다.
네이버 라인의 Letter Sealing 기능이 ECDH를 사용하고 있다고 한다.
7. 교재
조지프 힐럴 실버먼(Joseph Hillel Silverman)의 타원곡선에 대한 책 2권( The Arithmetic of Elliptic Curves, Advanced Topics in the Arithmetic of Elliptic Curves)이 가장 표준적인 책이다. AMS의 Citation 수치로 봐도 압도적이다. 그리고 데일 휴스몰러(Dale Husemöller)의 책이 있는데, GTM 시리즈이긴 하지만 연습 문제가 거의 없고, 책도 400페이지 내외이고, 게르트 팔팅스 교수의 리뷰를 보면 실버먼의 모든 토픽을 다루고 있다고 하는 걸로 봐선 Springer Monograph in Mathematics의 책으로 추정된다.
[1]
원의 방정식의 '표준형' 등 할 때 같은 표준형이다.
[2]
이는 타원곡선을
사영기하학적 관점에서 볼 때 이해될 수 있다.
[3]
4차원 복소공간에서는
토러스 형태이다.
페르마의 마지막 정리를 다룬
다큐멘터리에서 이 형태로 나왔다.
[4]
뭔 말이냐면 이 함수는 복소평면에서 두 방향으로 주기성이 나타나는데, 이런 두 방향 주기성은 원환면이 가지는 특징이다.
[5]
아래 공식을 이용해서 각각 [math( S_1=\rm{(P+Q)+R})]과 [math( S_2=\rm{P+(Q+R)})]을 계산해보자. 물론 이 [math( \rm R)]은 [math( \rm{P+Q})]을 말하는 게 아니다.
[6]
정수론에서 타원곡선의 A와 B는 보통 유리수이다.
[7]
대수학을 배운 사람들이 알아들을 수 있는 정확한 내용은 이는 E(Q)의 군이 유한생성 가환군(Finitely generated abelian group)이라는 것이다.
[8]
정확하게는 다음 판별식을 만족하는 타원함수에 대하여 적용된다. 즉 [math(\Delta E=-4a^3c+a^2b^2-4b^3-27c^2+18abc)]가 0이 아닌 정수 [math(a,b,c)]에 대하여 [math(E:y^2=x^3+ax^2+bx+c)]라는 타원곡선은 유한개의 유리수해를 가진다는 것이 밝혀져 있으며, 만약 판별식이 0이면 해당 타원곡선은 삼중근 혹은 중근을 가져서 자기 자신과 교차하거나 첨점을 가지게 된다. 또한, 이 판별식이 0이 아닐 때, 이미 알려진 유리수점과 직선을 이용한 평행이동을 이용한 닫힌 연산으로는 확장할 수 없는 꼬인점(Torsion Point)은 많아야 15개 있다는 것도 알려져 있으며(마주르의 정리), 이런 꼬인점은 반드시 정수 격자점 좌표를 가지고 특히 [math(y)]좌표는 반드시 그 제곱이 판별식의 16배로 나뉘진다(나겔-루츠 정리)는 것도 밝혀져 있다.
[9]
여기서 A와 B는 정수, 혹은 분모가 N하고 서로소인 유리수여야 한다.
[10]
국소-대역 원리(local-global principle)에 따르면 디오판토스 방정식의 global field solution, 즉 Q-solution이 local field solution, 즉 p-adic 해와 real/complex solution과 관련이 있어야 하기 때문이다.
[11]
이를 보통 이 타원곡선이 'modular가 아니다' 고 한다.
[12]
조금 더 구체적인 아이디어는
ElGamal 문서를 참고하자.
[13]
이때 어떤 타원곡선을 쓰느냐에 따라 여러 알고리즘을 만들 수 있다. 가장 유명한 예로
Curve25519를 들 수 있다.
[14]
키 교환 과정에서 생길 수 있는
중간자 공격을 방어하기 위한 수단이 필요한데, 이를 위해 흔히 쓰이는 것이 바로 전자서명이다.