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

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
3. 원리
4. 예시
5. 변형
6. 시간 복잡도
7. 이용
8. 2단계
9. 양자 버전 (GEECM)
10. 초타원 곡선 방법 (HECM)
참조

1. 개요

렌스트라의 타원곡선 알고리즘(Elliptic curve method, ECM)은 주어진 자연수를 소인수분해하는 데 사용되는 알고리즘이다. 임의의 타원곡선을 선택하고, 타원곡선 덧셈 법칙을 반복적으로 적용하여 소인수를 찾는다. 알고리즘은 확장된 유클리드 호제법과 타원곡선의 덧셈 법칙을 기반으로 하며, 덧셈 과정에서 분모의 역수를 구할 수 없거나, 타원곡선 위의 점을 계산할 수 없는 경우, n의 비자명한 약수를 발견하고 알고리즘을 종료한다. ECM은 작은 소인수를 빠르게 찾는데 유용하며, 시간 복잡도는 최소 소인수의 크기에 영향을 받는다. ECM은 2단계 과정을 포함하며, 변형된 타원곡선 및 다른 알고리즘과 결합하여 효율성을 높일 수 있다. 또한, 양자 컴퓨터를 위한 버전과 초타원 곡선을 사용한 방법도 개발되었다.

더 읽어볼만한 페이지

소인수 분해 알고리즘 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
소인수 분해 알고리즘 - 연분수 소인수분해 알고리즘
연분수 소인수분해 알고리즘은 합성수 $n$ 의 제곱근을 연분수로 전개하여 얻은 값으로 $x^2 \equiv y^2 \pmod n$ 를 만족하는 $x$ 와 $y$ 를 찾아 $n$ 의 약수를 구하는 알고리즘이다.
유한체 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
유한체 - 순환 중복 검사
순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.

렌스트라의 타원곡선 알고리즘
알고리즘 정보
종류	정수 인수 분해 알고리즘
개발자	헨드릭 렌스트라
발표 시기	1987년
시간 복잡도 (발견적)	L(n, 1/2, O(1))
공간 복잡도	O(n)
세부 정보
아이디어	n의 인수 분해는 n을 법으로 하는 타원 곡선의 그룹 구조에 따라 달라진다. Pollard의 p-1 알고리즘과 유사하지만, 페르마의 작은 정리에 의존하는 대신, 타원 곡선 그룹의 크기에 의존한다.
장점	가장 작은 소인수 p에 대해 실행 시간이 민감하다.
특징	나눗셈을 사용하지 않고도 최대공약수 계산으로 대체하여 여러 숫자를 동시에 인수 분해할 수 있다. 제곱인수가 없는 합성 숫자에 대해 더 잘 작동한다.

2. 알고리즘

렌스트라 타원곡선 알고리즘은 주어진 자연수 n을 소인수분해하기 위한 알고리즘이다. 모든 연산은 (mod n)을 기준으로, 즉 n으로 나눈 나머지를 취하여 계산한다.

알고리즘의 핵심은 무작위로 선택된 타원 곡선과 그 위의 점을 이용하여 n의 약수를 찾는 것이다. 이 과정에서 확장된 유클리드 호제법이 중요한 역할을 한다. 타원 곡선 위의 점 덧셈 과정에서 분모의 역수를 구할 수 없는 경우가 발생하는데, 이때 분모와 n의 최대공약수가 n의 비자명한 약수가 된다.

만약 $[k]P$ (여기서 k는 여러 작은 소인수들을 많이 가지고 있는 자연수)를 계산하는 과정에서 비자명한 약수를 찾지 못하면, 다른 타원 곡선과 시작점을 선택하여 알고리즘을 다시 실행하거나, 폴라드 로 알고리즘이나 이차 체와 같은 다른 소인수분해 알고리즘을 사용할 수 있다.

2. 1. 기본 단계

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

# 무작위로 타원곡선을 하나 고른다. 타원 곡선은 y²=x³+ax+b^영어 형태이며, 이 타원 곡선의 비자명한 점 P(x₀, y₀)^영어을 구한다. 이 과정은 무작위로 x₀, y₀, a∈ Z/nZ^영어인 정수 x₀, y₀, a를 고른 후, b≡ y₀²-x₀³-ax₀ (mod n)^영어를 구하면 된다.

