Lenstra 타원-곡선 인자화

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 제거하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2020년 12월) (이 템플릿 메시지를 제거하는 방법 및 시기 학습)

Lenstra 타원곡선 인자화 또는 타원곡선 인자화 방법(ECM)은 타원곡선을 채용한 정수 인자화를 위한 알고리즘인 고속의 부배수 런닝 시간이다. 범용 팩토링의 경우 ECM은 세 번째로 빠르게 알려진 팩토링 방법이다. 두 번째로 빠른 것은 다항식 2차 체이고, 가장 빠른 것은 일반수 필드 체이다. Lenstra 타원 곡선 인자화는 Hendrik Lenstra의 이름을 따서 명명되었다.

현실적으로 ECM은 작은 요인을 찾기에 가장 적합하기 때문에 특수 목적의 팩토링 알고리즘으로 간주된다. 현재도^[update] 50~60자리를 넘지 않는 디비저의 알고리즘으로는 여전히 최적인데, 그 러닝타임이 인수할 숫자 n의 크기보다는 가장 작은 요인 p의 크기에 의해 지배되기 때문이다. ECM은 많은 인자를 가진 매우 큰 정수에서 작은 인자를 제거하기 위해 자주 사용된다. 나머지 정수가 여전히 복합적인 경우, 큰 인자만 가지고 있으며 범용 기법을 사용하여 인수된다. 지금까지 ECM을 사용하여 발견된 가장 큰 인자는 소수점 83개로 R. Propper에 의해 2013년 9월 7일에 발견되었다.^[1] 시험한 곡선의 수를 늘리면 인자를 찾을 가능성이 높아지지만 자릿수 증가와 선형적이지 않다.

알고리즘.

주어진 자연수 $n{\displaystyle }$ ${\displaystyle n}$의 인자를 찾기 위한 Lenstra 타원-곡선 인자화 방법은 다음과 같이 작용한다$$.

1. Pick a random elliptic curve over ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, with equation of the form ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {n}}}$ together with a non-trivial point${\displaystyle P(x_{0},y_{0})}$ on it.

   This can be done by first picking random ${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} }$, and then setting ${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}}$ to assure the point is on the curve.

