타원형 곡선의 점 개수

타원곡선 연구의 중요한 측면은 곡선의 점을 세는 효과적인 방법을 고안하는 것이다.그렇게 하기 위한 몇 가지 접근방식이 있었으며, 고안된 알고리즘은 숫자 이론과 같은 다양한 분야의 연구에 유용한 도구임이 입증되었고, 최근에는 암호학 및 디지털 서명 인증(타원곡선 암호학과 타원곡선 DSA 참조)에서도 유용한 도구가 되었다.숫자 이론에서 그들은 디오판틴 방정식의 해결에서 중요한 결과를 가져오지만, 암호학에 관해서는, 유한한 필드 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$에 걸쳐 타원곡선의 E (${\displaystyle {\mathbb{}}_{}{}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ E$(\mathb {F} _{q}})$그룹에 대한 이산 로그 문제(DLP)의 난이도를 효과적으로 이용할 수 있게 해준다.${\displaystyle \mathb{F} _{q$ 여기서 q = p와^k p는 prime이다.알려진 대로 DLP는 공개키 암호화에 널리 사용되는 접근법이며, 이 문제를 해결하는 데 어려움이 암호체계의 보안 수준을 결정한다.이 글에서는 특히 p > 3의 큰 특성의 필드 위에 타원곡선의 점을 계수하는 알고리즘을 다룬다.작은 특성 필드 위의 곡선의 경우 p-adic 방법에 기반한 보다 효율적인 알고리즘이 존재한다.null

타원형 곡선의 점 카운트 접근법

그 문제에 대한 몇 가지 접근법이 있다.순진한 접근으로부터 시작하여, 우리는 그 주제에 관한 Schoof의 확정적 저작까지의 전개 상황을 추적하는 한편, 엘키스(1990)와 앳킨(1992)이 만든 Schoof의 알고리즘의 개선 사항도 열거한다.null

$E{\displaystyle }$ (F${\displaystyle {}_{}}$) ${\displaystyle$ E$(\mathb {F} _{q}})$ 형식의 그룹은 고려할 포인트의 수를 제한하는 Hasse로 인해 중요한 정리의 대상이 된다는$$ 사실을 여러 알고리즘에서 활용한다.Hasse의 정리에서는 E가 유한장 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$에 대한 타원 곡선일 $경우{\displaystyle }$ E${\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$)$${\$displaystyle E(\mathb {F} _{q})$의 카디널리티가 만족한다고$$ 밝히고 있다$.$

${\displaystyle E(\mathb {F} _{q}) -(q+1) \leq 2{\sqrt {q}}\,}$

순진한 접근법

가장 덜 정교한 포인트 계산에 대한 순진한 접근법에는 $필드{\displaystyle {\mathbb{}}_{}}$ F ${\displaystyle {}_{}}${\$displaystyle \mathb{F$} $_{q}$의 모든 요소를 훑어보고$$ 어떤 요소가 타원곡선의 Weierstrass 형태를 만족하는지 테스트하는 것이 포함된다.

${\displaystyle y^{2}=x^{3}+Ax+B.\,}$

예

E를² y = x³ + x + 1에서 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$를 곱한 값$(\$} $_{5$E에 점을 세기 위해 x의 가능한 값, x mod 5의 2차 잔류 값, x³ + 1 모드의 값, x + 1 모드의 값, 그리고³ x + 1 모드의 y의 값을 리스트로 작성한다.이것은 E에 대한 포인트를 산출한다.

${\displaystyle x}$	${\displaystyle x^{2}}$	${\displaystyle x^{3}+x+1}$	$(\displaystyle y}$	포인트
${\displaystyle \cHB 0}$	${\displaystyle 0}$	${\displaystyle 1}$	$(\displaystyle 1,4}$	${\displaystyle(0,1)(0,4)}$
$\displaystyle \filename 1}$	${\displaystyle 1}$	$(\displaystyle 3}$	${\displaystyle -}$	${\displaystyle -}$
$\displaystyle \property 2}$	$(\displaystyle 4}$	${\displaystyle 1}$	$(\displaystyle 1,4}$	${\displaystyle(2,1),$
$\displaystyle \cHB 3}$	$(\displaystyle 4}$	${\displaystyle 1}$	$(\displaystyle 1,4}$	${\displaystyle(3,1)(3,4)$
$\displaystyle \filency 4}$	${\displaystyle 1}$	$(\displaystyle 4}$	$(\디스플레이 스타일 2,3}$	$(4,2),(4,3)$

예: 마지막 행은 다음과 같이 계산한다.x³${\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle$ x$=4}$을(를) x + 1 mod 5에$$ 삽입하면 $결과$(3번째 열)로 4 ${\displaystyle$ 4$}$이(가) 표시된다.$y{\displaystyle }$= ${\displaystyle 2}$,${\displaystyle 3}$ ${\displaystyle$ y$=2,3}$일 경우 이 결과를 얻을 수 있다.$$ (2번째 열에서 정량 잔류물을 조회할 수 있다.)따라서 마지막 행의 포인트는${\displaystyle }$(${\displaystyle 4,}$ 2${\displaystyle }$)${\displaystyle }$,${\displaystyle }$(${\displaystyle 4,}$ ${\displaystyle 3}$) ${\displaystyle (4,2$), $(4,3)}$ 입니다$.$

따라서 $E{\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle E(\mathb {F} _{5})$의 카디널리티는 9: 이전에 열거된 8 포인트와 무한대의 포인트를 가진다.null

$이{\displaystyle }$ 알고리즘은 x${\displaystyle {}_{}}$ F$q$ {\$displaystyle x\in$ \$mathb {F}$ _{$q}$의 모든 값을 고려해야 하기$$ 때문에 실행 시간 O(q)가 필요하다.null

베이비 스텝 거인 스텝

${\displaystyle {실행\mathrm{}}^{}}$ 시간의 향상은 다른 접근법을 사용하여 얻는다: x 3${\displaystyle {}^{}}$+ ${\displaystyle A}$+ ${\displaystyle B}$${\$$displaystyle x}$의 $랜덤{\displaystyle }$ 값을 선택하여$$ $요소{\displaystyle }$ ${\displaystyle P}$=${\displaystyle }$( x${\displaystyle }$, ${\displaystyle y}$) ${\displaystyle \in }$ $(\$$displaystyle$ P$=(x,y)\in$ E$(\mathb {F}$$_{$$q})$를 선택한다.$Ax+B}$ is a square in ${\displaystyle \mathbb {F} _{q}}$ and then computing the square root of this value in order to get ${\displaystyle y}$. Hasse's theorem tells us that ${\displaystyle E(\mathbb {F} _{q}) }$ lies in the interval ${\displaystyle (q$$+1-2{\sqrt{q},q+1+2{\sqrt {q$따라서 라그랑주의 정리로는 이 간격에 놓여$$ 있는 고유한 $M{\displaystyle }$ ${\displaystyle M}$을(를) 찾고 ${\displaystyle M}$ $P{\displaystyle }$ =${\displaystyle O}$ ${\displaystyle$ MP=$O}$을$($를) 만족시키면 E($F{\displaystyle {}_{}}$ )${\displaystyle E(\mathb {F} _{q})$의 카디널리티를 찾게 된다$.$The algorithm fails if there exist two distinct integers ${\displaystyle M}$ and ${\displaystyle M'}$ in the interval such that ${\displaystyle MP=M'P=O}$. In such a case it usually suffices to repeat the algorithm with another randomly chosen point in ${\displaystyle E(\mathbb {F} _$$\{$$q}$ .

$M{\displaystyle }$ ${\displaystyle P}$= ${\displaystyle O}$ ${\displaystyle MP=O}$을(를) 만족하는 값을 찾기 위해$$ $M{\displaystyle }$ ${\displaystyle M}$의 모든 값을 시도하면 약 $4{\displaystyle \mathrm{}}$ ${\$ 4${\sqrt{q}$ 단계를$$ 거친다$$.null

단, $E{\displaystyle ({}_{}}$) ${\displaystyle E(\mathb {F} _{q}})$에 베이비스텝 거인스텝 알고리즘을 적용함으로써 약 $4{\displaystyle \mathrm{}}$ ${\displaystyle \text{exception 25:}}$ 4 ${\$단계까지$$ 속도를 낼 수 있다$.$알고리즘은 다음과 같다.null

알고리즘

1. 선택하 m{m\displaystyle}정수, m>q 4{\displaystyle m>,{\sqrt[{4}]{q}}}2.FOR{j=0{\displaystyle j=0}{m\displaystyle}m에}jP DO 3.Pj← jP{\displaystyle P_{j}\leftarrow}4.ENDFOR 5. 나는 ← 1{\displaystyle L\leftarrow 1}6.Q←(q+1)P{\displaystyle Q\le.ftarro$w (q+1)P}$ 7. REPEAT compute the points ${\displaystyle Q+k(2mP)}$ 8. UNTIL ${\displaystyle \exists j}$: ${\displaystyle Q+k(2mP)=\pm P_{j}}$  \\the ${\displaystyle x}$-coordinates are compared 9.${\displaystyle M}$ ${\displaystyle \leftarrow }$ ${\displaystyle q}$+ ${\displaystyle 1}$+ ${\displaystyle 2}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle \mp }$ j ${\displaystyle M\leftarrow q+1+2mk\mp j}$ \$$note $M{\displaystyle }$ ${\displaystyle P}$= ${\displaystyle O}$ ${\displaystyle MP=O}$ 10$$.인자 $M{\displaystyle }$ ${\displaystyle$ M$\}.$ ${\displaystyle {p\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ ${\$는 $M{\displaystyle }$ ${\$$displaystyle M}$. 11. 반면 i$$ ${\displaystyle \mathrm{11}}$ r $displaystyty$ i$\leq$ r$}$ DO$$ 12.IF $M{\displaystyle \frac{}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{i_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$= ${\displaystyle O}$ ${\displaystyle {\frac {M}{p_{i}}P=O}$ 13$$.그 다음 $M{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle M\frac{}{}}$ ${\displaystyle \frac{p_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\$ 14$$.기타 $i{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle i}$+ ${\displaystyle 1}$ ${\displaystyle$ i$\왼쪽 화살표$ i$+1}$ 15$$.16번 엔디프, 17번 엔디프.${\displaystyle L\leftarrow \operatorname {lcm} (L,M)}$     \\note ${\displaystyle M}$ is the order of the point ${\displaystyle P}$ 18. WHILE ${\displaystyle L}$ divides more than one integer ${\displaystyle N}$ in ${\displaystyle (q+1-2{\sqrt {q}$$}}q+1+2{\sqrt{q}}}$ 19. 새로운$$ $포인트{\displaystyle }$ P ${\displaystyle P}$를 선택하고$$ 1. 20. $ENDWIDY{\displaystyle }$ 21. $RETURN{\displaystyle }$ N ${\displaysty N$$}\\\\\$displaysty E(\mathb {F} _{q}}})의 카디널리티임.

알고리즘 참고 사항

• 8행. 우리는 성냥의 존재를 가정한다.실제로 다음과 같은 보조정리기로 그러한 일치가 존재함을 보장한다.

${\displaystyle a}$을(를) ${\displaystyle \le }$ ${\displaystyle {2m\mathrm{}}^{}}$ 2 ${\$ a $\leq 2m^{2}}$의 정수로 한다$$$.$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$과($)$ 1 {\$displaystystyle a_{1$}의 정수가 있다.

${\displaystyle -m<a_{0}\leq m{\mbox{{} 및 }-m\leq a_{1}\leq mbox{{{}a=a_{0}+2ma_{1}.}$

• 일단 $j{\displaystyle }$ ${\displaystyle P}$ ${\displaystyle jP}$이(가) 계산되면${\displaystyle }$($j$+${\displaystyle 1}$) ${\displaystyle P}$ ${\displaystyle$ ($j$$+1)P}$은 완전한 스칼라 곱셈을 새로$$ 계산하는 대신 j {\$displaystyle$ $jP}$에 $P{\displaystyle }$ ${\\displaysty$ jP$}$을 추가하면 된다.따라서 완전한 계산을 위해서는 $m{\displaystyle }$ ${\displaystyle m}$을(를) 추가해야 한다.${\displaystyle \mathrm{2m}}$ ${\displaystyle P}$ ${\displaystyle 2mP}$은(는) $m{\displaystyle }$ ${\displaystyle P}$ ${\displaystyle mP}$에서 두 배로 증가하여 얻을 수 있다$$$.$$Q{\displaystyle }$ ${\displaystyle Q}$을$($를) 계산하려면 ${\displaystyle \mathrm{로그}}$ ${\displaystyle (q}$ +${\displaystyle 1}$) ${\displaystyle \log(q+1$) 의심과$$ $w{\displaystyle }$ ${\displaystyle$ w$}$을(를) 추가해야 하는데$$ $여기$서 w ${\displaystyle$ w}은 $q$ +${\displaystyle 1}$ ${\$$displaystystyle$ $q+$1}의 이진 표현에서 0이 아닌 자릿수가 된다$.$ $JP}$에 대한 지식이다.$그리고{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{2m}}$ P$[\displaystyle 2mP}$는 더블링의 수를 줄일 수 있게 해준다.마지막으로 $Q{\displaystyle }$+ ${\displaystyle k}$( ${\displaystyle 2}$ m ${\displaystyle P}$) ${\displaystyle Q+k(2mP)}$에서 Q${\displaystyle }$+${\displaystyle }$( ${\displaystyle \mathrm{k}}$+ 1${\displaystyle }$)${\displaystyle }$( 2 ${\displaystyle \mathrm{m}}$ ${\displaystyle P)}$ ${\displaystyle$ Q$+(k+1)(2mP)}$까지 가려면 모든 것을 다시 계산하기보다는$$ 2 ${\displaystyle m}$ P ${\displaysty 2mP}$만 추가하면 된다$.$
• $우리$는 M ${\displaystyle M}$을(를) 인수할 수 있다고 가정하고 있다$.$ 그렇지 않다면 최소한 모든 작은 주요 요인 ${\$을(를) 찾아 M p ${\displaystyle \frac{i_{}}{}}for$ O ${\displaystyle {\p}{p_}}}\neq$ O$}$를 확인할 수 있다.그러면 $M{\displaystyle }$ ${\displaystyle M}$이(가) $P{\displaystyle }$ ${\displaystyle P}$의 순서에 적합한 후보가 될 것이다$.$
• The conclusion of step 17 can be proved using elementary group theory: since ${\displaystyle MP=O}$, the order of ${\displaystyle P}$ divides ${\displaystyle M}$. If no proper divisor ${\displaystyle {\bar {M}}}$ of ${\displaystyle M}$ realizes ${\displaystyle {\bar {M}}P=O}$$$, 그러면 $M{\displaystyle }$ ${\displaystyle M}$이(가) $P{\displaystyle }$ ${\displaystyle P}$의 순서 입니다$.$

이 방법의 한 가지 단점은 집단이 커지면 너무 많은 메모리가 필요하다는 것이다.이 문제를 해결하려면 $j{\displaystyle }$ ${\displaystyle P}$ ${\displaystyle jP}$ 지점의 $x{\displaystyle }$ ${\displaystyle jP}$ 좌표만$$ 저장하는 것이 더 효율적일 수 있다($$해당 $정수{\displaystyle }$ j ${\displaysty j}).$그러나 이 경우 -${\displaystyle j}$ ${\displaystyle -j}$과$({\displaystyle }$와) + ${\displaystyle j}$ ${\displaystyle +j}$ 중 하나를 선택하기 위해 추가 스칼라 곱으로 이어진다$.$

폴라드의 rho 알고리즘과 폴라드 캥거루 방법 등 보다 공간 효율적인 그룹 요소의 순서를 계산하는 다른 일반적인 알고리즘이 있다.폴라드 캥거루 방법은 $O{\displaystyle ({\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$${\displaystyle \text{exception 25:}}$${\displaystyle {}^{}}$ $q$ O$({\$$sqrt[{4$$}]{q}}})$의 실행 시간을 $산출$하여 정해진 간격으로 솔루션을 검색할 수 있다.null

쇼프의 알고리즘

$E형{\displaystyle ({}_{}}$) ${\displaystyle$ E$(\mathb {F} _{q}})$의 그룹 카디널리티 계산 문제에 대한 이론적 돌파구는 1985년 첫 번째 결정론적 다항식 시간 알고리즘을 발표한 레네 쇼프에 의해 달성되었다$$.스쿠프의 알고리즘의 중심은 중국 나머지 정리와 함께 분할 다항식 및 하세의 정리를 사용하는 것이다.null

Schoof의 식견. 그것은(Fq)의 나머지를 정수 N을{E(\mathbb{F}_{q})\displaystyle}E를 계산하기 위해 충분. 4q{\displaystyle N> 이렇게 4{\sqrt{q}}}. 사실, Hasse의 정리까지 가능한 값의 E(Fq){E(\mathbb{F}_{q})\displaystyle}에 유한한 범위는 T. 착취그의 것이다.${\displaystyle E}$(${\displaystyle {\mathbb{}}_{}}$ $displaystyle E(\mathb {F} _{q}} }$ modulo$$ primes ${\displaystyle {\ell \mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$… ${\displaystyle s_{}}$ ${\$ \$ell \1},\ldots,\s}}}$ $제품$을 4 ${\displaystyle q}${\displaystystyt}, 중국 나머지 정리를 적용하여 달성.알고리즘의 핵심은 분할 다항식 ${\$을(를) 사용하여 ${\displaystyle E({\mathbb{}}_{}}$ $displaystyle E(\mathb {F} _{q})}$modulo$$ $\ell {\displaystyle }$ ${\displaysty \ell }}$을 효율적으로 계산하는 것이다$.$

The running time of Schoof's Algorithm is polynomial in ${\displaystyle n=\log {q}}$, with an asymptotic complexity of ${\displaystyle O(n^{2}M(n^{3})/\log {n})=O(n^{5+o(1)})}$, where ${\displaystyle M(n)}$ denotes the complexity of integer m초절개공간 복잡성은 O($n{\displaystyle {3\mathrm{}}^{}}$ )${\displaystyle O(n^{3})}$ 입니다$.$

스쿠프-엘키스–Atkin 알고리즘

1990년대에 노암 엘키스에 이어 A. O. L. 앳킨이 사용되는 프리임$$ ${\displaystyle {imes1\mathrm{}}_{}}$,${\displaystyle {\ell }_{}}$ s ${\$ _${1},\ldots \ell _{s}$을 구별하여 Schoof의 기본 알고리즘의 개선을 고안했다.A prime ${\displaystyle \ell }$ is called an Elkies prime if the characteristic equation of the Frobenius endomorphism, ${\displaystyle \phi ^{2}-t\phi +q=0}$, splits over ${\displaystyle \mathbb {F} _{\ell }}$. Otherwise ${\displaystyle \ell }$ is called an Atkin prime.엘키 프리임은 쇼프의 알고리즘의 점증적 복잡성을 개선하는 열쇠다.Atkin primes에서 얻은 정보는 증상 없이 무시할 수 있는 추가적인 개선을 허용하지만 실제로는 상당히 중요할 수 있다.Elkies와 Atkin 프리임을 사용하도록 Schoof의 알고리즘을 수정하는 것을 Schoof-라고 한다.엘키스-앳킨(SEA) 알고리즘.null

The status of a particular prime ${\displaystyle \ell }$ depends on the elliptic curve ${\displaystyle E/\mathbb {F} _{q}}$, and can be determined using the modular polynomial ${\displaystyle \Psi _{\ell }(X,Y)}$. If the univariate polynomial ${\displaystyle \Psi _{$$\ell }(X,j(E))}$ has a root in ${\displaystyle \mathbb {F} _{q}}$, where ${\displaystyle j(E)}$ denotes the j-invariant of ${\displaystyle E}$, then ${\displaystyle \ell }$ is an Elkies prime, and otherwise it is an Atkin prime.엘키스의 경우 모듈형 다항식을 포함하는 추가 연산을 사용하여 분할 다항식 ${\$}}의 적절한 인자를 얻는다.이 인자의 정도는 $O{\displaystyle }$ (${\displaystyle \ell }$) ${\displaystyle O(\ell )}$인 반면$,$ $\psi {\displaystyle {}_{}}$ ${\displaystyle {\ell }_{}}$ ${\$은(는) $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ )${\displaystystyle O(\ell ^{2})}$이다$.$

Schoof의 알고리즘과 달리 SEA 알고리즘은 (라스베가스 유형의) 확률 알고리즘으로 구현되어 뿌리 찾기 및 기타 연산을 보다 효율적으로 수행할 수 있다.그것의 계산 복잡성은 모듈식 다항식 ${\displaystyle {\ell }_{}X}$, Y$){\디스플레이$ 스타일 $\PSI _{\ell }(X,Y$의 계산 비용에 의해 지배되지만, 이것들은 $E{\displaystyle }$ ${\displaystyle E}$에 의존하지 않기 때문에 한 번 계산되어 재사용될 수 있다$.$Under the heuristic assumption that there are sufficiently many small Elkies primes, and excluding the cost of computing modular polynomials, the asymptotic running time of the SEA algorithm is ${\displaystyle O(n^{2}M(n^{2})/\log {n})=O(n^{4+o(1)})}$, where ${\displaystyle n=\log }$${\displaystyle q}$ ${\$ n$=\log{q$ 공간 복잡성은 $O{\displaystyle ({n\mathrm{}}^{}}$ 3 ${\displaystyle \log logn}$ )${\displaystyle$ O$(n^{3}\log {n}})$이지만$,$ 사전 계산된 모듈식 다항식을 사용하면 $O{\displaystyle ({n\mathrm{}}^{}}$ 4${\displaystyle {}^{}}$) ${\displaystyle O(n^{4})$로 증가한다$.$

참고 항목

• 쇼프의 알고리즘
• 타원곡선암호법
• 베이비 스텝 거인 스텝
• 공개키암호법
• 스쿠프-엘키스–Atkin 알고리즘
• 폴라드 로
• 폴라드 캥거루
• 타원 곡선 원시성 증명

참고 문헌 목록

• I. Blake, G. Seroussi 및 N. Smart: Cryptography, Cambridge University Press, 1999. Cryptography의 타원 곡선.
• A. Enge:타원 곡선 및 암호화에 대한 응용 프로그램: 소개1999년 Dordrecht의 Kluwer Academic Publishers.
• G. Musicer: Schoof의 $E{\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle$ E$(\mathb {F} _{q}}}}.$http://www.math.umn.edu/~musiker/schoof.pdf에서 사용 가능
• R. Schoof:유한 필드 위의 타원 곡선의 점 카운팅.J. 이론.Nombres Bordeaux 7:219-254, 1995.http://www.mat.uniroma2.it/~schoof/ctg.pdf에서 이용 가능
• L. C. Washington: 타원 곡선:숫자 이론과 암호학.Chapman \& Hall/CRC, 2003년 뉴욕.

참조