슈프의 알고리즘

슈프의 알고리즘은 유한장 위의 타원 곡선 위의 점들을 세는 효율적인 알고리즘입니다. 이 알고리즘은 타원 곡선 암호학에서 응용되며, 타원 곡선의 점 그룹에서 이산 로그 문제를 푸는 어려움을 판단하기 위해 점의 수를 아는 것이 중요합니다.

이 알고리즘은 1985년 르네 쇼프(René Schoof)에 의해 발표되었으며 타원 곡선에서 점을 세는 최초의 결정론적 다항 시간 알고리즘이었기 때문에 이론적인 돌파구였습니다. 슈프의 알고리즘 이전에는 순진하고 아기 단계의 거대 단계 알고리즘과 같은 타원 곡선에서 점을 세는 접근 방식은 대부분 지루하고 지수적인 실행 시간을 가졌습니다.

이 글은 슈프의 접근 방식을 설명하면서 알고리즘의 구조에 기초한 수학적 아이디어를 강조합니다.

서론

Let ${\displaystyle E}$ be an elliptic curve defined over the finite field ${\displaystyle \mathbb {F} _{q}}$, where ${\displaystyle q=p^{n}}$ for ${\displaystyle p}$ a prime and ${\displaystyle n}$ an integer ${\displaystyle \geq 1}$. Over a field of characteristic ${\displaystyle \ne 2,}$${\displaystyle \n$$eq 2,3}$ 타원$$ 곡선은 (짧은) Weierstrass 방정식으로 주어질 수 있습니다.

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