2. 원곡선에서 두 점의 추가를 정의하여 그룹을 정의할 수 있다. 추가 법칙은 타원곡선에 관한 글에 제시되어 있다.

   We can form repeated multiples of a point ${\displaystyle P}$: ${\displaystyle [k]P=P+\ldots +P{\text{ (k times)}}}$. The addition formulae involve taking the modular slope of a chord joining ${\displaystyle P}$ and ${\displaystyle Q}$, and thus division between residue classes modulo $$${\displaystyle }$확장된 유클리드 알고리즘을 사용하여 수행된 n $[\displaystyle n$ 특히 일부 ${\displaystyle vmd}$ ${\displaystyle n}$ ${\$ v${\bmod{n}}$에 의한 분할에는 ${\displaystyle gcd(v}$,${\displaystyle n}$) ${\displaystyle \gcd(v,n)}$의 계산이 포함된다$.$

   Assuming we calculate a slope of the form ${\displaystyle u/v}$ with ${\displaystyle \gcd(u,v)=1}$, then if ${\displaystyle v=0{\bmod {n}}}$, the result of the point addition will be ${\displaystyle \infty }$, the point "at infinity" corresponding to the intersection of the "vertical" 연결 선 $P{\displaystyle }$( ${\displaystyle x}$, y${\displaystyle }$)${\displaystyle }$, ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( ${\displaystyle x}$,${\displaystyle }$- ${\displaystyle y}$) ${\displaystyle P(x,y),$ P$'(x,-y)}$ 및 곡선$$. 단, ${\displaystyle gcd(v}$ ,${\displaystyle n}$ )${\displaystyle \ne 1}$, n$${\$displaystyle \gcd(v,n)\neq$ 1,$n}$이$($가) 포인트 추가가 곡선에 의미 있는 포인트를 생성하지는 않지만, 더 중요한 것은 ${\displaystyle gcd(v}$,${\displaystyle n}$) ${\$$displaysty$ $\gcd(v,$$n)}$의 비특수 요소인 것이다$.$

3. Compute ${\displaystyle [k]P}$ on the elliptic curve (${\displaystyle {\bmod {n}}}$), where ${\displaystyle k}$ is a product of many small numbers: say, a product of small primes raised to small powers, as in the p-1 algorithm, or the factorial${\displaystyle B!}$ for some not too large ${\disp$$레이스타일 B$ 이것은 한 번에 하나의 작은 요소로서 효율적으로 이루어질 수 있다. ${\displaystyle 자},{\displaystyle }$ [${\displaystyle B!]}$ P ${\디스플레이 스타일$ [B$!]$를 얻으려면.$P$ 먼저${\displaystyle }$[${\displaystyle 2}$ ${\displaystyle ]}$ P ${\displaystyle [2]P}$을$($를) 계산한 다음$,{\displaystyle }$ [ ${\displaystyle 3}$ ${\displaystyle ]}$ ${\$$displaystyle$$[3]([2]P)}$을$($를) 계산한 다음$,{\displaystyle }$ [$4$ 등을 계산한다$.$ ${\displaystyle }$$B{\displaystyle }$ ${\displaystyle B}$을(를$$) 충분히 작게 선택하여 B ${\displaystyle B}$ -wise point addition을 합리적인 시간에 수행할 수 있도록 한다$$.
   • 만일 우리가 반전 ${\displaystyle 불가능}$한 요소(${\displaystyle mod}$n {\$displaystyle$ {\$bmod{n}})$를 만나지 않고 위의 모든 계산을 마치면 타원곡선(modulo primes)의 순서가 충분히 매끄럽지 않음을 의미하므로 다른 곡선과 출발점으로 다시 시도해야 한다.$$
   • ${\displaystyle gcd(v}$, ${\displaystyle n}$) ${\displaystyle \ne }$ ${\displaystyle 1}$, ${\displaystyle m}$ ${\displaystyle \gcd(v,n)\neq$1$,m}$을(를) 만나게 되면 끝낸다$$: $n{\displaystyle }$ ${\displaystyle n}$의 비경쟁 요인이다$.$

The time complexity depends on the size of the number's smallest prime factor and can be represented by exp[(√2 + o(1)) √ln p ln ln p], where p is the smallest factor of n, or ${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]}$, in L-notation.

알고리즘이 작동하는 이유는?

p와 q가 n의 두 주요 구분자라면 y² = x + 도끼³ + b(mod n)는 modulo p와 modulo q의 동일한 방정식을 의미한다. $⊞{\displaystyle }$ ${\displaystyle \boxplus }$ -addition이$$ 있는 이 두 개의 더 작은 타원형 곡선은 이제 진정한 그룹이 되었다. 라그랑주 정리의 수정으로 원래 곡선에 미칠 P점을 이 그룹 Np과 Nq하는 요소도 각각 다음, k>0는 아주 적다고는 곡선에 k.P는∞{kP=\infty\displaystyle}의 나머지를 p이 kNp을 나누는;게다가, Np.P는 ∞{\displaystyle N_{p}P=\infty}을 의미한다. 이와 유사한 진술은 curv에서나 있다.emodulo q. 타원곡선을 무작위로 선택한 경우, N과_p N은_q 각각 p + 1과 q + 1에 가까운 난수(아래 참조)이다. 따라서 N과_p N의_q 주요 요인이 대부분 같을 가능성은 낮으며, eP를 계산하는 동안 modulo q가 아니라 ∞ modulo p인 kP와 마주칠 가능성이 상당히 높다. 이 경우 kP는 원래 곡선에 존재하지 않으며, 계산에서 gcd(v,p) = p 또는 gcd(v, q) = q를 가진 일부 v를 발견했지만 둘 다 있는 것은 아니었다. 즉, gcd(v, n)는 n의 비경쟁 인자를 주었다.

ECM은 그것의 핵심에 구형 p - 1 알고리즘의 개선이다. p - 1 알고리즘은 p - 1이 b의 작은 값에 대해 b-힘이 매끄러울 정도로 primary 인자 p를 찾는다. 어떤 e, p - 1의 배수와 p에 대한 비교적 prime을 위해, 페르마의 작은 정리에 의해 우리는 1 1 (mod p)을^e 가지게 된다. 그러면 gcd(a^e - 1, n)는 n의 인자를 산출할 가능성이 있다. 그러나, 예를 들어, 강한 프리마임을 포함하는 숫자의 경우와 같이 p - 1이 큰 프라이마 인자를 가질 때 알고리즘이 실패한다.

ECM은 항상 p - 1의 순서를 갖는 Z의_p 승법 그룹을 고려하기보다는 유한장 Z에_p 대한 무작위 타원 곡선 그룹을 고려함으로써 이 장애물을 극복한다.

Z에_p 대한 타원곡선의 집단의 순서는 하세의 정리에 의해 p + 1 - 2 pp와 p + 1 + 2 √p 사이에 (임의적으로 정격) 달라지며, 일부 타원곡선의 경우 매끄러울 가능성이 있다. 하세-인터벌에서 원활한 그룹 순서가 발견될 것이라는 증거는 없지만, 경험적 확률론적 방법, 적절히 최적화된 파라미터 선택을 가진 캔필드-에르드-포머런스 정리, L-통지법을 사용함으로써, 우리는 원활한 그룹 순서를 얻기 전에 L[[2/2, √2] 곡선을 시도해 볼 수 있을 것으로 기대할 수 있다. 이 휴리스틱한 추정은 실제로 매우 신뢰할 수 있다.

예

다음은 트라페 & 워싱턴(2006)의 사례로, 몇 가지 세부사항이 추가되었다.

우리는 n = 455839를 인자화하고자 한다. 점² P = (1, 1)가³ 표시된 타원 곡선 y = x + 5x – 5를 선택하고 (10!)P를 계산해 봅시다.

A=(x, y) 지점의 접선 선의 기울기는 s = (3x² + 5)/(2y) (mod n)이다. s를 사용하여 2A를 계산할 수 있다. s 값이 a/b 형식인 경우 b > 1과 gcd(a,b) = 1이면 b의 모듈형 역수를 찾아야 한다. 존재하지 않는 경우, gcd(n,b)는 n의 비경쟁적 요인이다.

먼저 우리는 2P를 계산한다. s(P) = s(1,1) = 4이므로 2P = (xx, y′)의 좌표는 x′ = s – 2x² = 14, y′ = s(x – x′) – y = 4(1 – 14) – 1 = 1 – 53, 모든 숫자 이해(mod n)이다. 이 2P가 실제로 곡선에 있는지 확인하기 위해: (–53)² = 2809 = 14³ + 5/14 – 5

그리고 나서 우리는 3(2P)을 계산한다. 우리는 s(2P) = s(14,-53) = –593/106 (mod n)을 가지고 있다. 유클리드 알고리즘 사용: 455839 = 4300/106 + 39, 106 = 2/39 + 28, 39 = 28 + 11, 28 = 2/11 + 6, 11 = 6 + 5, 6 = 5 + 1 따라서 gcd(455839, 106) = 1, 역방향 작업(확장 유클리드 알고리즘의 버전): 1 = 6~5 = 2·6 – 11 = 2·28 – 5·11 = 7·106 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. 따라서 106⁻¹ = 81707(모드 455839), –593/106 = –133317(모드 455839)이다. 이 s를 감안하여, 위와 같이 2(2P)의 좌표를 계산할 수 있다: 4P = (259851, 116255) 이 점이 실제로 곡선상의 점인지 확인하기 위해: y² = 54514 = x³ + 5x – 5(mod 455839) 이 후, $우리$는 3${\displaystyle }$( ${\displaystyle 2P}$) = ${\displaystyle 4}$ ${\displaystyle P2}$ 2 ${\displaystyle P}$ $(\displaystyle$ 3 $(2P)=4P\boxplus 2P}$를 계산할 수 있다$.$

비슷하게 4!P 등을 계산할 수 있지만, 8!P는 599(모드 455839)를 뒤집어야 한다. 유클리드 알고리즘에 따르면 455839는 599로 분할할 수 있으며, 우리는 455839 = 599·761 인자를 발견했다.

이것이 효과가 있었던 이유는 곡선(모드 599)이 640 = 2⁷·5점이고, (모드 761)은 777 = 3·7·37점이기 때문이다. 더욱이 640과 777은 각각 곡선(mod 599)과 (mod 761)에서 kP = ∞이 될 정도로 가장 작은 양의 정수 k이다. 8!은 640의 배수지만 777의 배수는 아니기 때문에 8이 있다!P = ∞은 곡선(mod 599), 그러나 곡선(mod 761)에서는 그렇지 않으므로 반복적인 덧셈이 여기서 분해되어 인자화가 발생한다.

투영 좌표가 있는 알고리즘

투사 평면 over${\displaystyle }$(${\displaystyle Z\mathbb{}}$/ ${\displaystyle n\mathbb{}}$ ${\displaystyle Z}$)${\displaystyle }$/${\displaystyle }$~ ,${\displaystyle (\mathb {Z} /n\mathb {Z} )/\sim}$을(를) 고려하기 전에 먼저$$ ℝ 위에 '정상적인' 투사 공간을 고려한다: 점 대신 원점을 통과하는 선들을 연구한다. A line may be represented as a non-zero point ${\displaystyle (x,y,z)}$, under an equivalence relation ~ given by: ${\displaystyle (x,y,z)\sim (x',y',z')}$ ⇔ ∃ c ≠ 0 such that x' = cx, y' = cy and z' = cz. 이 동등성 관계에서 공간은 투영 평면 P ${\displaystyle {\mathrm{}}^{}}$ ${\$;${\displaystyle }$(${\displaystyle x}$: z${\displaystyle }$) ${\displaystyle (x:y:z)$로 표시된 점들은 원점을 통과하는 3차원 공간의 선에 해당한다$.$ 가능한 방향으로 선을 그리려면 x$',$y' 또는 z' 0 0 중 하나 이상이 ${\displaystyle \mathrm{필요}}$하므로${\displaystyle }$점${\displaystyle (0}$ :${\displaystyle 0}$ : 0 ) $displaystyle(0:0:0)$은 이 공간에 존재하지$$ 않는다는 점에 유의하십시오. 이제 거의 모든 선이 (X,Y,1) 면과 같은 주어진 기준면을 통과하며 선은 이 평면과 정확히 평행하게 배치되어 있음을 관찰하십시오.ates(X,Y,0)는 위에 있는 아핀(X,Y) 평면에 사용되는 '무한한 지점'으로 고유하게 방향을 지정한다.

알고리즘에서는 필드 ℝ 위에 있는 타원곡선의 그룹 구조만 사용된다. 우리가 반드시 필드 Ⅱ를 필요로 하는 것은 아니기 때문에, 유한장은 타원곡선에 그룹 구조도 제공할 것이다. 단,${\displaystyle }$(${\displaystyle Z}$/ ${\displaystyle n\mathbb{}}$ Z${\displaystyle }$)${\displaystyle }$/ ~에 대한 동일한 곡선 및 연산을 고려할 때(n이 prime이 아닌 경우$$) / ${\displaystyle(\mathb {Z}/n\mathb {Z} )/\sim }$을(를) 고려할 때 그룹이 주어지지 않는다. 타원곡선법은 가산법의 실패사례를 이용한다.

이제 알고리즘을 투영 좌표로 표시한다. The neutral element is then given by the point at infinity ${\displaystyle (0:1:0)}$. Let n be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) ${\displaystyle E(\mathbb$${Z} /n\mathb {Z}=\{(x:y:z)\in \mathb {P}^{2}\ \ y^{2}z=x^{3}+axz^{2}+bz^{3$$}$$}\}}$.

1. ${\displaystyle \ne }$ ${\displaystyle {}_{}}$이 $mathb {Z}/$ Z ${\$in$\$mathb {Z}/n$\mathb$ {$Z}을$$($를) 선택하십시오.
2. 계산 $b{\displaystyle }$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2${\displaystyle {}_{}^{}}$- ${\displaystyle {}_{}^{}}$ P ${\displaystyle {}_{}^{}}$- ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$$P}^{2}-x_{P}^{3}-ax_{P}}$. The elliptic curve E is then in Weierstrass form given by ${\displaystyle y^{2}=x^{3}+ax+b}$ and by using projective coordinates the elliptic curve is given by the homogeneous equation ${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$. It h포인트 $P{\displaystyle }$=${\displaystyle }$( ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$: ${\displaystyle \mathrm{y}}$ P${\displaystyle {}_{}}$: 1${\displaystyle }$) ${\displaystyle P=(x_{P:y_{P:1$ .
3. 이 타원형 곡선에 대해$$ 상한 $B{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle Z\mathbb{}}$ ${\$를) 선택하십시오. 비고: You will only find factors p if the group order of the elliptic curve E over ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ (denoted by ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$) is B-smooth, which means that all prime factors of ${\displaystyle \#E(\mathbb {Z} /p\mat$$hbb {Z}}$은(는) B보다 작거나 같아야 한다$$.
4. $k{\displaystyle }$= ${\displaystyle l\mathrm{}}$ ${\displaystyle \mathrm{c}}$ m${\displaystyle }$( ${\displaystyle 1}$,${\displaystyle }$… ,${\displaystyle B}$) ${\displaystyle k={\rm$ {$lcm}(1,\dots,B)}$을 계산하십시오$.$
5. Calculate ${\displaystyle kP:=P+P+\cdots +P}$ (k times) in the ring ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$. Note that if ${\displaystyle \#E(\mathbb {Z} /n\mathbb {Z} )}$ is B-smooth and n is prime (and therefore ${\displaystyle \mathbb {Z}$$/n\mathbb {Z} }$ is a field) that ${\displaystyle kP=(0:1:0)}$. However, if only ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$ is B-smooth for some divisor p of n, the product might not be (0:1:0) because addition and multiplication are not well-defined if n is not prime. 이 경우, 비종교적 구분자를 찾을 수 있다.
6. 그렇지 않으면 2단계로 돌아가십시오. 만약 이것이 일어난다면, 당신은 $제품{\displaystyle }$ k ${\displaystyle P.}$ ${\displaystyle kP$를 단순화할 때 이것을 알게 될 것이다$.$$}$

5번 지점에서는 적절한 상황에서 비독점자를 찾을 수 있다고 한다. As pointed out in Lenstra's article (Factoring Integers with Elliptic Curves) the addition needs the assumption ${\displaystyle \gcd(x_{1}-x_{2},n)=1}$. If ${\displaystyle P,Q}$ are not ${\displaystyle (0:1:0)}$ and distinct (otherwise addition works similarly, but is a little 차등), 그 후 다음과 같이 덧셈이 작동한다.

• 계산하는 방법: ${\displaystyle R}$= ${\displaystyle P}$+ Q${\displaystyle ;}$ ${\displaystyle R=P+Q;}$ $P$${\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$: ${\displaystyle \mathrm{y}}$ ${\displaystyle {1\mathrm{}}_{}}$: 1${\displaystyle }$)${\displaystyle }$, ${\displaystyle Q}$=${\displaystyle }$( ${\displaystyle {x\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$: ${\displaystyle {}_{}}$ ${\displaystyle 2{}_{}}$: 1${\displaystyle }$) ${\displaysty P=(x_{1}:1:1$),$Q=(x_{2:y_{2:1$ ,
• ${\displaystyle \lambda }$=${\displaystyle }$( y ${\displaystyle {1\mathrm{}}_{}}$- ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$( ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}{}^{}}$)${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$
• ${\displaystyle x_{}}$ ${\displaystyle {3\mathrm{}}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- x ${\displaystyle {1\mathrm{}}_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$
• ${\displaystyle y_{}}$ ${\displaystyle {3\mathrm{}}_{}}$= ${\displaystyle \lambda }$( x ${\displaystyle {1\mathrm{}}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ 3${\displaystyle {}_{}}$)${\displaystyle }$- y ${\displaystyle {1\mathrm{}}_{}}$ ${\$}-y_$\{$$1},$
• ${\displaystyle R}$= ${\displaystyle P}$+ ${\displaystyle Q}$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$: y ${\displaystyle {3\mathrm{}}_{}}$: ${\displaystyle 1}$) ${\displaystyle R=P+Q=(x_{3}:y_{3:1)}$.

If addition fails, this will be due to a failure calculating ${\displaystyle \lambda .}$ In particular, because ${\displaystyle (x_{1}-x_{2})^{-1}}$ can not always be calculated if n is not prime (and therefore ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ is not a field). $Z{\displaystyle \mathbb{}}$/ ${\displaystyle n}$ ${\displaystyle Z\mathbb{}}$ ${\$를) 필드로 사용하지$$ 않고 다음을 계산할 수 있었다.

• ${\displaystyle {\lambda }^{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}{}_{}}$- ${\displaystyle {}_{}}$ 2 ${\$
• ${\displaystyle x_{}^{}}$ ${\displaystyle {3\mathrm{}}_{}^{}}$′${\displaystyle }$= ${\displaystyle {{}^{}}^{}}$ ${\displaystyle {{\prime }^{}}^{}}$ ${\displaystyle 2^{\mathrm{}}}$- ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ (${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ 2${\displaystyle {}_{}{}^{}}$) 2${\displaystyle {}^{}}$- x ${\displaystyle {2\mathrm{}}_{}}$( x ${\displaystyle {1\mathrm{}}_{}}$- x ${\displaystyle {2\mathrm{}}_{}{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$ ${\$ '}^{2$}-x_{1}(x_{1$}-$x_{2})^{2}-x_{2$}^{2}-x_{2},{2},{2}}, $,,$ 2,}, 2,3$}$
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$,
• ${\displaystyle R}$= ${\displaystyle P}$+ Q${\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}^{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\displaystyle {}_{}^{}}$ (${\displaystyle }$x ${\displaystyle {}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$: ${\displaystyle {}_{}^{}}$ ${\displaystyle {3\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$:${\displaystyle }$( x ${\displaystyle {1\mathrm{}}_{}}$- x ${\displaystyle {2\mathrm{}}_{}{}^{}}$) ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle R=P+Q=(x_{3})(x_{1}-x_{2$}'):$y_{3}':(x_{1$}-$x_{2$ 가능하면 단순화한다.

이러한 계산은 항상 합법적이며, Z의 gcd가 n ((1 또는 n)로 조정될 경우, 단순화가 실패할 때 n의 비종교적 구분자가 발견된다.

트위스트 에드워즈 곡선

Edwards 곡선의 사용은 몽고메리 곡선 또는 Weierstrass 곡선(기타 사용된 방법)의 사용보다 모듈식 승수가 적고 시간이 짧다. Edwards 곡선을 사용하면 더 많은 프라임도 찾을 수 있다.

정의. $k{\displaystyle }$ ${\displaystyle k}$은(는) $2{\displaystyle \mathrm{}}$ ${\displaystyle \ne }$ 0 ${\displaystyle 2\neq$ 0$\}$이(가) 있는 필드로$,$ $a{\displaystyle }$, ${\displaystyle dk}$ k${\displaystyle \{}$ { $}$ {\$d\in$k\$setminus$\{$0\}$이(가) ${\displaystyle \ne }$ ${\displaystyle d}$ ${\displaystystyle a\neq d}$이(가)되도록 한다$.$ Then the twisted Edwards curve ${\displaystyle E_{E,a,d}}$ is given by ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$ An Edwards curve is a twisted Edwards curve in which ${\displaystyle a=1}$.

Edwards 곡선에 점 집합을 구축하는 방법에는 5가지 알려진 방법, 즉 부착점 집합, 투영점 집합, 반전점 집합, 확장점 집합, 완료된 점 집합이 있다.

부속 포인트의 집합은 다음과 같다.

${\displaystyle \{}$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle \in }$ ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {}^{}}$: ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle {y\mathrm{}}^{}}$= ${\displaystyle 1}$+ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ 2 ${\displaystyle {y\mathrm{}}^{}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle {}^{}}$ ${\d$ 스타일 \{($x,y)\in \mathb {A}^{2}:ax^{2}+y^{2}=1+dx^{2}y^{$2$\}\backslash \}.$

가산법은 에 의해 주어진다.

${\displaystyle (e,f),(g,h)\mapsto \left({\frac {fla+fg}{1+fghfh},{\frac {fh-aeg}{1-fh}}\right).}$

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

다른 표현은 투영적인 Weierstrass 곡선이 아핀에서 따라오는 방법과 유사하게 정의된다.

Edwards 형태의 타원형 곡선에는 순서 4가 있다. So the torsion group of an Edwards curve over ${\displaystyle \mathbb {Q} }$ is isomorphic to either ${\displaystyle \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} }$ 또는$$ Z${\displaystyle }$/ ${\displaystyle 2\mathbb{}}$ Z ${\displaystyle \times }$ Z${\displaystyle }$/ ${\displaystyle 8\mathbb{}}$ Z ${\$$}$ .

The most interesting cases for ECM are ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$ and ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$, since they force the group orders of the curve modulo primes to be divisible by 12 and 16 respectively. 다음 곡선에는 $Z{\displaystyle \mathbb{}}$/ ${\displaystyle 12}$ ${\displaystyle Z}$에 대한 비틀림 그룹 이형성이 있다$(\backslash$$displaystyle \mathb {Z} /12\mathb {Z}).$

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

순서 3의 포인트가 있는 모든 Edwards 곡선은 위에 표시된 방법으로 작성할 수 있다. Curves with torsion group isomorphic to ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$ and ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$ may be more efficient at finding primes.^[2]

2단계

위의 텍스트는 타원 곡선 인자화의 첫 번째 단계에 관한 것이다. There one hopes to find a prime divisor p such that ${\displaystyle sP}$ is the neutral element of ${\displaystyle E(\mathbb {Z} /p\mathbb {Z} )}$. In the second stage one hopes to have found a prime divisor q such that ${\displaystyle sP}$ has small prime order in ${\displayst$$yle E(\mathb {Z} /q\mathb {Z}$ $)\}.$

우리는 B ${\displaystyle {1\mathrm{}}_{}}$ ${\$}와$$ ${\displaystyle {B\mathrm{}}_{}}2{\displaystyle {}_{}}$ {\$displaystyle B_{1}$사이에 오더가 되길 바라며$,$ 여기서 $B{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}는$$1단계에서 결정되고$$ B ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}는 새로운$$ 2단계 매개 변수다. $s{\displaystyle }$ ${\displaystyle P}$ ${\displaystyle sP}$의$$소량 주문 확인은 (${\displaystyle l}$ ${\displaystyle s}$) ${\displaystyle P}$ ${\displaystyle (ls)$ 계산으로 할 수 있다.$각$prime l에 대해 P} modulo$$ n.

GMP-ECM 및 EECM-MPFQ

ECM의 최적화된 구현을 제공하기 위해 Bernstein 외 연구진이^[2] Twisted Edwards 타원곡선 및 기타 기법을 사용하였다. 유일한 단점은 보다 범용적인 구현인 짐머만의 GMP-ECM보다 더 작은 복합적인 숫자로 작업한다는 점이다.

과속-곡선법(HECM)

최근 정수를 인자화하기 위해 초고속 곡선을 사용하는 것이 발전하고 있다. 코셋은 (2010년) 기사에서 2속(그러므로 f가 5인$$ $원곡선{\displaystyle {}^{}}$ y${\displaystyle {}^{}}$= ${\displaystyle f}$( $){\displaystyle$ y$^{2}=f(x)})$으로 과급 곡선을 구축할 수 있다는 것을 보여주는데, 이는 두 개의 "정상" 타원곡선을 동시에 사용하는 것과 같은 결과를 준다. 쿠메르 표면을 사용함으로써 계산이 더 효율적이다. 과대망상곡선의 단점(타원형 곡선과는 반대)은 이러한 대체적인 계산방법에 의해 보상된다. 따라서 Cosset은 인수화를 위해 과대망상 곡선을 사용하는 것이 타원형 곡선을 사용하는 것과 다를 바 없다고 대략 주장한다.

양자 버전(GEECM)

번스타인, 헤닝거, 루, 발렌타인은 에드워즈 곡선이 있는 ECM의 양자 버전인 GEECM을 제안한다.^[3] 그것은 Grover의 알고리즘을 사용하여 표준 EECM과 비교했을 때 발견되는 프리타임의 길이를 대략 두 배로 늘리며, EECM을 실행하는 고전적인 컴퓨터와 충분한 qubit와 비슷한 속도를 가진 양자 컴퓨터를 가정한다.

참고 항목

• 실용 프로그램을 위한 UBASIC (ECMX).

참조

• Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). "ECM using Edwards curves". Mathematics of Computation. 82 (282): 1139–1179. doi:10.1090/S0025-5718-2012-02633-0. MR 3008853.
• Bosma, W.; Hulst, M. P. M. van der (1990). Primality proving with cyclotomy. Ph.D. Thesis, Universiteit van Amsterdam. OCLC 256778332.
• Brent, Richard P. (1999). "Factorization of the tenth Fermat number". Mathematics of Computation. 68 (225): 429–451. Bibcode:1999MaCom..68..429B. doi:10.1090/S0025-5718-99-00992-8. MR 1489968.
• Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Vol. 138. Berlin: Springer-Verlag. doi:10.1007/978-3-662-02945-9. ISBN 978-0-387-55640-6. MR 1228206.
• Cosset, R. (2010). "Factorization with genus 2 curves". Mathematics of Computation. 79 (270): 1191–1208. arXiv:0905.2325. Bibcode:2010MaCom..79.1191C. doi:10.1090/S0025-5718-09-02295-9. MR 2600562.
• Lenstra, A. K.; Lenstra Jr., H. W., eds. (1993). The development of the number field sieve. Lecture Notes in Mathematics. Vol. 1554. Berlin: Springer-Verlag. doi:10.1007/BFb0091534. ISBN 978-3-540-57013-4. MR 1321216.
• Lenstra Jr., H. W. (1987). "Factoring integers with elliptic curves" (PDF). Annals of Mathematics. 126 (3): 649–673. doi:10.2307/1971363. hdl:1887/2140. JSTOR 1971363. MR 0916721.
• Pomerance, Carl; Crandall, Richard (2005). Prime Numbers: A Computational Perspective (Second ed.). New York: Springer. ISBN 978-0-387-25282-7. MR 2156291.
• Pomerance, Carl (1985). "The quadratic sieve factoring algorithm". Advances in Cryptology, Proc. Eurocrypt '84. Lecture Notes in Computer Science. Vol. 209. Berlin: Springer-Verlag. pp. 169–182. doi:10.1007/3-540-39757-4_17. ISBN 978-3-540-16076-2. MR 0825590.
• Pomerance, Carl (1996). "A Tale of Two Sieves" (PDF). Notices of the American Mathematical Society. 43 (12): 1473–1485. MR 1416721.
• Silverman, Robert D. (1987). "The Multiple Polynomial Quadratic Sieve". Mathematics of Computation. 48 (177): 329–339. doi:10.1090/S0025-5718-1987-0866119-8. MR 0866119.
• Trappe, W.; Washington, L. C. (2006). Introduction to Cryptography with Coding Theory (Second ed.). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5. MR 2372272.
• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 173–190. ISBN 978-1-4704-1048-3.
• Watras, Marcin (2008). Cryptography, Number Analysis, and Very Large Numbers. Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564.

외부 링크

• ECM을 사용하고 더 빠를 때 자체 초기화 2차 체로 전환하는 자바 애플릿인 타원곡선법을 이용한 인자화.
• ECM의 효율적인 구현인 GMP-ECM.
• ECMNet, 여러 요인화 프로젝트와 함께 작동하는 쉬운 클라이언트-서버 구현.
• ECM의 파이크(pyecm) 구현. 싸이코 및/또는 gmpy로 훨씬 더 빠르게.
• 분산 컴퓨팅 프로젝트 yoyo@Home Subproject ECM은 여러 프로젝트에서 서로 다른 종류의 숫자에 대한 인자를 찾기 위해 사용하는 타원 곡선 인자화 프로그램이다.
• Lenstra 타원 곡선 인자화 알고리즘 소스 코드 단순 C 및 GMP 타원 곡선 인자화 알고리즘 소스 코드
• EECM-MPFQ MPFQ 유한 필드 라이브러리로 작성된 Edwards 곡선을 사용하여 ECM 구현.