# '타원곡선의 덧셈 법칙' 문단에 나오는 s를 이용하여 [k]P=P+P+...+P^영어 (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^영어를 다 계산했는데 비자명한 약수가 나오지 않았다면 다른 x₀, y₀, a, b를 고른 후 이 알고리즘을 다시 실행하거나, 폴라드 로 알고리즘이나 이차 체 같은 다른 소인수분해 알고리즘으로 n을 소인수분해한다.

2. 2. 확장된 유클리드 호제법

타원곡선 알고리즘에서 (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의 역수가 된다.^[1]

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

$r_0=a, r_1=b$ 이고 $s_0=1, s_1=0$ 이며, $t_0=0, t_1=1$ 이라고 초깃값을 설정한다.^[1]
다음 점화식에 따라 r, s, t를 계산해 나간다.^[1]
$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로 나눈 몫이라고 생각하면 된다.)^[1]
$s_{i+1}=s_{i-1}-q_is_i$ ^[1]
$t_{i+1}=t_{i-1}-q_it_i$ ^[1]
만약 $r_{k+1}=0$ 이라면 확장된 유클리드의 호제법은 멈추게 되고, $r_k=\gcd(a, b)$ 가 되며 $p=s_k$ , $q=t_k$ 가 된다.^[1]

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

2. 3. 타원곡선의 덧셈 법칙

타원곡선 위의 두 점 P(x_P, y_P)와 Q(x_Q, y_Q)를 더하여 R(x_R, y_R)을 구하는 법칙은 다음과 같다. 모든 과정에서는 n으로 나눈 나머지만을 생각한다.

x_P ≠ x_Q인 경우:

1. s = (y_P - y_Q) / (x_P - x_Q)를 계산한다.

2. 만약 s가 정수가 아니라면, 확장된 유클리드 호제법을 이용하여 분모 (x_P - x_Q)의 모듈러 역원을 구한 후, 이 역수를 (y_P - y_Q)에 곱하여 s를 구한다.

3. x_R = s² - x_P - x_Q, y_R = y_P + s(x_R - x_P)로 계산한다.

x_P = x_Q인 경우:

1. s = (3x_P² + a) / (2y_P)를 계산한다. (여기서 a는 타원곡선 방정식 y² = x³ + ax + b의 계수이다.)

2. 만약 s가 정수가 아니라면, 확장된 유클리드 호제법을 이용하여 분모 (2y_P)의 모듈러 역원을 구한 후, 이 역수를 (3x_P² + a)에 곱하여 s를 구한다.

3. x_R = s² - 2x_P, y_R = y_P + s(x_R - x_P)로 계산한다.

s를 계산하는 과정에서 분모의 역수를 구할 수 없다면, 분모와 n의 최대공약수가 n의 비자명한 약수가 된다.^[2]

3. 원리

소인수분해하고 싶은 자연수를 n이라 하자. 렌스트라의 타원곡선 알고리즘은 n의 서로 다른 소인수 p, q에 대해, 타원곡선은 (mod p)와 (mod q)에서 각각 군을 형성한다는 사실을 이용한다. 이 두 군은 각각 N_p와 N_q개의 원소를 가지는데, 타원 곡선이 무작위로 골라진다면 N_p와 N_q는 각각 p+1과 q+1에 근접한 어떤 수가 되고, 이때 N_p의 소인수들과 N_q의 소인수들은 대부분 다른 수가 된다.^[1]

임의의 수 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)를 제공한다.^[1]

이 알고리즘의 구체적인 작동 방식은 다음과 같다.^[1]

1. 무작위로 타원곡선 $y^2=x^3+ax+b$ 와 그 위의 점 $P(x_0, y_0)$ 을 고른다. 이는 무작위로 $x_0, y_0, a\in \Z/n\Z$ 인 정수 x₀, y₀, a를 고른 후, $b\equiv y_0^2-x_0^3-ax_0\pmod{n}$ 를 계산하여 얻을 수 있다.

2. '타원곡선의 덧셈 법칙'을 이용하여 $[k]P=P+P+...+P$ (k번 더한다)를 계산한다. 여기서 k는 여러 작은 소인수들을 많이 가지고 있는 자연수이며, 간단히 충분히 작은 수 B를 이용하여 k=B!라고 할 수 있다.

3. s를 구하는 과정에서 분수 형태로 나온다면 확장된 유클리드 호제법을 이용해서 분모의 역수를 구한다. 만약 분모의 역수가 존재하지 않고 분모와 n의 최대공약수가 1보다 크면서 n보다 작을 때, 이 최대공약수가 n의 비자명한 약수가 된다.