$A{\displaystyle ,}$ ${\displaystyle {}_{}}$ ∈ $Fq {\displaystyle$A,B$\in \mathbb {$F$\}$ _{q}}입니다. $F$ ${\displaystyle {}_{}^{}}$ ${\displaystyle \mathbb {F}$ _${q}}$에 정의된 점 집합은 곡선 방정식과 무한 ${\displaystyle$ O$\}$의 점을 만족하는 해 (a$)$∈ F$q$ 2 {\$displaystyle$(a, b)\$in$ \$mathbb {F}$ _${$q}^{2}}로 구성됩니다. 이 집합으로 제한된 타원 곡선에 대한 군 법칙을 사용하면 이 집합 $E{\displaystyle {}_{}}$) ${\$$displaystyle E$$(\mathbb {F}_{q})}$가 0 $요소$로 작용하는$$ 아벨 군을 형성한다는$$ 것을 알 수 있습니다$.$ 타원 곡선의 점을 세기 위해 $E{\displaystyle {}_{}}$) ${\displaystyle E(\mathbb {F}_{q}}$의 카디널리티를 계산합니다$.$ 카디널리티${\displaystyle \mathrm{}}$#${\displaystyle E({\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \#E(\mathbb {F}_{q}}$를 계산하는 슈프의 접근 방식은 중국의 나머지 정리 및 나눗셈 다항식과 함께 타원 곡선에 대한 하세 정리를 사용합니다$$.

하세 정리

하세의 정리는 $만약{\displaystyle }$E / ${\displaystyle {}_{}}$ q$${\$displaystyle E$/\$mathbb {F}$_{$q}$가 $유한장{\displaystyle {\mathbb{}}_{}}$ F ${\displaystyle {}_{}}$ ${\$에 대한 타원 곡선이라면$,$ # E${\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \#E(\mathbb {F} _{q}}}$는 다음을$$ 만족한다고 말합니다.

${\displaystyle \mid q+1-\#E(\mathbb {F}_{q})\mid \leq 2{\sqrt {q}}.$

1934년 Hasse가 제공한 이 강력한 결과는 #${\displaystyle E}({\displaystyle \mathrm{}{}_{}}$ ${\displaystyle \#E(\mathbb {F}_{q})}$를 유한한(큰) 가능성 집합으로$$ 좁혀 문제를 단순화합니다. Defining ${\displaystyle t}$ to be ${\displaystyle q+1-\#E(\mathbb {F} _{q})}$, and making use of this result, we now have that computing the value of ${\displaystyle t}$ modulo ${\displaystyle N}$ where ${\displaystyle N>4{\sqrt {q}}}$, $이$는$$t {\$displaystyle t},$ 따라서 #${\displaystyle }$E $($$)$ {\$displaystyle \#E(\mathbb {F}_{$q}}을(를) 결정하는 데 충분합니다$.$ $일반{\displaystyle }$N {\$displaystyle$ N$}$에 $대해{\displaystyle }$ t (${\displaystyle mod}$N$)$ {\$displaystyle$ t${\pmod$ {N$}}$을 직접$$ 계산하는 효율적인 방법은 없지만$,$ $l{\displaystyle }$ ${\displaystyle l}$에 대해 t${\displaystyle }$(${\displaystyle \mathrm{mod}}$ ${\displaystyle l)}$ ${\$ t${\pmod {l}}$을(를) 효율적으로 계산할 수 있습니다. We choose ${\displaystyle S=\{l_{1},l_{2},...,l_{r}\}}$ to be a set of distinct primes such that ${\displaystyle \prod l_{i}=N>4{\sqrt {q}}}$. Given ${\displaystyle t{\pmod {l_{i}}}}$ for all ${\displaystyle l_{i}\in S}$, 중국어 나머지 정리를 통해 t${\displaystyle (\mathrm{mod}}$ ${\displaystyle N)}$ ${\$을 계산할 수 있습니다$.$

${\displaystyle \mathrm{기본}}$ ≠ p${\displaystyle$ l\n에 대해 $t{\displaystyle }$(${\displaystyle \mathrm{mod}}$ ${\displaystyle l)}$ ${\displaystyle$ t${\pmod {l}}$을 계산하려면$eq$ 저희는 프로베니우스 내형$$$ϕ$ {\displaystyle$$\phi} 및 나눗셈 다항식의 이론을 사용합니다. ${\displaystyle \mathrm{소수}}$ ≠ p${\displaystyle$ l\n을 고려합니다.$eq}$는 제품이 충분히 큰지 확인하기 위해 항상 더 큰 프라임을 선택할 수 있기 때문에 손실이 없습니다$$. 어쨌든 Schoof의 알고리즘은 소특성 필드에 대한 p {\displaystyle p} 애디컬 알고리즘이라고 불리는 더 효율적인 것이 있기 때문에 케이스 $q$ = ${\displaystyle p}$ ${\$displaystyle q = $p}$를 해결하는 데 가장 자주 사용됩니다.

프로베니우스 내형성

Given the elliptic curve ${\displaystyle E}$ defined over ${\displaystyle \mathbb {F} _{q}}$ we consider points on ${\displaystyle E}$ over ${\displaystyle {\bar {\mathbb {F} }}_{q}}$, the algebraic closure of ${\displaystyle \mathbb {F} _{q}}$; i.e. ${\displaystyle F_{}}$¯ q {\$displaystyle${\$bar {\mathbb {F$_{q}}의 좌표를 갖는 점을 허용합니다. $F$$q$ {\displaystyle ${\mathbb {F}}$_{$q$}$$위의 F ¯ q {\$displaystyle \mathbb {$F}_{q}의 프로베니우스 내형은 ϕ${\displaystyle :}$ (${\displaystyle {}^{}{}^{}}$ y${\displaystyle {}^{}}$ ↦ (x$q$, y$q$) ${\displaystyle \phi$ : (x$,$ y$)\backslash$mapsto (x^{q, y ^{q}}에 의해 $타원{\displaystyle }$곡선으로 확장됩니다.

이 맵은 $E{\displaystyle ({}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ E$(\mathbb {F} _{q})}$의 ID이며 무한대 $O${\$displaystyle$ O$}$의 점까지 확장할$$수 $E$(${\displaystyle \stackrel{}{{}_{}}}$¯) ${\displaystyle$E({\$bar {\mathbb$ {F$}$ _{q}})에서 자신으로 그룹 모피즘이 됩니다.

프로베니우스 내동형은 다음 정리에$$ $의해{\displaystyle }$ E${\displaystyle ({}_{}}$)${\displaystyle E(\mathbb {F}_{q})}$의 카디널리티와 연결되는 2차 다항식을 만족합니다.

정리: ϕ${\displaystyle$ \phi}에 의해 주어진 프로베니우스 내형은 특성 방정식을 만족합니다.

${\displaystyle {}^{}}$2${\displaystyle {}^{}}$- ${\displaystyle t}$ ${\displaystyle \mathrm{\varphi }{}^{}}$+$$q = $0$, ${\displaystyle$ \$phi$ ^{2}-t\phi${\displaystyle {}^{}}$+ q = 0,} 여${\displaystyle {기}^{}}$서 t = q + 1 - # E (F q) {\displaysty${\displaystyle l^{}}$e t = q$+$1-\# E (\mathbb {F} _{q})}

Thus we have for all ${\displaystyle P=(x,y)\in E}$ that ${\displaystyle (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$, where + denotes addition on the elliptic curve and ${\displaystyle q(x,y)}$ and ${\displaystyle t(x^q,}$${\displaystyle t(x^{q},y^{q})}$ denote scalar multiplication of ${\displaystyle (x,y)}$ by ${\displaystyle q}$ and of ${\displaystyle (x^{q},y^{q})}$ by ${\displaystyle t}$.

One could try to symbolically compute these points ${\displaystyle (x^{q^{2}},y^{q^{2}})}$, ${\displaystyle (x^{q},y^{q})}$ and ${\displaystyle q(x,y)}$ as functions in the coordinate ring ${\displaystyle {\mathbb{F}}_q[x,}$${\displaystyle y]/}$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$- A ${\displaystyle x}$- ${\displaystyle B}$) ${\$$displaystyle$$\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)}$ $E{\displaystyle }${\displaystyle $E}$의 값을 찾은 다음 방정식을 만족하는$$ $t{\displaystyle }$ ${\displaystyle$ t$}$의 값을 검색합니다. 그러나, 그 정도가 매우 커지고 이 접근법은 비현실적입니다.

Schoof의 아이디어는 다양한 작은 $소수{\displaystyle }$ ${\displaystyle l}$에 대해 $순서{\displaystyle }$ l$${\$displaystyle$ l$}$의 점으로 제한된 이 계산을 수행하는 것이었습니다$.$ 홀수 $소수{\displaystyle }$ ${\displaystyle l}$을$($를) 고치고 이제 ${\displaystyle t_{}}$ ${\$}을$($를) 결정하는 문제를 해결합니다$.$ $t{\displaystyle (\mathrm{mod}}$ ${\displaystyle l)}$ ${\displaystyle t{\pmod {l}}$로 정의됨$,$ 주어진 ${\displaystyle \mathrm{기본}}$ ≠ $2$에 대해 p${\displaystyle$ l\n$eq 2,p$ 점${\displaystyle }$(${\displaystyle x,}$ y${\displaystyle )}$ ${\displaystyle (x,$$y)}$은(는) l ${\displaystyle$ l$}$ - $tors$ $부분군{\displaystyle }$E$$[l] $=$ {P $∈$ E (Fq $¯$) $∣$ l P $=$ O} {\displaystyle E[l]$=$\{P\in E ({\bar {\mathbb {F} _{q}})\mid lP$=$O\}, then ${\displaystyle qP={\bar {q}}P}$ where ${\displaystyle {\bar {q}}}$ is the unique integer such that ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$ and ${\displaystyle \mid {\bar {q}}\mid <l/2}$. Note that ${\displaystyle \phi (O)=O}$ and that for any integer ${\displaystyle r}$ we have ${\displaystyle r\phi (P)=\phi (rP)}$. Thus ${\displaystyle \phi (P)}$ will have the same order as ${\displaystyle P}$. Thus for ${\displaystyle (x,y)}$ belonging to ${\displaystyle E[l]}$, we also have ${\displaystyle t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})}$ if ${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$. 그래서 우리는 우리의 문제를 방정식을 푸는 것으로 줄였습니다.

${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q}),}$

여기서 $t$¯ ${\displaystyle${\bar {t}}${\displaystyle }$및 q ¯ {\displaystyle {\bar {q}}은 [ -(l - 1 ) / 2, (l - 1 ) / 2] {\displaystyle [-(l-1)/ 2, (l-1)/ 2]의 정수 값을 갖습니다.

연산 모듈로 소수

l번째 나눗셈 다항식은 그 근이 정확히 l의 점들의 x좌표가 되도록 하는 것입니다. 따라서 $($x ${\displaystyle q^{}}$ ${\displaystyle {2^{}}^{}}$ y ${\displaystyle {q^{}}^{}}$ 2${\displaystyle {{}^{}}^{}}$+ ${\displaystyle q}$ ¯${\displaystyle }$(x, $y$) ${\displaystyle (x^{q^{2}},$ y$^{$q^{$2}}+{\bar {q$}}(x,y)}의 계산을 l-토션 포인트로 제한하는 것은 E와 l차 나눗셈 다항식의 좌표 링에서 이 식을 함수로 계산하는 것을 의미합니다. $즉$, ${\displaystyle {}_{}}$[ ${\displaystyle x,}$ y${\displaystyle }$]${\displaystyle }$/${\displaystyle }$(${\displaystyle y^{}}$ 2${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle 3^{}}$- ${\displaystyle A}$ ${\displaystyle x}$- ${\displaystyle B,}$ψ l) ${\$displaystyle $\mathbb {F} _{q}[$x,$y]$ /($y^{$2}-$x^{$3}-$Ax-B,\$psi$$_{l}}에서 작업 중입니다. 이는 특히${\displaystyle {}^{}}$와${\displaystyle Y}$의${\displaystyle \mathrm{정도}}$가${\displaystyle }$(X ${\displaystyle (}$x${\displaystyle ,}$ ${\displaystyle y}$ ), ${\displaystyle Y}$ (x${\displaystyle ,}$ y${\displaystyle )}$ ${\displaystyle {{}^{}}^{}}$=${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {{}^{}}^{}}$2${\displaystyle ,}$ ${\displaystyle yq}$ 2${\displaystyle }$) +$q$ ¯ ($x,$ y ) {\$displaystyle (X(x,$y), Y(x, y):$=$(x^{$q^{2}}, y^{q^{2}}+{\bar {q}}(x,y)}$는 y에서 최대 1, x에서 최대$$2(${\displaystyle l^{}}$2 -${\displaystyle 3}$)/${\displaystyle 2}$ ${\displaystyle (l^{2}-3)/2}$입니다.

스칼라 $곱셈$ ${\displaystyle q}$ ¯${\displaystyle }$(x, $y$) ${\displaystyle {\bar {$q}}(x, y)}은 이중 덧셈 방법 또는$q$ ¯ {\$displaystyle$ {\bar {q}} 제분 다항식을${\displaystyle \stackrel{}{}}사용$하여 수행할 수 있습니다. 후자의 접근 방식은 다음과 같습니다.

${\displaystyle {\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{\bar {q}-1}\psi _{\bar {q}+1}{\bar {q}+1}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{2{\bar {q}}},{2\psi _{\bar {q}}^{4}}\right)}}$

여기서$$ψ n ${\displaystyle \$psi _{n}}은 n차 나눗셈 다항식입니다. y ${\displaystyle q}$ ¯ / y {\$displaystyle y_{\bar {$q}}/y}는 x에만 있는 함수이며${\displaystyle }$θ${\displaystyle (}$x )${\displaystyle$ $\backslash$theta(x)}로 $표시$됩니다.

문제를$$(${\displaystyle {x^{}}^{}q}$ ${\displaystyle {}^{}}$, ${\displaystyle y}$ $q$) ¯ ± q ≠ (x$, y) {\displaystyle$ (x$^{q$^{2$}},$ y^{q^{2}}\n인 경우로 나누어야 합니다.$eq \pm {\bar {q}}(x,y$ 및 (${\displaystyle {}^{}}$ ${\displaystyle {q^{}}^{}}$ 2${\displaystyle {{}^{}}^{}{}^{}}$ ${\displaystyle q^{}}$ ${\displaystyle {2^{}}^{}}$ $=$${\displaystyle }$±$$q $¯$ (x,y) {\displaystyle (x^{q^{2}},y^{q^{2}) $=$\pm {\bar {q}}(x,y)}인 경우. 이러한 동등성은 모듈로$$ψ ${\displaystyle${l}}에서 확인됩니다.

사례 1:$$(${\displaystyle {}^{}}$ ${\displaystyle {q^{}}^{}}$ 2${\displaystyle {{}^{}}^{}}$ y ${\displaystyle q}$ 2${\displaystyle {{}^{}}^{}}$ ≠ ± ${\displaystyle q}$ ¯ (x, y)${\displaystyle (x^{$q^{$2$}}, y^{q^{2}})\n$eq \pm {\bar {q}}(x,y)}$

그룹 $E{\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}${\$displaystyle$ E $(\mathbb {F} _{q}}$에 대한 덧셈 공식을 사용하면 다음을$$ 얻을 수 있습니다.

${\displaystyle X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}-x^{q^{2}}-x_{\bar {q}}.}$

부등식 가정이 잘못된 경우 이 계산은 실패합니다.

이제 x좌표를 사용하여 $t$¯ {\$displaystyle {\$t}의 선택 범위를 양의 경우와 음의 경우로 좁힐 수 있습니다. y좌표를 사용하면 나중에 두 경우 중 어떤 경우가 성립하는지 알 수 있습니다.

우리는 먼저 X가 x에서만 함수라는 것을 보여줍니다. $({\displaystyle {}^{}}$ ${\displaystyle q^{}}$ ${\displaystyle {2^{}}^{}}$- ${\displaystyle {}_{}}$ ${\displaystyle q^{}{}_{}}$¯) ${\displaystyle {}^{}}$ = ${\displaystyle y^{}}$ ${\displaystyle {2^{}}^{}}$($y$$$q 2 - 1 - y q ¯ / y) 2 {\displaystyle(y^{q^{2}-y_{\bar {q}}^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}/y)^{2}}를 생각해 보십시오. q 2 - 1 {\displaystyle q^{2}-1}은 짝수이므로, $y{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$ $y$$^{2}}$를 $x{\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$+ ${\displaystyle A}$ ${\displaystyle x}$+ B ${\displaystyle$ x$^{3}+$로 대체합니다.$Ax+B$ 식을 다음과 같이 씁니다.

${\displaystyle (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))}$

그리고 그것을 가지고 있습니다.

${\displaystyle X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)){\bmod {\psi }}_{l}(x).}$

여기, 잘못된 것 같습니다. $x$ ${\displaystyle q^{}}$ ${\displaystyle {2^{}}^{}}$- ${\displaystyle {}_{}}$ $q$¯ {\$displaystyle x^{q^{2$}}-$x_$bar {q}}}를 버립니다.

Now if ${\displaystyle X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)}$ for one ${\displaystyle {\bar {t}}\in [0,(l-1)/2]}$ then ${\displaystyle {\bar {t}}}$ satisfies

${\displaystyle \phi ^{2}(P)\mp {\bar {t}}\phi (P)+{\bar {q}}P=O}$

모든 l-토션 점 P에 대하여.

As mentioned earlier, using Y and ${\displaystyle y_{\bar {t}}^{q}}$ we are now able to determine which of the two values of ${\displaystyle {\bar {t}}}$ (${\displaystyle {\bar {t}}}$ or ${\displaystyle -{\bar {t}}}$) works. 이것은 $t$ ≡ ${\displaystyle t}$ ¯($mod$ $l$) {\displaystyle t\equiv {\bar {}}{\pmod {l}}의 값을 제공합니다. Schoof의 알고리즘은 고려되는 각 프라임에 대한 변수 t {\displaystyle {t}}{\pmod {l}}의 값을 t ¯(mod l) {\displaystyle {t}} {\pmod {l}}의 값을 저장합니다.

사례 2:$$(${\displaystyle {}^{}}$ ${\displaystyle q^{}}$ ${\displaystyle {2^{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {q^{}}^{}}$ 2${\displaystyle {{}^{}}^{}}$ =${\displaystyle }$± $q$¯$$(x, y) {\displaystyle (x^{q^{2}}, y^{q^{2}) =\pm {\bar {q}} (x,y)}

먼저 $({\displaystyle x^{}}$ ${\displaystyle {q^{}}^{}}$2, ${\displaystyle y^{}}$ ${\displaystyle {q^{}}^{}}$2) = ${\displaystyle q}$¯ (x, y) ${\displaystyle$ (x^{q^{2}}, y^{q^{2}) = {\bar {q}}(x,y)}라고 가정합니다. l은 홀수 소수이므로$q$ ¯ (x, y) = - q ¯ (x, y) {\displaystyle {\bar {q}}(x,y) =-{\bar {q}}(x, y)}(x,$y)}$ $따라서$ $t$$¯ ≠$ ${\displaystyle 0}$ {\displaystyle ${\bar {t$}}\n$eq$ 0$\}.$ 특성 방정식은 $t{\displaystyle }$¯ ϕ (P${\displaystyle )}$ = 2${\displaystyle }$q ¯ P {\displaystyle ${\$bar {t}}\$phi$ (P$)$= 2{\bar {q}P}입니다. 결과적으로 t ¯ 2 q ¯ ≡ (2 q) 2 (mod l) {\displaystyle {\bar {t}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}입니다. 이는 q가 정방형 모듈임을 의미합니다. Let ${\displaystyle q\equiv w^{2}{\pmod {l}}}$. Compute ${\displaystyle w\phi (x,y)}$ in ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ and check whether ${\displaystyle \overline{q}(x,y)=w\varphi (x,}$$displaystyle {\bar {q}}(x,y$=w$\phi(x,y)}$입니다$.$ 그렇다면 ${\displaystyle {tl}_{}}${\$displaystyle t_{l}}$은 y좌표에 따라 $\pm {\displaystyle \mathrm{2w}(mod}$ l${\displaystyle )}${\$displaystyle \pm2w{\pmod {l}}$입니다.

If q turns out not to be a square modulo l or if the equation does not hold for any of w and ${\displaystyle -w}$, our assumption that ${\displaystyle (x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)}$ is false, thus ${\displaystyle (x^{q^2},y^{q^2})=-\overline{q}(x,}$$displaystyle(x^{q^{2}},y^{q^{2$}}${\displaystyle )}$=$-{\bar {q}}(x,y$ 특성 방정식은 ${\displaystyle l_{}}$${\displaystyle }$= ${\displaystyle 0}$ {\$displaystyle$ $t_{l$${\displaystyle \}}$= 0}을 제공합니다.

${\displaystyle \mathrm{추가}}$ 대소문자 $l$ =$$2 {\displaystyle l = 2$}$

기억하신다면, $저희$의 초기 고려 ${\displaystyle \mathrm{사항}}$은 l =$$2 {\displaystyle $l$ = 2}의 경우를 생략합니다. q를 홀수라고 가정하기 때문에 q + 1 - t ≡ t (mod 2) {\displaystyle q + 1-t\equiv {\pmod {2}} 특히, ${\displaystyle {}_{}t}$ ${\displaystyle 2_{}}$ ${\displaystyle \equiv }$ ${\displaystyle 0}$ (mod $2)$ {\$displaystyle t_{2}\equiv 0{\$pmod {2}}${\displaystyle {}_{}}$E$$($F q)$ {\$displaystyle$ E$(\mathbb$ {F}_{q})}가 차수 2의 요소를 갖는 ${\displaystyle {}_{}}$에만${\displaystyle .}$ 그룹의 덧셈에 대한 정의에 따라 순서 2의 모든 요소는${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle 0)}${\$displaystyle (x_{0}, 0)}$ 형식이어야 합니다$.$ ${\displaystyle {따라서}^{}}$$t$ ${\displaystyle 2}$ ≡ 0 (mod $2$) {\$displaystyle t_{2}\equiv 0{\$pmod {2}} ${\displaystyle \mathrm{다항식}}$ ${\displaystyle x3}$ + A$$x + B {\$displaystyle$x^{3}+인 경우에만$Ax+B}$은(는) $Gcd$(${\displaystyle x^{}{q}^{}}$ - ${\displaystyle {}^{}}$ ${\displaystyle x}$ ${\displaystyle 3}$ + A ${\displaystyle \mathrm{x}}$+ ${\displaystyle B)}$$≠$ 1 ${\displaystyle$ \$gcd(x^{q}-x,$x^{3}+Ax+B)인 $경우$에만 ${\displaystyle {}_{}}$ ${\displaystyle \mathbb {F}_{q}}$에 루트가 있습니다$.$$\n$$eq$ 1$\}.$

알고리즘이.

    입력 : 1. 타원 곡선 $E$ = ${\displaystyle y^{}}$ 2${\displaystyle {}^{}}$-$$x 3 - A x - B {\$displaystyle$ E = y$^{2$}-x^{3}-Ax-B$}.$ 2. q = p b, b ≥ 1 {\displaystyle F_{q}인 유한 필드 F q {\displaystyle F_{q}에 대한 정수 q. 출력:         The number of points of E over ${\displaystyle F_{q}}$.     Choose a set of odd primes S not containing p such that ${\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.}$ Put ${\displaystyle t_{2}=0}$ if ${\displaystyle gcd(x^q-x,}$$x$$\n$$eq 1}$, else ${\displaystyle t_{2}=1}$. Compute the division polynomial ${\displaystyle \psi _{l}}$.      All computations in the loop below are performed in the ring ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).$$}$ For ${\displaystyle l\in S}$ do: Let ${\displaystyle {\bar {q}}}$ be the unique integer such that  ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$ and ${\displaystyle \mid {\bar {q}}\mid <l/2}$. Compute ${\displaystyle (x^{q},$$y^{q})}$, ${\displaystyle (x^{q^{2}},y^{q^{2}})}$ and ${\displaystyle (x_{\bar {q}},y_{\bar {q}})}$. if ${\displaystyle x^{q^{2}}\n$$eqx_{\bar {q}}$ 다음$$ 계산$({\displaystyle X,}$ Y${\displaystyle )}$ ${\displaystyle (X, Y$ for ${\displaystyle 1\leq {\bar {t}}\leq (l-1)/2}$ do: if ${\displaystyle X=x_{\bar {t}}^{q}}$ then if ${\displaystyle Y=y_{\bar {t}}^{q}}$ then ${\displaystyle t_{l}={\bar {t}}}$; else ${\displaystyle$$t_{l}=-{\bar {t}}}$. else if q is a square modulo l then compute w with ${\displaystyle q\equiv w^{2}{\pmod {l}}}$ compute ${\displaystyle w(x^{q},y^{q})}$ if ${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},$$y^{q^{2}}}$ 다음 t $l$ $=$ w (x$$q, y q ) $=$ (x q 2, - y q 2) {\displaystyle w (x^{q}) $=$ (x^{q^{2}}인 경우 ${\displaystyle 2_{}}$ $displaystyle$ t_{l} $=$ 2w}입니다.$-y^{q^{2}})}$ then ${\displaystyle t_{l}=-2w}$ else ${\displaystyle t_{l}=0}$ else ${\displaystyle t_{l}=0}$     Use the Chinese Remainder Theorem to compute t modulo N         from the equations ${\displaystyle t\equiv t_{l}{\pmod {l}}}$, ${\displaystyle \mathrm{여기}}$서 l$$∈ S ${\display$l$\backslash$in S}.${\displaystyle \mathrm{출력}}$ ${\displaystyle q}$+ 1 - t {\$display$q+1-t}. 

복잡성

Most of the computation is taken by the evaluation of ${\displaystyle \phi (P)}$ and ${\displaystyle \phi ^{2}(P)}$, for each prime ${\displaystyle l}$, that is computing ${\displaystyle x^{q}}$, ${\displaystyle y^{q}}$, ${\displaystyle x^{q^{2}}}$, ${\displaystyle {}^{}}$$y{\displaystyle }$ ${\displaystyle {q{}^{}}^{}}$ ${\displaystyle {{2\mathrm{}}^{}}^{}}$ ${\displaystyle {q$$^{2$}} 각 기본 {\$displaystyle$ l$}$에 대한$$ y q 2 {\$displaystyle$ y$^{q$^{2$\}\}.$ 여기에는 링 $R$ = ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$[${\displaystyle }$x, y ] / (y 2 - x 3 - A x - B, ψ l) {\displaystyle R =\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}}의 지수가 포함되며 O(로그 ⁡ q) {\displaystyle O(\log q)} 곱셈이 필요합니다. ψ$$ {\displaystyle $\psi_{$l}}의 차수가 $l$ 2 - 12 {\displaystyle {\frac {l^{2}-1}{2}}이므로, 환의 각 원소는 차수 O(l 2) {\displaystyle O(l^{2}}의 다항식입니다. 소수 정리에 의해, there are around ${\displaystyle O(\log q)}$ primes of size ${\displaystyle O(\log q)}$, giving that ${\displaystyle l}$ is ${\displaystyle O(\log q)}$ and we obtain that ${\displaystyle O(l^{2})=O(\log ^{2}q)}$. 따라서 링 $R$ ${\displaystyle$ R$}$의 각 곱셈은 ${\displaystyle F^{}}$$q {\displaystyle \mathbb {$F} _{q}에서 O(log 4 ⁡ q) {\$displaystyle$ O$(\log$^{4}q)} ${\displaystyle {}_{}}$을 필요로 하며, 이때 $log$2$$⁡ q) ${\displaystyle$O(\log ^{2}q)} 비트 연산이${\displaystyle {\mathrm{필요}}^{}}$합니다. $각$ 기본 ${\displaystyle l}$의 비트 연산 수는 $O{\displaystyle (\log }$ ${\displaystyle 7^{}}$ ⁡ q) ${\displaystyle$ O$(\$log ^{7}q)}입니다. 이 계산은 각 O(log ⁡ q) {\displaystyle O(\log q)}개의 기본에 대해 수행되어야 합니다. Schoof의 알고리즘의 전체 복잡도는 $O{\displaystyle (\log }$ ${\displaystyle 8^{}}$ ⁡ q) ${\displaystyle O(\log$8}q)}인 것으로 나타났습니다. 빠른 다항식과 정수 산술을 사용하면 이 값이 O ~ (log 5 ⁡ q) {\displaystyle {\tilde {O}}(\log ^{5}q)}로 줄어듭니다.

Schoof 알고리즘의 개선점

1990년대에 노암 엘키스(Noam Elkies)와 A. O. L. 애트킨(${\displaystyle {}_{}{}_{}{O}_{}.}$L. Atkin)은 이전에 고려된 소수 S$$= {l 1, …, l s} {\displaystyle S =\{l_{1},\ldots,l_{s}\} 집합을 특정 종류의 소수로 제한함으로써 슈프의 기본 알고리듬에 대한 개선 사항을 고안했습니다. 이것들은 각각 엘키스 소수와 앳킨 소수라고 불리게 되었습니다. $특성$${\displaystyle {}^{}}$방정식인${\displaystyle }$ϕ 2 - t$$ϕ +$$q$$= 0${\$displaystyle \phi^{2$}-$t\phi + q=0}이 Fl {\displaystyle \mathbb {F}_{l}에 걸쳐 분할되는 반면, Atkin 프라임은 Elkies 프라임이 아닌 프라임입니다. Atkin은 효율적인 알고리즘을 만들기 위해 Atkin 소수에서 얻은 정보와 Elkies 소수에서 얻은 정보를 결합하는 방법을 보여주었고, 이는 Schof-로 알려지게 되었습니다.엘키스–Atkin 알고리즘. 첫 번째 해결해야 할 문제는 주어진 소수가 엘키스인지 앳킨인지를 결정하는 것입니다. 이를 위해 모듈 형태에 대한 연구와 복소수에 대한 타원 곡선의 해석에서 나온 모듈 다항식을 격자로 사용합니다. 일단 우리가 어떤 경우에 해당하는지를 결정하고 나면, 우리는 나눗셈 다항식을 사용하는 대신 해당 나눗셈 다항식보다 낮은 차수를 갖는 다항식을 사용할 수 있습니다: $O{\displaystyle ({l\mathrm{}}^{}}${\$display$O($l^{2}}$ 대신$$ $O{\displaystyle (l)}$ ${\style$O($l$$)\}.$ 효율적인 구현을 위해, 확률적 근찾기 알고리즘을 사용하므로 결정론적 알고리즘이 아닌 라스베이거스 알고리즘이 됩니다. $O{\displaystyle (\mathrm{로그}}$ ⁡ q) ${\displaystyle$ O$(\$log q)} 바운드까지의 소수 중 약 절반이 Elkies 소수라는 휴리스틱 가정 하에서, 이것은 순진한 산술을 사용하여 O(로그 6 ⁡ q) {\displaystyle O(\log ^{6}q)}의 예상 실행 시간으로 Schoof의 것보다 더 효율적인 알고리즘을 산출합니다. 그리고 $O{\displaystyle \stackrel{}{}}$~${\displaystyle }$(${\displaystyle \log }$ 4 ⁡ q ) ${\displaystyle {\tilde$ {O$}}(\log$^{4}q)}는 빠른 연산을 사용합니다. 이 휴리스틱 가정은 대부분의 타원 곡선에서 성립하는 것으로 알려져 있지만, GRH 하에서도 모든 경우에 성립하는 것으로 알려져 있지는 않습니다.

구현

마이크 스콧(Mike Scott)이 C++로 구현한 알고리즘은 소스 코드로 사용할 수 있습니다. 구현은 무료이며(조건, 조건 없음) AGPLv3에서 배포되는 MIRACL 라이브러리를 사용합니다.

• 소수 $p$가 ${\displaystyle p}$인 $E{\displaystyle ({\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle E(\mathbb {F}_{p})}$에 대한 슈프의 알고리즘 구현$.$
• 슈프의 $E{\displaystyle ({\mathbb{}}_{}}$ ${\displaystyle {{2m}^{}}_{}}$ ${\displaystyle E(\mathbb {F}$ _${2^{m}}}$에 대한 알고리즘 구현$.$

참고 항목

• 타원곡선암호
• 타원 곡선에 점을 세는 중
• 나눗셈 다항식
• 프로베니우스 내형성

참고문헌

• R. 슈프: 유한장 위의 타원 곡선과 제곱근 modp의 계산. 수학. Comp., 44(170):483-494, 1985. http://www.mat.uniroma2.it/ ~schoof/ctpts.pdf에서 이용 가능
• R. 슈프: 유한 필드 위의 타원 곡선에서 점을 계산합니다. J. 이론. Nombres Bordeo 7:219–254, 1995. http://www.mat.uniroma2.it/ ~schoof/ctg.pdf에서 이용 가능
• G. Musiker: $Schoof$의 E (${\displaystyle {}_{}}$ ${\displaystyle$ E $(\mathbb {F}$ _${q$ http://www.math.umn.edu/ 에서 이용 가능합니다.musiker/schoof.pdf
• V. 뮐러: Die Berechnung der Punktanzahl von Elliptischen Kurven über endlichen Primkörpern. 석사 논문. 1991년 자르브뤼켄 대학교(Universität des Saarlandes). http://lecturer.ukdw.ac.id/vmueller/publications.php 에서 이용 가능
• A. Enge: 타원곡선과 암호학의 응용: 서론. Kluwer Academic Publishers, Dordrecht, 1999.
• L. C. 워싱턴: 타원 곡선: 숫자 이론과 암호학. 채프먼 & 홀/CRC, 뉴욕, 2003.
• N. 코블리츠: 정수론과 암호학 과정, 수학 대학원 교재. 스프링어-베를라그, 1987년 114호 1994년 2판