렌스트라의 타원곡선 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''렌스트라의 타원곡선 알고리즘 (Lenstra Elliptic Curve Algorithm)'''은 [[타원곡선]]의 성질을 이용한 [[소인수분해]] 방법이다. 모든 [[자연수]]에 적용할 수 있으면서 일반적인 컴퓨터에서 실행할 수 있는 소인수분해 알고리즘 중 3번째로 빠른 [[알고리즘]]이며 (2번째는 다중 [[이차 체]] - Multiple Polynomial Quadratic Sieve, 1번째는 [[수체 체]] - General Number Field Sieve), 주로 소인수분해하고 싶은 큰 수에서 작은 소인수들을 분리하는 데 많이 쓰이는 알고리즘이다. 또한 이 알고리즘은 소인수분해하고 싶은 수가 60-70자리를 넘지 않는 소인수를 가지고 있을 때는 가장 빨리 작동하는 알고리즘이다.

== 알고리즘 ==
렌스트라의 타원곡선 알고리즘은 다음과 같이 작동한다. 여기서 [[소인수분해]]하고 싶은 자연수는 n이며, 모든 과정의 수들이나 타원 곡선은 (mod n)을 기준으로 계산한다. 즉, n으로 나눈 나머지를 생각한다.

# 무작위로 타원곡선을 하나 고른다. 여기서 타원 곡선은 <math>y^2=x^3+ax+b</math> 형태의 곡선이며, 이 타원 곡선의 비자명한 점 <math>P(x_0, y_0)</math>을 구한다. 이 과정은 간단히 무작위로 <math>x_0, y_0, a\in \Z/n\Z</math>인 정수 x<sub>0</sub>, y<sub>0</sub>, a를 고른 후, <math>b\equiv y_0^2-x_0^3-ax_0\pmod{n}</math>를 구하면 된다.
# 밑의 '타원곡선의 덧셈 법칙' 문단에 나오는 s를 이용하여 <math>[k]P=P+P+...+P</math> (k번 더한다)를 계산한다. 여기서 k는 여러 작은 소인수들을 많이 가지고 있는 자연수이며, k는 간단히 충분히 작은 수 B를 이용하여 k=B!라고 해도 된다. <math>[B!]P</math>를 계산하는 경우 먼저 <math>[2]P=P+P</math>를 계산한 후, <math>[3!]P=[3]([2]P)=[2]P+[2]P+[2]P</math>를 계산하고, 이런 식으로 <math>[B!]P</math>를 계산하거나 s를 구하는 과정에서 n의 비자명한 약수가 나올 때까지 계속하면 된다.
## 여기서 s를 구할 때 s가 분수 형태로 나온다면 확장된 유클리드 호제법을 이용해서 분모의 역수를 구한다. 만약 분모의 역수가 존재하지 않고 분모와 n의 최대공약수가 1보다 크면서 n보다 작을 때 이 최대공약수가 n의 비자명한 약수가 된다. 이 경우 약수를 출력한 후 알고리즘을 종료한다.
## 만약 <math>[k]P</math>를 다 계산했는데 비자명한 약수가 나오지 않았다면 다른 x<sub>0</sub>, y<sub>0</sub>, a, b를 고른 후 이 알고리즘을 다시 실행하거나, [[폴라드 로 알고리즘]]이나 [[이차 체]] 같은 다른 소인수분해 알고리즘으로 n을 소인수분해한다.

=== 타원곡선의 덧셈 법칙 ===
타원곡선의 두 점을 알 때, 이 두 점을 더하면 타원 곡선 위에 있는 또 다른 한 점을 알 수 있는데, 이때 두 점을 더하는 법칙을 타원곡선의 덧셈 법칙이라고 한다. 타원곡선의 덧셈 법칙은 다음과 같다. 여기서 타원 곡선은 <math>y^2=x^3+ax+b\pmod{n}</math>이며, 모든 과정에서는 n으로 나눈 나머지만을 생각한다는 것에 주의한다.

* 두 점 <math>P(x_P,y_P)</math>와 <math>Q(x_Q, y_Q)</math> (단, x<sub>P</sub>와 x<sub>Q</sub>의 값은 다르다)를 더한 값이 <math>R(x_R, y_R)</math>이라고 할 때, x<sub>R</sub>과 y<sub>R</sub>은 다음과 같이 구하면 된다.
** <math>s=\frac{y_P-y_Q}{x_P-x_Q}</math>를 구한다. 만약 이 수가 정수가 아니라면 확장된 유클리드 호제법을 이용하여 분모의 역수를 구한 후 그 역수를 <math>y_P-y_Q</math>에 곱한 값을 s로 정하면 된다. 이 과정에서 <math>x_P-x_Q</math>의 역수를 구할 수 없다면 이 수와 n의 최대공약수는 n의 비자명한 약수가 된다.
** <math>x_R=s^2-x_P-x_Q</math>, <math>y_R=y_P+s(x_R-x_P)</math>가 된다.

* 만약 x<sub>P</sub>=x<sub>Q</sub>인 경우 다음과 같이 <math>R(x_R, y_R)</math>을 구하면 된다.
** <math>s=\frac{3{x_P}^2+a} {2y_P}</math>를 구한다. 위에서와 마찬가지로 이 수가 정수가 아니라면 확장된 유클리드 호제법을 이용하여 분모의 역수를 구한 후 그 역수를 <math>3{x_P}^2+a</math>에다가 곱한 값을 s로 정한다. 이 과정에서 <math>2y_P</math>의 역수를 구할 수 없다면 이 수와 n의 최대공약수는 n의 비자명한 약수가 된다.
** <math>x_R=s^2-2x_P</math>, <math>y_R=y_P+s(x_R-x_P)</math>가 된다.

=== 확장된 유클리드 호제법 ===
타원곡선 알고리즘에서는 (mod n)에서 어떤 수 x의 [[곱셈 역원|역수]] y를 구해야 하는 경우가 생긴다. 이때 <math>xy\equiv1\pmod{n}</math>이 되게 하는 수 y를 x의 역수, 즉 x<sup>-1</sup> ≡ y (mod n)이라고 정의한다. 이때, 확장된 유클리드 호제법은 일반적인 유클리드 호제법과는 다르게 두 수 a와 b의 최대공약수뿐만이 아니라 어떤 두 수 p, q에 대하여 <math>ap+bq=\gcd(a,b)</math>인지도 알려 주는데, 여기서 a=n이라 하고 b는 역수를 구하고 싶은 수라고 하면 gcd(n, b)가 1 또는 n이 아닌 경우에는 이 gcd(n, b)가 n의 비자명한 약수가 되고, gcd(n, b)가 1인 경우에는 <math>np+bq \equiv bq \equiv 1 \pmod{n}</math>이 되므로 q가 b의 역수가 된다.

이때, 확장된 유클리드 호제법은 다음과 같이 작동한다.

* <math>r_0=a, r_1=b</math>이고 <math>s_0=1, s_1=0</math>이며, <math>t_0=0, t_1=1</math>이라고 초깃값을 설정한다.
* 다음 점화식에 따라 r, s, t를 계산해 나간다.
** <math>r_{i+1}=r_{i-1}-q_{i}r_{i}</math> (단, 여기서 <math>0\leq r_{i+1}<|r_i|</math>이며, 이 조건이 q<sub>i</sub>를 정의한다. 이 과정은 간단하게 r<sub>i+1</sub>은 r<sub>i-1</sub>을 r<sub>i</sub>로 나눈 나머지, q<sub>i</sub>는 r<sub>i-1</sub>을 r<sub>i</sub>로 나눈 몫이라고 생각하면 된다.)
** <math>s_{i+1}=s_{i-1}-q_is_i</math>
** <math>t_{i+1}=t_{i-1}-q_it_i</math>
* 만약 <math>r_{k+1}=0</math>이라면 확장된 유클리드의 호제법은 멈추게 되고, <math>r_k=\gcd(a, b)</math>가 되며 <math>p=s_k</math>, <math>q=t_k</math>가 된다.

여기서 1 < r<sub>k</sub> < n이라면 r<sub>k</sub>는 n의 비자명한 약수가 되고 r<sub>k</sub>=1인 경우 t<sub>k</sub>가 b의 역수가 된다.

== 원리 ==
만약 p와 q가 n의 소인수라고 하면, <math>y^2=x^3+ax+b\pmod{n}</math>은 (mod n)을 (mod p)나 (mod q)로 바꾸어도 똑같은 해들을 가지게 된다. 이 두 새 타원곡선들에서 타원곡선 위의 점들을 더해 나가 얻어낸 해들은 군을 이루게 되는데, 만약 이 두 군이 각각 N<sub>p</sub>, N<sub>q</sub>개의 원소를 가지고 있다면 라그랑주의 정리에 의해 원래 타원곡선의 아무 점 P에 대해서 k>0이면서 <math>kP=\infty</math> (mod p)인 최소의 k가 존재하고 이 k는 N<sub>p</sub>를 나누게 되며 <math>N_pP=\infty</math>이 된다. 또한 이 논리는 (mod q)인 경우에도 그대로 적용할 수 있다. 여기서 원래의 타원곡선이 무작위로 골라진다면 N<sub>p</sub>와 N<sub>q</sub>는 각각 p+1과 q+1에 근접한 어떤 수가 되고, 이때 N<sub>p</sub>의 소인수들과 N<sub>q</sub>의 소인수들은 대부분 다른 수가 된다. 따라서 이 차이에 의해 만약 우리가 임의의 수 e에 대하여 ''eP''를 계산해 나가면 우리는 어떤 수 k에 대하여 ''kP''가 (mod p)에서는 ∞의 값을 가지지만 (mod q)에서는 ∞이 아닌 경우가 생기거나 이 반대의 경우가 생겨나게 된다. 이때 원래의 타원곡선 ((mod n)의 경우)에서는 ''kP''라는 점이 존재하지 않게 되는데, 이 점이 존재하지 않는 경우 우리는 알고리즘의 과정 중에서 어떤 수 v에 대하여 gcd(v, n)=p이거나 gcd(v, n)=q인 v를 찾아내게 된다. 이 경우, gcd(v, n)은 n의 비자명한 [[약수]] (p 또는 q)를 찾아내게 되어 타원곡선 알고리즘이 n의 비자명한 약수를 찾아내게 된다.

== 예시 ==
n = 455839를 소인수분해하고 싶다고 하자.

# x<sub>0</sub>, y<sub>0</sub>, a는 0부터 n-1 사이의 정수 중 아무 수나 뽑으면 된다. 여기서 무작위로 이 수들을 고르면 x<sub>0</sub>=1, y<sub>0</sub>=1, a=5이고 <math>b\equiv {y_0}^2-{x_0}^3-ax_0\equiv1-1-5\equiv-5 \pmod{455839}</math>가 되므로 타원곡선은 <math>y^2=x^3+5x-5</math>이고 점 <math>P(1, 1)</math>은 이 타원곡선 위의 점이 된다.
# [10!]P를 계산하기로 하면 먼저 2P를 계산하고, 그 다음 3(2P), 4(3!P), ... 이런 식으로 10(9!P)까지 계산하면 된다.
## 2P = P+P를 계산하려면 먼저 s를 구한다. 위의 알고리즘 문단의 공식에 대입하면 s=4가 되고, 다시 위의 공식에 대입하면 2P = (14, -53)이 된다. 실제로 2P = (14, -53)은 (-53)<sup>2</sup> ≡ 14<sup>3</sup>+5·14-5 (mod 455839)가 되어 타원곡선 위의 점이 된다.
## 다음으로 3!P = 2P+2P+2P를 계산한다. 먼저 2P+2P를 구하면 <math>s=-\frac{593}{106}</math>이므로 106의 역수를 확장된 유클리드 호제법을 이용하여 구하면 81707이 된다 (즉, 106<sup>−1</sup> ≡ 81707 (mod 455839)이다). 따라서 s=-593 · 81707 ≡ 322522 (mod 455839)이고, 이 s와 위의 공식을 이용하여 2P+2P=4P를 계산하면 4P = (259851, 116255)이며 이 점 역시 원래 타원곡선 위의 점이 된다. 이 4P와 2P를 다시 더하면 3!P를 구할 수 있게 된다.
## 이런 식으로 반복하면 비슷한 방식으로 4!P, 5!P, 6!P 등을 구할 수 있게 되는데, 8!P를 구하는 과정에서 타원곡선 알고리즘은 599의 역수를 구하게 된다. 여기서 확장된 유클리드 알고리즘은 n = 455839가 599로 나누어 떨어진다고 나오고, 455839/599=761이며 이 두 수는 모두 소수이므로 n을 소인수분해하면 n = 455839 = 599 · 761이 된다.

여기서 타원곡선 알고리즘이 작동한 이유는 <math>y^2=x^3+5x-5\pmod{599}</math>는 640 (= 2<sup>7</sup> · 5)개의 점들을 가지지만, <math>y^2=x^3+5x-5\pmod{761}</math>은 777 (= 3 · 7 · 37)개의 점들을 가졌고, 640과 777은 각각 (mod 599)와 (mod 761)에서 <math>kP=\infty</math>를 만족하는 최소의 자연수 k들이었기 때문이다. 알고리즘에서 8!은 640의 배수이지만 777의 배수는 아니었으므로 (mod 599)에서 점 8!P는 존재했지만 (mod 761)에서 점 8!P는 존재하지 않게 되었다. 따라서 이 부분에서 알고리즘은 599라는 455839의 약수를 찾아내게 되어 n = 455839의 소인수분해에 성공했던 것이다.

== 변형 ==
방금 예시 문단에서 사용한 타원곡선의 종류는 바이어슈트라스 형태의 타원 곡선식인데, 실제로 약수를 찾을 때에는 몽고메리 형태의 타원 곡선식이나 뒤틀린 에드워즈 곡선 등을 이용하면 평균적으로 약수 (소인수)를 더 빨리, 그리고 더 많이 찾아낼 수 있다.

== 시간복잡도 ==
타원곡선 알고리즘의 [[시간 복잡도|시간복잡도]]는 소인수분해하고 싶은 자연수 n의 크기보다는 그 자연수의 최소의 소인수 p가 작을수록 더 잘 작동하는 알고리즘이다. 타원곡선 알고리즘의 시간복잡도는 <math>e^{(\sqrt{2}+o(1))\sqrt{\ln{p}}\sqrt{\ln{\ln{p}}}}</math>이며, 여기서 p는 자연수 n의 최소의 소인수이다.

== 이용 ==
렌스트라의 타원곡선 알고리즘은 어떤 큰 수를 소인수분해하고자 할 때 먼저 작은 소인수들을 걸러내는 데 자주 쓰이는 [[알고리즘]]이다. 또한 [[GIMPS]]에서는 타원곡선 알고리즘을 개량한 알고리즘을 이용하여 메르센 수들의 약수를 찾아내기도 하고, 최근에는 이 알고리즘의 변형 · 개량된 알고리즘도 다양하게 쓰이고 있다.

== 같이 보기 ==
* [[소인수분해|소인수분해 알고리즘]]
* [[소수판별법]]
* [https://www.alpertron.com.ar/ECM.HTM 타원곡선 알고리즘과 이차 체를 이용하여 소인수분해를 해 주는 사이트]
** Only evaluate를 누르면 계산만 해 주고, Factor를 누르면 소인수분해해 준다. 참고로 웬만한 계산 기호는 다 넣을 수 있고 컴퓨터로 할 경우 매우 빠르게 소인수분해할 수 있다.
{{수론 알고리즘}}

[[분류:소인수 분해 알고리즘]]
[[분류:유한체]]