4. 만약 $[k]P$ 를 다 계산했는데 비자명한 약수가 나오지 않았다면 다른 x₀, y₀, a, b를 고른 후 이 알고리즘을 다시 실행하거나, 폴라드 로 알고리즘이나 이차 체 같은 다른 소인수분해 알고리즘으로 n을 소인수분해한다.

이는 폴라드 p-1 알고리즘을 개선한 것이다. 폴라드 p-1 알고리즘은 p-1이 작은 값의 b에 대해 b-powersmooth인 소인수 p를 찾는 알고리즘이다. ECM은 '''Z'''_''p''의 곱셈군을 고려하는 대신, '''Z'''_''p'' 위의 임의의 타원 곡선의 군을 고려하여 p-1이 큰 소인수를 갖는 경우에도 작동하도록 개선되었다.^[1]

4. 예시

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\equiv1-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) 순서로 계산한다.

2P = P+P를 계산하기 위해 s를 구한다. s=4가 되고, 2P = (14, -53)이 된다. 실제로 2P = (14, -53)은 (-53)² ≡ 14³+5·14-5 (mod 455839)를 만족하여 타원곡선 위의 점이 된다.
다음으로 3!P = 2P+2P+2P를 계산한다. 먼저 2P+2P를 구하면 $s=-\frac{593}{106}$ 이 된다. 확장 유클리드 호제법을 이용하여 106의 역수를 구하면 81707이 된다 (즉, 106⁻¹ ≡ 81707 (mod 455839)). 따라서 s=-593 · 81707 ≡ 322522 (mod 455839)이고, 4P = (259851, 116255)를 얻는다. 이 점 역시 원래 타원곡선 위의 점이 된다. 이 4P와 2P를 더하면 3!P를 구할 수 있다.
이와 같은 방식으로 4!P, 5!P, 6!P 등을 구할 수 있다. 하지만 8!P를 구하는 과정에서 599의 역수를 구해야 하는데, 확장된 유클리드 알고리즘을 통해 n = 455839가 599로 나누어 떨어진다는 것을 알 수 있다. 455839/599=761이고, 두 수는 모두 소수이므로 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의 소인수분해에 성공한다.

5. 변형

바이어슈트라스 형태의 타원곡선 외에도, 몽고메리 곡선이나 뒤틀린 에드워즈 곡선 등을 사용하면 평균적으로 약수(소인수)를 더 빠르고 많이 찾아낼 수 있다.^[2]

만약 ''p''와 ''q''가 ''n''의 두 소수 약수이면, $y^2 = x^3 + ax + b \pmod n$ 은 동일한 방정식이 $y^2 = x^3 + ax + b \pmod p$ 와 $y^2 = x^3 + ax + b \pmod q$ 에서도 성립함을 의미한다. $\boxplus$ -덧셈을 갖는 이 두 개의 작은 타원 곡선은 이제 진정한 군이다. 만약 이 군들이 각각 ''N''_''p''와 ''N_q''개의 원소를 가진다면, 원래 곡선상의 어떤 점 ''P''에 대해, 라그랑주의 정리에 따라, $k > 0$ 는 곡선 modulo ''p''에서 $kP=\infty$ 가 ''k''가 ''N''_''p''를 나누는 최소값이다. 게다가 $N_p P=\infty$ 이다. 유사한 진술은 곡선 modulo ''q''에 대해서도 성립한다. 타원 곡선이 무작위로 선택될 때, ''N''_''p''와 ''N''_''q''는 각각 $p + 1$ 과 $q + 1$ 에 가까운 무작위 숫자이다. 따라서 ''N''_''p''와 ''N''_''q''의 대부분의 소인수가 동일할 가능성은 낮으며, ''eP''를 계산하는 동안, ∞ $\pmod p$ 이지만 $\pmod q$ 는 아닌 어떤 ''kP''를 만날 가능성이 매우 높거나 그 반대의 경우도 마찬가지다. 이 경우, ''kP''는 원래 곡선에 존재하지 않으며, 계산 과정에서 $\gcd(v, p) = p$ 또는 $\gcd(v, q) = q$ 둘 중 하나가 성립하지만 둘 다 성립하지 않는 어떤 ''v''를 찾게 된다. 즉, $\gcd(v, n)$ 은 ''n''의 비자명한 인수를 제공한다.

