렌스트라의 타원곡선 알고리즘

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

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

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

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

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

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

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

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

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

여기서 1 k k는 n의 비자명한 약수가 되고 rk=1인 경우 tk가 b의 역수가 된다.

## 원리
만약 p와 q가 n의 소인수라고 하면, y^2=x^3+ax+b\pmod{n}은 (mod n)을 (mod p)나 (mod q)로 바꾸어도 똑같은 해들을 가지게 된다. 이 두 새 타원곡선들에서 타원곡선 위의 점들을 더해 나가 얻어낸 해들은 군을 이루게 되는데, 만약 이 두 군이 각각 Np, Nq개의 원소를 가지고 있다면 라그랑주의 정리에 의해 원래 타원곡선의 아무 점 P에 대해서 k>0이면서 kP=\infty (mod p)인 최소의 k가 존재하고 이 k는 Np를 나누게 되며 N_pP=\infty이 된다. 또한 이 논리는 (mod q)인 경우에도 그대로 적용할 수 있다. 여기서 원래의 타원곡선이 무작위로 골라진다면 Np와 Nq는 각각 p+1과 q+1에 근접한 어떤 수가 되고, 이때 Np의 소인수들과 Nq의 소인수들은 대부분 다른 수가 된다. 따라서 이 차이에 의해 만약 우리가 임의의 수 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를 소인수분해하고 싶다고 하자.

# x0, y0, a는 0부터 n-1 사이의 정수 중 아무 수나 뽑으면 된다. 여기서 무작위로 이 수들을 고르면 x0=1, y0=1, a=5이고 b\equiv {y_0}^2-{x_0}^3-ax_0\equiv1-1-5\equiv-5 \pmod{455839}가 되므로 타원곡선은 y^2=x^3+5x-5이고 점 P(1, 1)은 이 타원곡선 위의 점이 된다.
# [10!]P를 계산하기로 하면 먼저 2P를 계산하고, 그 다음 3(2P), 4(3!P), ... 이런 식으로 10(9!P)까지 계산하면 된다.
## 2P = P+P를 계산하려면 먼저 s를 구한다. 위의 알고리즘 문단의 공식에 대입하면 s=4가 되고, 다시 위의 공식에 대입하면 2P = (14, -53)이 된다. 실제로 2P = (14, -53)은 (-53)2 ≡ 143+5·14-5 (mod 455839)가 되어 타원곡선 위의 점이 된다.
## 다음으로 3!P = 2P+2P+2P를 계산한다. 먼저 2P+2P를 구하면 s=-\frac{593}{106}이므로 106의 역수를 확장된 유클리드 호제법을 이용하여 구하면 81707이 된다 (즉, 106−1 ≡ 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이 된다.

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

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

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

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

## 같이 보기
* 소인수분해 알고리즘
* 소수판별법
* 타원곡선 알고리즘과 이차 체를 이용하여 소인수분해를 해 주는 사이트
** Only evaluate를 누르면 계산만 해 주고, Factor를 누르면 소인수분해해 준다. 참고로 웬만한 계산 기호는 다 넣을 수 있고 컴퓨터로 할 경우 매우 빠르게 소인수분해할 수 있다.

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