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

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

알고리즘

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

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

타원곡선의 덧셈 법칙

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

• 두 점 $P(x_{P},y_{P})$와 $Q(x_{Q},y_{Q})$ (단, x_P와 x_Q의 값은 다르다)를 더한 값이 $R(x_{R},y_{R})$이라고 할 때, x_R과 y_R은 다음과 같이 구하면 된다.
  • $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})$가 된다.

• 만약 x_P=x_Q인 경우 다음과 같이 $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\equiv 1{\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}<|r_{i}|$이며, 이 조건이 q_i를 정의한다. 이 과정은 간단하게 r_i+1은 r_i-1을 r_i로 나눈 나머지, q_i는 r_i-1을 r_i로 나눈 몫이라고 생각하면 된다.)
  • $s_{i+1}=s_{i-1}-q_{i}s_{i}$
  • $t_{i+1}=t_{i-1}-q_{i}t_{i}$
• 만약 $r_{k+1}=0$이라면 확장된 유클리드의 호제법은 멈추게 되고, $r_{k}=\gcd(a,b)$가 되며 $p=s_{k}$, $q=t_{k}$가 된다.

여기서 1 < r_k < n이라면 r_k는 n의 비자명한 약수가 되고 r_k=1인 경우 t_k가 b의 역수가 된다.

원리

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

1. x₀, y₀, a는 0부터 n-1 사이의 정수 중 아무 수나 뽑으면 된다. 여기서 무작위로 이 수들을 고르면 x₀=1, y₀=1, a=5이고 $b\equiv {y_{0}}^{2}-{x_{0}}^{3}-ax_{0}\equiv 1-1-5\equiv -5{\pmod {455839}}$가 되므로 타원곡선은 $y^{2}=x^{3}+5x-5$이고 점 $P(1,1)$은 이 타원곡선 위의 점이 된다.
2. [10!]P를 계산하기로 하면 먼저 2P를 계산하고, 그 다음 3(2P), 4(3!P), ... 이런 식으로 10(9!P)까지 계산하면 된다.
   1. 2P = P+P를 계산하려면 먼저 s를 구한다. 위의 알고리즘 문단의 공식에 대입하면 s=4가 되고, 다시 위의 공식에 대입하면 2P = (14, -53)이 된다. 실제로 2P = (14, -53)은 (-53)² ≡ 14³+5·14-5 (mod 455839)가 되어 타원곡선 위의 점이 된다.
   2. 다음으로 3!P = 2P+2P+2P를 계산한다. 먼저 2P+2P를 구하면 $s=-{\frac {593}{106}}$이므로 106의 역수를 확장된 유클리드 호제법을 이용하여 구하면 81707이 된다 (즉, 106⁻¹ ≡ 81707 (mod 455839)이다). 따라서 s=-593 · 81707 ≡ 322522 (mod 455839)이고, 이 s와 위의 공식을 이용하여 2P+2P=4P를 계산하면 4P = (259851, 116255)이며 이 점 역시 원래 타원곡선 위의 점이 된다. 이 4P와 2P를 다시 더하면 3!P를 구할 수 있게 된다.
   3. 이런 식으로 반복하면 비슷한 방식으로 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 (= 2⁷ · 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를 누르면 소인수분해해 준다. 참고로 웬만한 계산 기호는 다 넣을 수 있고 컴퓨터로 할 경우 매우 빠르게 소인수분해할 수 있다.