ECM은 본질적으로 이전 p-1 알고리즘을 개선한 것이다. p-1 알고리즘은 $p - 1$ 이 작은 값의 ''b''에 대해 b-powersmooth인 소인수 ''p''를 찾는다. 어떤 ''e''에 대해서, $p - 1$ 의 배수이고, ''p''와 서로소인 어떤 ''a''에 대해, 페르마의 소정리에 의해 $a^e \equiv 1 \pmod p$ 이 성립한다. 그러면 $\gcd(a^e - 1, n)$ 는 ''n''의 인수를 생성할 가능성이 높다. 그러나 이 알고리즘은 $p - 1$ 이 큰 소인수를 가질 때, 예를 들어 강한 소수를 포함하는 숫자와 같은 경우에 실패한다.

ECM은 항상 차수가 $p - 1$ 인 '''Z'''_''p''의 곱셈 군을 고려하는 대신, '''Z'''_''p'' 위의 임의의 타원 곡선의 군을 고려함으로써 이러한 장애를 해결한다.

'''Z'''_''p'' 위의 타원 곡선의 군의 차수는 하세의 정리에 의해 $p + 1 - 2\sqrt{p}$ 와 $p + 1 + 2\sqrt{p}$ 사이에서 (다소 무작위로) 변하며, 어떤 타원 곡선에 대해서는 스무스할 가능성이 높다. Hasse-구간에서 스무스한 군의 차수가 발견될 것이라는 증명은 없지만, 휴리스틱 확률적 방법을 사용하고, 적절하게 최적화된 매개변수 선택과 L-notation을 통해, 스무스한 군의 차수를 얻기 전에 $L[\sqrt{2}/2, \sqrt{2}]$ 개의 곡선을 시도할 것으로 예상할 수 있다. 이 휴리스틱 추정은 실제에서 매우 신뢰할 수 있다.

에드워드 곡선의 사용은 몽고메리 곡선 또는 바이어슈트라스 곡선을 사용하는 것보다 더 적은 모듈러 곱셈과 더 적은 시간을 필요로 한다. 에드워드 곡선을 사용하면 더 많은 소수를 찾을 수도 있다.

'''정의.''' $k$ 를 $2 \neq 0$ 인 체라고 하고, $a, d \in k\setminus\{0\}$ with $a \neq d$ 라고 하자. 그러면 뒤틀린 에드워드 곡선 $E_{E,a,d}$ 는 $ax^2 + y^2 = 1 + dx^2y^2$ 로 주어진다. 에드워드 곡선은 $a = 1$ 인 뒤틀린 에드워드 곡선이다.

에드워드 곡선에 점 집합을 구축하는 데에는 다섯 가지 알려진 방법이 있다. 아핀 점 집합, 투영 점 집합, 반전 점 집합, 확장 점 집합 및 완료 점 집합이다.

아핀 점 집합은 다음과 같이 주어진다.

: $\{(x,y) \in \mathbb{A}^2 : ax^2 + y^2 = 1 + dx^2y^2\}$ .

덧셈 법칙은 다음과 같이 주어진다.

: $(e,f),(g,h) \mapsto \left(\frac{eh+fg}{1+degfh},\frac{fh-aeg}{1-degfh}\right).$

점 (0,1)은 중립 요소이고 $(e,f)$ 의 역원은 $(-e,f)$ 이다.

다른 표현은 아핀에서 투영 바이어슈트라스 곡선이 나오는 방식과 유사하게 정의된다.

에드워드 형태의 모든 타원 곡선은 4차의 점을 갖는다. 따라서 $\mathbb{Q}$ 위의 에드워드 곡선의 비틀림 군은 $\mathbb{Z}/4\mathbb{Z}, \mathbb{Z}/8\mathbb{Z}, \mathbb{Z}/12\mathbb{Z}, \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}$ 또는 $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z}$ 와 동형이다.

ECM에 가장 흥미로운 경우는 $\mathbb{Z}/12\mathbb{Z}$ 및 $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z}$ 인데, 이는 소수에 대한 곡선의 군의 차수가 각각 12와 16으로 나누어지도록 강제하기 때문이다. 다음 곡선은 $\mathbb{Z}/12\mathbb{Z}$ 와 동형인 비틀림 군을 갖는다.

$x^2 + y^2 = 1 + dx^2y^2$ with point $(a,b)$ where $b \notin\{-2,-1/2,0,\pm1\}, a^2=-(b^2+2b)$ and $d=-(2b+1)/(a^2b^2)$
$x^2 + y^2 = 1 + dx^2y^2$ with point $(a,b)$ where $a=\frac{u^2-1}{u^2+1}, b=-\frac{(u-1)^2}{u^2+1}$ and $d=\frac{(u^2+1)^3(u^2-4u+1)}{(u-1)^6(u+1)^2}, u\notin\{0,\pm1\}.$

3차의 점이 있는 모든 에드워드 곡선은 위에 표시된 방식으로 작성할 수 있다.

\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z}

및

\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}

와 동형인 비틀림 군을 가진 곡선은 소수를 찾는 데 더 효율적일 수 있다.^[2]

베른스타인 등^[2]은 트위스티드 에드워드 타원 곡선 및 기타 기술을 사용하여 ECM의 최적화된 구현을 제공했다. 단점은 Zimmerman의 보다 범용적인 구현인 GMP-ECM보다 작은 합성수에 대해서만 작동한다는 것이다.

6. 시간 복잡도

시간 복잡도는 소인수분해하려는 자연수 n의 크기보다 최소 소인수 p의 크기에 더 크게 의존한다. 시간 복잡도는 $e^{(\sqrt{2}+o(1))\sqrt{\ln{p}}\sqrt{\ln{\ln{p}}}}$ 또는 L-notation에서 $L_p\left[\frac{1}{2},\sqrt{2}\right]$ 로 표현된다.^[2]

7. 이용

렌스트라의 타원곡선 알고리즘(ECM)은 큰 수의 작은 소인수를 찾는 데 효과적인 방법이다. 특히, GIMPS와 같은 프로젝트에서는 이 알고리즘을 개선하여 메르센 수의 약수를 찾는 데 활용한다.^[2] 또한, 최근에는 ECM의 다양한 변형 및 개선된 알고리즘들이 개발되어 사용되고 있다.

ECM은 기본적으로 p-1 알고리즘의 개선된 형태이다. p-1 알고리즘은 ''p''-1이 작은 값의 ''b''에 대해 ''b''-powersmooth인 소인수 ''p''를 찾는 방식이지만, ''p''-1이 큰 소인수를 가지면 실패할 수 있다. ECM은 '''Z'''_''p''의 곱셈 군 대신 '''Z'''_''p'' 위의 임의의 타원 곡선의 군을 고려하여 이 문제를 해결한다.

8. 2단계

1단계에서 소인수를 찾지 못한 경우, 2단계를 수행할 수 있다. 2단계에서는 $sP$ 가 $E(\mathbb{Z}/q\mathbb{Z})$ 에서 작은 소수 차수를 갖는 소인수 q를 찾는다. $B_1$ 과 $B_2$ 사이의 소수 l에 대해 $(ls)P$ 를 계산하여 확인한다.^[1]

9. 양자 버전 (GEECM)

번스타인, 헤닝어, Lou, 그리고 Valenta는 에드워드 곡선을 사용하는 ECM의 양자 버전인 GEECM을 제안했다.^[3] 이 알고리즘은 충분한 큐비트와 EECM을 실행하는 고전적인 컴퓨터와 비슷한 속도를 가진 양자 컴퓨터를 가정하여, 그로버 알고리즘을 사용하여 표준 EECM에 비해 찾아낸 소수의 길이를 대략 두 배로 늘린다.

10. 초타원 곡선 방법 (HECM)

종수 2의 초타원 곡선을 이용한 HECM은 두 개의 "일반" 타원 곡선을 동시에 사용하는 것과 유사한 결과를 제공한다. 2010년 코세(Cosset)는 차수가 5인 f|f^영어에 대한 $y^2 = f(x)$ 곡선 형태인 종수 2의 초타원 곡선을 구성할 수 있음을 보였다.^[1] 쿠머 곡면을 사용하면 계산이 더 효율적이다.^[1] 초타원 곡선의 단점(타원 곡선 대비)은 이러한 대안적인 계산 방식으로 보완된다.^[1] 따라서 코세는 소인수분해에 초타원 곡선을 사용하는 것이 타원 곡선을 사용하는 것보다 대략적으로 나쁘지 않다고 주장한다.^[1]

참조

_[1] 웹사이트 50 largest factors found by ECM http://www.loria.fr/[...]
_[2] 웹사이트 ECM Using Edwards Curves https://eprint.iacr.[...] 2008-01-09
_[3] 간행물 Post-quantum RSA https://eprint.iacr.[...] Springer, Cham 2017

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com