타원곡선 원시성

수학에서 타원곡선 원시성 시험 기법 또는 타원곡선 원시성 증명(ECPP)은 원시성 ^[1]증명에서 가장 빠르고 널리 사용되는 방법 중 하나이다.1986년 샤피 골드워서와 조 킬리안이 내놓은 아이디어로 같은 해 A.O.L. 앳킨이 알고리즘으로 만들었다.이 알고리즘은 이후 여러 협력자들에 의해 변경되고 개선되었으며, 특히 1993년 ^[2]앳킨과 프랑수아 모랭[de]에 의해 개선되었다.인수분해에서 타원 곡선을 사용하는 개념은 1985년 H. W. 렌스트라에 의해 개발되었으며, 원시성 테스트(및 증명)에서의 사용에 대한 암시는 빠르게 이어졌다.

원시성 테스트는 페르마 시대부터 존재해 온 분야로, 대부분의 알고리즘이 인수분해(Factoring)에 근거하고 있어, 대량의 입력에 의해 다루기 어려워집니다.현대 알고리즘은 숫자가 소수인지, 그 인자가 무엇인지를 개별적으로 판단하는 문제를 다루고 있습니다.그것은 현대 암호학의 출현과 함께 실질적으로 중요해졌다.많은 현재 테스트 결과 확률론적 출력이 나오지만 (N은 Baillie와 같이 복합적이거나 아마도 프라임으로 표시됨)PSW 프라이머리 테스트 또는 밀러-라빈 테스트, 타원 곡선 테스트는 신속하게 검증 가능한 증명서를 사용하여 프라이머리(또는 합성도)^[3]를 증명합니다.

이전에 알려진 Pocklington primality test와 같은 프라임 증명 방법에서는$N$이 $프라임임$을 증명하기 위해 N${\displaystyle }$± $(디스플레이$ $스타일$ N$\$$pm$1) 이상의$$ $부분{\displaystyle }$ 인수 분해가 필요했다.결과적으로, 이러한 방법들은 약간의 운이 필요했고 일반적으로 실행 속도가 느렸다.

타원곡선 원시성 증명

이것은 범용 알고리즘으로, 특수한 형식의 번호에 의존하지 않습니다.ECPP는 현재 일반적인 숫자의 소수성을 테스트하기 위한 가장 빠른 알고리즘이지만 최악의 경우 실행 시간은 알려져 있지 않습니다.ECPP는 휴리스틱하게 시간 내에 실행됩니다.

$(\displaystyle O(\log n)^{5+\varepsilon }),$

\ $displaystyle$\ $varepsilon$> $0$^[4]. 。휴리스틱 인수에 의해 일부 버전에서는 이 지수를${\displaystyle }$4 +$${\(\$displaystyle$ 4$+\varepsilon)$로 줄일 수 있습니다.ECPP는 다른 대부분의 프라이머리 테스트와 동일하게 동작하며 그룹을 찾아 크기를 p$\style$p가 프라임이$$ 되도록 $나타냅니다{\displaystyle }$.ECPP의 경우 그룹은 2차 ${\displaystyle \mathrm{형식}}$의 유한 집합 위에 있는 타원 곡선이며${\displaystyle ,}$p - 1(\$displaystyle p-1$)은$$ $그룹$에 대해 인수분해하기 쉽다.

ECPP는 재귀에 의해 Atkin-Goldwasser-Killian-Morain 프라이머리 증명서를 생성하고 증명서 확인을 시도합니다.클래스 필드에 대한 팩터링을 수행해야 하므로 CPU 시간이 가장 오래 걸리는 단계는 증명서 생성입니다.증명서를 빠르게 검증할 수 있기 때문에 동작 체크에 걸리는 시간은 매우 짧습니다.

2022년 6월^[update] 현재 ECPP 방식으로 증명된 최대 소수는 ${\displaystyle {1050000}^{}}$ ${\displaystyle {}^{}}$ $(\display style$ 10$^{50000}$ + $65859$^[5]이다.인증은 Andreas Enge가 FastECPP 소프트웨어를 사용하여 수행했습니다.

제안

그 타원 곡선 primality 시험 기준이(Z/nZ)({\displaystyle(\mathbb{Z}/n\mathbb{Z})^{*}}E(Z/nZ),{\displaystyle E(\mathbb{Z}/n\mathbb{Z}),}, E에 의해 교체 대상 집단이 제대로 선택한 e. 그 시험 based,[6][7]은 Pocklington 판단 기준과 유사한에 기초한다lliptic 곡선이제 우리는 포클링턴 기준과 유사하며 타원 곡선 원시성 테스트의 골드워서-킬리안-애킨 형식을 발생시키는 우리의 테스트의 기초가 되는 제안을 말할 것이다.

N을 양의 정수, E를 ${\displaystyle {y2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}{3\mathrm{}}^{}}$ +${\displaystyle a}$ + ${\displaystyle b}$ ${\displaystyle mod}N$으로 정의되는 집합으로 합니다$.{$ $displaystyle$$$y$^{2$} =$x^{3}$ + $ax$ + b ${bmod$ {N$$}$$} }${\displaystyle over\mathbb{}}$ Z$,$ {\$displaystyle$ \$mathbbbb}$ {$Z} 。$

m을 정수로 합니다.m을 나눗셈하는${\displaystyle {\text{exception 25:}}^{}}$가 있으며${\displaystyle {}^{}}$(N 4 + 1${\displaystyle {)}^{}}$2보다 클 경우 \$displaystyle \left({\sqrt[{4})}{$$N}}+1\right)^{2}}$ 및$$ E에는 다음과 같은 P점이 존재합니다.

(1) mP = 0

(2) (m/q)P가 정의되어 있으며 0과 동일하지 않다.

그러면 N은 소수이다.

증명

N이 컴포지트일 경우 N을 분할하는 $소수{\displaystyle }$ p$n$N이 $존재합니다$$.$${\displaystyle E_{}}$p { $displaystyle E$_ { $p$} as$$ 、 E e e as as 、 E as as as as mod mod mod mod mod evaluated evaluated mod mod mod mod mod mod mod mod mod mod mod mod 、${\displaystyle m_{}}$p { $displaystyle m$_ { $p$$$} the$$ 、${\displaystyle {그룹}_{}}$ E$$p { $displaystyle$E _$${ p$$}의 순서로 $정의$합니다. 타원곡선에 대한 Hasse의 정리에 의해 알 수 있습니다.

${\displaystyle m_{p}\leq p+1+2{\sqrt{p}}=\left({\sqrt{p}}+1\right)^{2}\leq \left({\sqrt[{4}]{.N}}+1\right)^{2}<, q}$

따라서 gcd=1{\displaystyle \gcd(q,m_{p})=1}고 있는 정수가 속성은 존재할(q, m p).

${\displaystyle uq\equiv 1{\bmod{m_{p}}}.}$

P평가해 Pp{\displaystyle P_{p}}그 시점의 나머지 p.자따라서, Ep{\displaystyle E_{p}에}우리가 가지고 있다.

${\displaystyle(m/q)P_{p}(m/q)P_{p}=umP_{p}=0,}$

(1)으로, mPp{\displaystyle mP_{p}로}mP과 같은 메서드를 사용하여. p보다는 나머지 N(그리고 동업-∣ N{\displaystylep\mid N})을 제외하고 계산한다.

왜냐하면(m/q)P고 0(Nmod)이 아닌 정의되면 같은 방법 모듈로 대신 나머지 N:[8]를 양보할 것이다 이 계산된 이,(2)을 거스르는 것이다.

${\displaystyle(m/q)P_{p}\neq 0입니다.}$

골드워서-킬리안 알고리즘

이 명제에서부터 한 알고리즘 정수, N, 최상의 것을 입증할 구성될 수 있습니다.로:[6] 따르도록 한다.

무작위로, x와 세트 y세개의 정수를 선택합니다.

${\displaystyleb\equiv y^{2}-x^{3}-ax{\pmod{N}}}$

이제 P = (x,y)는 E 위의 점이며, 여기서 E는 y ${\displaystyle {2\mathrm{}}^{}}$ $=$ ${\displaystyle {x\mathrm{}}^{}}$3 +${\displaystyle a}$ + $({displaystyle$ y$^{2$}=$x^{3}+ax+b$로 정의됩니다.다음으로 E의 포인트 수를 세는 알고리즘이 필요합니다.이 알고리즘은 E에 적용되며(Koblitz와 다른 알고리즘은 Schof의 알고리즘을 제안함) N이 소수일 경우 F에 대한_N 곡선 E 위의 점 수인 숫자 m을 생성합니다.포인트 카운트 알고리즘이 정의되지 않은 식에서 정지하면 N의 중요하지 않은 계수를 결정할 수 있습니다.성공하면 곡선 E가 허용 가능한지 여부를 판단하기 위한 기준을 적용합니다.

$m{\displaystyle }$ ${\displaystyle =}$ ${\displaystyle k}$ q \$displaystyle$ m= kq$$ $형식으로$m을 쓸 수 있습니다.$여기$서 k${\displaystyle 2}$2 \ $displaystyle$ k \ $geq$2는$$ 작은 정수이고 q는 큰 가능성이 있는 소수(예를 들어 확률론적 프라임성 테스트를 통과한 수)입니다.그러면 E는 폐기되지 않습니다.그렇지 않으면 곡선을 버리고 처음부터 다시 시작할 다른 트리플(a, x, y)을 무작위로 선택합니다.여기서의 개념은 큰 소수 q로 나누어질 수 있는 m을 찾는 것입니다.이 소수는 m(또는 N)보다 몇 자리 작기 때문에 q는 N보다 소수를 증명하기 쉽습니다.

기준을 통과한 곡선을 발견했다고 가정하고 mP와 kP 계산을 진행합니다.두 계산 중 하나라도 정의되지 않은 식을 생성하면 N의 중요하지 않은 계수를 얻을 수 있습니다. 두 계산 모두 성공하면 결과를 검사합니다.

${\displaystyle m}$ P${\displaystyle 0}$0 { $display mP$\ $neq$ 0$$}이면 N이 소수가 아닌 것이 분명합니다.N이 소수일 경우 E는 차수 m을 가지며 E의 모든 요소는 m의 곱셈에서는 0이 되기 때문입니다.kP = 0이면 알고리즘은 E를 폐기하고 다른 a, x, y 트리플로 다시 시작합니다.

${\displaystyle m}$ P ${\displaystyle =}$ ${\displaystyle 0}${ $style mP$=$0$$k$ ${\displaystyle k0}$0 { $display kP$\ $neq$ 0$$}이면$$ $이전{\displaystyle }$ 명제는 N이 소수임을 나타냅니다.단, 생각할 수 있는 문제가 하나 있습니다.그것은 q의 primity입니다.이것은, 같은 알고리즘을 사용해 검증됩니다.그래서 우리는 재귀 알고리즘에 대해 설명했습니다.여기서 N의 primality는 q의 primality에 의존하며, 실제로 더 작은 primality에 도달하여 q가 비재귀 ^[9][10]결정론적 알고리즘을 적용하기에 충분히 작은 것으로 간주됩니다.

알고리즘에 관한 문제

앳킨과 모랭은 "GK의 문제는 슈프의 알고리즘이 ^[3]구현이 거의 불가능해 보인다는 것이다."라고 말한다.Goldwasser-Kilian 알고리즘에서 선호하는 알고리즘인 Schof의 알고리즘을 사용하여 E의 모든 포인트를 계산하는 것은 매우 느리고 번거롭다.그러나 Schof의 원래 알고리즘은 단시간에 ^[11]포인트 수를 제공할 만큼 효율적이지 않습니다.이러한 코멘트는 Elkies와 Atkin이 Schof의 방법을 개선하기 전에 역사적 맥락에서 보아야 한다.

Koblitz는 위와 같이 포인트 수가 kq인 곡선 E를 찾는 것이 어렵다는 것을 지적한다.우리가 다항식으로 많은 시도에서 적절한 E를 찾을 수 있다는 것을 보장하는 알려진 정리는 없다.m을 포함하는 Hasse${\displaystyle }$간격 [${\displaystyle p}$+${\displaystyle 1}$ - ${\displaystyle 2}$ ${\displaystyle p,p}$ +${\displaystyle 1}$ + ${\displaystyle 2}$ $]{$ $display$style [$p+1-2{\sqrt {p}}}, p+1+2${\$sqrt {$p$\}\}\}\}$의 소수 분포는 그룹 순서의 소수 분포와 동일하지 않습니다.다양한 곡선을 카운트합니다.그러나 실제로는 ^[8]큰 문제가 되지 않습니다.

Atkin-Morain 타원곡선 프라이머리 테스트(ECPP)

1993년 논문에서 Atkin과 Morain은 번거로운 포인트 카운트 알고리즘(Schof's)에 의존하는 문제를 회피하는 알고리즘 ECPP를 기술했다.알고리즘은 여전히 위에 언급된 명제에 의존하지만, 무작위로 타원 곡선을 생성하고 적절한 m을 찾는 대신, 그들의 아이디어는 점의 수를 계산하기 쉬운 곡선 E를 만드는 것이었다.복잡한 곱셈은 곡선 구조에서 핵심입니다.

이제 원시성을 증명해야 하는 N이 주어지면 Goldwasser-Kilian 검정에서와 마찬가지로 N의 원시성을 충족하고 증명하는 적절한 m과 q를 찾아야 합니다(물론 P점과 곡선 자체 E도 찾아야 합니다).

ECPP는 복잡한 곱셈을 사용하여 곡선 E를 구성하며, m(E 위의 점 수)을 쉽게 계산할 수 있는 방식으로 곡선 E를 구성합니다.이제 이 방법에 대해 설명하겠습니다.

복소 곱셈을 이용하려면 음의 판별식 D가 필요하며, D는 2개의 원소 D $=$ $display$ \ $pi$ { pi $}$의$$곱으로 쓰이거나 완전히 동등하게 쓸 수 있다.

$({displaystyle a^{2}+Db^{2}=4N, )$

어떤 a, b는.이러한 형태 중 하나로 N을 설명할 수 있는 경우, 복소 곱셈(아래 상세 설명)을 사용하여${\displaystyle }$Z/${\displaystyle N\mathbb{}}$Z(\$displaystyle$ \$mathbb {Z} /N\mathbb${Z}$$})에 타원 곡선 E를 생성할 수 있습니다. 점 수는 다음과 같습니다.

$(\displaystyle E(\mathbb {Z} /N\mathbb {Z}) = N+1-\pi - {\bar {\pi }}= N+1-a).\,}$

N을 2개의 요소로 분할하려면 (${\displaystyle \frac{\mathrm{DN}}{})}$ ${\displaystyle =}$ ${\displaystyle 1}$($Displaystyle \leftfrac {D}$ {$N}}$ \$right$)$=$ 1$$(${\displaystyle 여기}$서 ($)$ \$displaystyle \leftfrac$ {D} {$N}$ \$right)$ 이 필요합니다.이는 필수조건으로 Q${\displaystyle }$( ${\displaystyle D\sqrt{}}$) \ $displaystyle$ \$mathbb$ {$Q$} （ \ $sqrt${$D$} ） $の$ ((((h(D)가 1이면 충분합니다.이는 D의 13개 값({-3, -4, -7, -8, -11, -12, -16, -19, -27, -28, -43, -67, -163)에 대해서만 발생합니다.

테스트

h(D)가 증가하는 순서대로 판별 D를 선택합니다.각 D에 대해 (${\displaystyle \frac{\mathrm{DN}}{})}$ $=${\$displaystyle \leftflac {D}{N}}\right$)=$1}$인지 여부와 4N이 다음과 같이 기록될 수 있는지 확인합니다.

$({displaystyle a^{2}+Db^{2}=4N, )$

이 부분은 Cornacchia 알고리즘을 사용하여 검증할 수 있습니다.허용 가능한 D 및 a가 발견되면 m ${\displaystyle =N}$ +${\displaystyle 1}$ - a$${$displaystyle$ m$=N+1-a$를 $계산$합니다. 이제 m이 크기의 소수 계수 q를 갖는 경우

${\displaystyle q>(N^{1/4}+1)^{2}}$

복잡한 곱셈법을 사용하여 곡선 E와 그 위에 점 P를 구성합니다.그런 다음 우리의 제안을 사용하여 N의 소수를 확인할 수 있습니다. m이 큰 소인수를 가지지 않거나 충분히 빨리 인수화할 수 없는 경우, 다른 D를 선택할 ^[1]수 있습니다.

복소 곱셈법

완성도를 높이기 위해 D(2개의 원소의 곱으로 작성 가능)에 따라 타원곡선을 작성할 수 있는 방법인 복소 곱셈의 개요를 제공한다.

$먼저{\displaystyle }$ D${\displaystyle }$${\$ - ${\displaystyle 3}$ ($displaystyle$ D \ $neq$ -$$3$$ )및 D $4 -$ ( $displaystyle$D \ neq - 4 $$)라고 가정합니다(이러한 경우는 훨씬 간단합니다).복소수로서 판별 D 차수의 h(D) 등급의 타원 j 불변량을 계산할 필요가 있다.이를 계산하는 공식은 여러 가지가 있습니다.

다음으로 h(D) 값에 대응하는 루트를 갖는 모노 $다항식{\displaystyle {}_{}}$ ${\displaystyle H_{}}$ D$)$ {$displaystyle$ H_${D}(X$를 작성합니다.${\displaystyle {참고}_{}}$로 H${\displaystyle {}_{}D}$( X )$${ $displaystyle H_{D}(X)}$는 클래스 다항식입니다.복소수 곱셈 이론에서 ${\displaystyle {우리}_{}}$는 H ${\displaystyle D{}_{}}$(${\displaystyle }$X )$$({$displaystyle H_{D}(X$)})가 정수 계수를 $가지고{\displaystyle {}_{}}$ 있다는 것을 알고 있습니다.이것에 의해, 우리는 이러한 계수를 충분히 정확하게 추정해, 그 참값을 찾아낼 수 있습니다.

여기서 N이 소수일 경우 CM은 D가 선택되고 N이 두 원소의 곱으로 분할된다는 사실에 근거하여 $)$ {$displaystyle H_{D}(X)}$가 모듈로 N을 h(D) 선형 인자의 곱으로 분할한다는 $것$을 알 수 있습니다.이제 j가 h(D) 루트 모듈 N의 하나일 경우 E를 다음과 같이 정의할 수 있습니다.

$({displaystyle y^{2}=x^{3}-3gc^{2r}x+2gc^{3r},{\text{여기}k=sgcfrac{j}{j-1728}}})$

c는 임의의 2차 비잔류 모드 N이고 r은 0 또는 1입니다.

루트 j가 주어졌을 때, E의 가능한 비동형 선택은 2개뿐이며, 각 선택 r에 대해 1개이다.이 곡선의 카디널리티는 다음과 같습니다.

${\displaystyle E}$(${\displaystyle Z\mathbb{}}$ / ${\displaystyle N\mathbb{}}$Z ) ${\displaystyle =N}$ +${\displaystyle 1}$ -$$\ $displaystyle$E ( \ $mathbb { Z$} /$N$ \ $mathbb { Z$${\displaystyle }$} ) ${\displaystyle =N}$+ $1$${\displaystyle }$+ a$$\ $displaystyle$ E ( \ $mathbbb { Z$/ $N$\ $mathbb$ { Z } ) =$N$ + ${\displaystyle 1}$ - a \ mathbbb {$Z$}

논의

골드워서-킬리언 테스트와 마찬가지로 이 테스트도 다운런 절차로 이어집니다.여기서도 범인은 q입니다.일단 동작하는 q를 찾으면 prime인지 확인해야 하기 때문에 실제로는 q에 대해 전체 테스트를 수행하고 있습니다.다시 한 번 q 인자에 대한 검정을 수행해야 할 수 있습니다.이는 각 레벨에서 타원곡선 E, m 및 의심스러운 소수, q를 갖는 중첩된 인증서로 이어집니다.

Atkin-Morain ECPP의 예

Atkin-Morain ECPP 테스트를 사용하여 N ${\displaystyle =}$ $({displaystyle$ N$=display})$이 프라임임을 증명하는 예를 구축한다.먼저 Legendre 기호$({\displaystyle D/N)}$ ${\displaystyle =}$ $(Displaystyle (D/N$)=$1$인지, 4N이 ${\displaystyle \mathrm{4N}}$ ${\displaystyle =}$ ${\displaystyle {}^{}{2\mathrm{}}^{}}$ + ${\displaystyle D{}^{}}$ ${\displaystyle {b\mathrm{}}^{}}$2({$displaystyle 4N=a^{2$}+ $D^{2$로 기록될 수 있는지 테스트하면서 가능한 13개의 식별자 세트를 진행합니다.

이 $예$에서는 D $=$ - ${\displaystyle 43}${\$displaystyle$ D=-$43}$이(가) 선택되었습니다.이는${\displaystyle }$(${\displaystyle D}$/${\displaystyle N}$ ) ${\displaystyle =}$( - ${\displaystyle 43}$/${\displaystyle 167}$ ) $=$ ${\displaystyle 1}$ { $displaystyle$(D$/N$) = 4 $43$${\displaystyle }$( ${\displaystyle 167}$) ${\displaystyle =}$ $25$2${\displaystyle }$+ (${\displaystyle 43}$) ( ${\displaystyle {1\mathrm{}}^{}}$)$$( 2 ) ( \ $displaystyle$4 \$cd$ ( 167) $= 25$^$${ 1 ( $43$ )

다음 단계는 m을 계산하는 것입니다.이는 m ${\displaystyle =}$ ${\displaystyle N}$+${\displaystyle 1}$ - ${\displaystyle a}${$displaystyle$ m$=N+1-a}$로 쉽게 수행되며 m ${\displaystyle =}$ ${\displaystyle 167}$+${\displaystyle 1}$ - ${\displaystyle 25}$ ${\displaystyle =\mathrm{}}$${\displaystyle 143}$이 $됩니다{\displaystyle }$.$다음$으로 m의$$소수(q라고 함$)$를 찾아야 합니다$.$q ( 1/4 +)2 .{{ $displaystyle$ q > ( $N ^$ { 1 / $}$ + $1)^{2$} 을 충족해야 합니다.

이 경우, m = 143 = 11×13이다.그래서 불행하게도 우리는 11이나 13을 q로 선택할 수 없다. 왜냐하면 그것은 필요한 불평등을 충족시키지 못하기 때문이다.그러나 우리는 ^[13]Morain의 논문에서 나온 Goldwasser-Kilian 알고리즘 이전에 설명한 것과 유사한 제안을 통해 구원을 받을 수 있다.m을 지정하면 m, ( 1 / + ) 2( \ $displaystyle$ s > ( $N^$ {$1$ / $4 }$ + $1)^{$2을(를) 찾을 수 있지만 반드시 소수일 필요는 없으며$,$ ${\displaystyle {pi}_{}}$마다 p_${displaystyle p_i$}를$$ 분할할 수 있는지 여부를 확인합니다.

${\displaystyle(m/p_{i})P\neq P_{\infty }}$

아직 생성되지 않은 곡선의 P점에 대한 것입니다.

만약 s가 부등식을 만족하고, 그 소인수가 위의 소인수를 만족시킨다면, N은 소인수이다.

따라서 이 경우 s = m = 143을 선택합니다.$따라서{\displaystyle {}_{}}$ 가능한$$(디스플레이 $스타일 p_{i$는 11과 13입니다.우선 143 ( 1 / +) ({$displaystyle$ 143 > ($167^{1/4$} +$1$)^{$2$ 이므로 값만 체크하면 됩니다.

${\displaystyle(143/11)P=13P\qquad(텍스트 { 및 }})\qquad(13/13)P=11P.}$

하지만 이 작업을 하기 전에 곡선을 만들고 P점을 선택해야 합니다.곡선을 만들기 위해 우리는 복소 곱셈을 이용한다.이 경우 J-불변량을 계산합니다.

${\displaystyle j\equiv -960^{3}{\pmod {filename}}\equiv 107pmod {filename}}.}$

다음으로 계산

${\displaystyle k=black {j}{1728-j}}{\pmod {block}}\equiv 158pmod {block}}$

타원 곡선이 다음과 같은 형태라는 것을 알 수 있습니다.

${\displaystyle {y\mathrm{}}^{}}$ 2 ${\displaystyle {}^{}}$ ${\displaystyle {}^{}{3\mathrm{}}^{}}$ + ${\displaystyle 3}$ k ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}{}^{}}$ + ${\displaystyle 2}$ ${\displaystyle k}$ ${\displaystyle {c\mathrm{}}^{}}$3 { $displaystyle$ y^ {2} =$x$^ {3} +$$3 display ^ {$2} x$ + 2 display ^ {3}$$$,$

여기서 k는 앞에서 설명한 바와 같이, c는 F $(\$에서 정사각형이 아닌 값입니다.따라서 다음과 같이 시작할 수 있습니다.

$({displaystyle}\displaystyle {argined}r&=0\3k&\equiv 140mod {argined}\2k&\equiv 149mod {argined}\end {argined})$

그 결과

$(\displaystyle E:y^{2}=x^{3}+140x+149{\pmod {display}})$

이제 E의 P = (6,6) 점을 사용하여 ${\displaystyle \mathrm{143}}$ P ${\displaystyle =}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ .$${ $displaystyle 143P$=$P_{\infty }$을 확인할 수 있습니다.

13(6, 6) = (12, 65) 및 11P = (140, 147)을 확인하는 것은 간단하며, 따라서 Morain의 명제에 따르면 N은 소수이다.

복잡성과 실행 시간

골드워서와 킬리안의 타원곡선 프라임리티 증명 알고리즘은 적어도 1년간 예상되는 다항식 시간으로 종료된다.

${\displaystyle 1-O\left(2^{-N{\frac {1}{\log \log n}}}\right)}$

주요 입력값입니다.

추측

${\displaystyle (}$ (${\displaystyle x}$) { $displaystyle \pi ($x ) the 。

$\displaystyle \pi c_{1}, c_{2}> 0:\pi (x+{\pirt {x})-\pi (x)\geq {c_{2}{\pirt {x}}{\log ^{c_{1}}}$

충분히 큰 x에 대해서.

이 추측을 받아들이면 Goldwasser-Kilian 알고리즘은 모든 입력에 대해 예상되는 다항식 시간으로 종료됩니다.또한 N의 길이가 k일 경우 알고리즘은 O${\displaystyle ({k\mathrm{}}^{}}$ 4$)\displaystyle$ O$(k^{4$^[14]로 확인할 수 있는 사이즈${\displaystyle }O{\displaystyle }$($k$2)의$$ 증명서를 작성합니다.

또 다른 추측을 생각해 봅시다.알고리즘의 총 시간에 대한 한계를 알 수 있습니다.

추측 2

$(\$과 $(\$의 양의 $상수$가 존재한다고 가정합니다.

${\displaystyle [x}$ ,${\displaystyle }$x + ${\displaystyle 2\sqrt{x}}$ ${\displaystyle ]}$ , ${\displaystyle x2}$2 ( x , $x +$ { \ $displayrt${ 2 $x$} ) ,$x$ \ $geq$2 ${\displaystyle \mathrm{is<img\; alt="[x,x+\{\backslash sqrt\; \{2x\}\}],x\backslash geq\; 2"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/9f135deed044ccfba12d1dc3d92b570a5304f492"\; style="vertical-align:\; -0.838ex;\; width:18.88ex;\; height:3.176ex;">}}$ ${\displaystyle {c\mathrm{}}_{}}$ $1$ ( $log$)x${\displaystyle {}^{}}$) -$$ $2$ ( \ $displaystyle$c _ { $1$} { \ $displayrt${ $x } ）$ 。

다음으로 Goldwasser Killian 알고리즘은 N의 primity를 다음 시간에 증명합니다.

$\displaystyle O(\log ^{10+c_{2}}n)}$^[13]

Atkin-Morain 알고리즘의 경우 기술된 실행 시간은 다음과 같습니다.

${\displaystyle O}$( ( ${\displaystyle \log n{}^{}}$N )${\displaystyle 6^{}}$ + $)$ ) \ $displaystyle$ O ( ( ( ( ( $log$ N ) ^{ 6 + \ $epsilon$} ) $>$ $0$） 。

특수 형식의 소수점

일부 숫자의 경우, 원시성 증명에 대한 '바로 가기'를 찾을 수 있습니다.이것은 메르센 수치들의 경우이다.사실, 소수를 더 쉽게 확인할 수 있는 특별한 구조 때문에, 알려진 가장 큰 6개의 소수들은 모두 메르센 ^[15]숫자이다.메르센 수의 원시성을 검증하기 위해 루카스라고 알려진 방법이 한동안 사용되어 왔다.레머 테스트이 검정은 타원 곡선에 의존하지 않습니다.그러나 우리는 ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle =}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$n -$$({$displaystyle$ N$=2^{k}n-1$$})$ $형태$의 $숫자$가${\displaystyle k}$, ${\displaystyle n\mathbb{},}$ ${\displaystyle Z}$, ${\$ 2({$displaystyle k, n\in$ \$mathbb {Z},$k$\geq2$ n 홀수가 타원 곡선을 사용하여 소수(또는 합성)임을 증명할 수 있는 결과를 제시한다.물론 이것은 또한 n = 1인 경우에 해당하는 메르센 수의 원시성을 입증하는 방법을 제공할 것이다.루카스라고 하는 타원 곡선(k 크기에 제한이 있음) 없이 이 형식의 숫자를 시험하는 방법이 있다.Lehmer-Riesel 검정.다음 방법은 타원 ${\displaystyle {}^{}}$을${\displaystyle \mathrm{사용}}$한 2kn -$$1({$displaystyle$ 2$^{k}n-1})$에 $대한{\displaystyle {\mathrm{}}^{}}$ 논문 Primality Test에서 도출한 것입니다.^[16]

E(F_N)의 그룹 구조

E를 타원곡선으로 삼습니다.여기서 E는 m${\displaystyle \mathrm{display}}$Z, m${\displaystyle display}$ ${\displaystyle 0}$ mod p$,$ \ $display$ m$\$$in$ \$mathbb$ { $Z}, m$$\$ \ equiv $0{\displaystyle {}^{}}$$$$$${\displaystyle \mathrm{modb}}$ {$p}$ ${\displaystyle p}$에 $대해$ ${\displaystyle {y\mathrm{}}^{}}$ 2 $=$ - m$$ \ $display$ y$^{2$} =$$x {3} -$resp}$ $형식$입니다${\displaystyle .}$k z ${\displaystyle Z\mathbb{},k2}$ 2, $n$ \$displaystyle k\in \mathbb$ {$Z},$k\$geq$2,n$}$ 홀수인$$ $}$$n$$,}.$

정리 1^[7] $\displaystyle E(\mathbb {F} _{p})=p+1.}$

정리 2.${\displaystyle }E{\displaystyle }$ ( ${\displaystyle {}_{}}$ ${\displaystyle )\cong }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {{\mathrm{}}^{}}_{}}$ ${\displaystyle {{}^{}}_{}}$n ( \ $displaystyle$ E ( \ $mathbb { F$ }$_${ $p$${\displaystyle {}_{}}$} ) \ $cong$ \$mathbb${$Z$}${\displaystyle {}_{}}$ Z ${\displaystyle {}_{}{\mathbb{}}_{}}$ Z $2$k - ${\displaystyle {{}^{}}_{}}$( \ $mathbb { F$ }$$$_${ $p }$ )

정리 3E 위의 Q = (x,y)가 x가 2차 비가산 모듈로 p가 되도록 하자.다음으로 Q의 순서는 사이클 $그룹{\displaystyle }$ E${\displaystyle ({}_{}}$ p${\displaystyle {}_{}}$의 $(\$ 2$^{k})$${\displaystyle {\mathbb{}}_{}}$ $.\displaystyle$ E$(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n$})로 나눌 수 있습니다.$}$

먼저 n이 $(\$ 2$^{k$에 비해 상대적으로 작은 경우를 제시합니다.이 경우 다음 정리가 하나 더 필요합니다.

정리 4 (\$displaystyle \lambda > 1$) 을 선택하고,

$\displaystyle n\leq {frac {p} {\frac} {\text {and}} \qquad \text\frt {p} > \ left \fright rt [ {p} + 1 \ right } {2}$

그러면 p는 Q = (${\displaystyle x_{}}$,y)가 E에 존재하는 경우에만 소수입니다. ${\displaystyle 예}$를 들어${\displaystyle {}_{}}$( ${\displaystyle S}$ i ,${\displaystyle }$p )$$ ${\displaystyle 1}$ { $displaystyle$ \gcd { ( $S _$ {$i$ ) p } =$1$$$= 1, 2, ..., k - 1 및 ${\displaystyle S_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 0}$( ${\displaystyle mod}$p${\displaystyle }$) ,$${ $display style 0$ . $equ}$laystyle $S_{0}=x$ 입니다.

알고리즘

주로 이론 3과 4에 의존하는 다음과 같은 알고리즘을 제공합니다.특정 $번호{\displaystyle }$ N$({displaystyle$N$\})$이 표시되어 있는지 확인하려면 다음 절차를 따릅니다.

(1) ( ${\displaystyle \frac{x}{}}$ N${\displaystyle }$) ${\displaystyle =}$ -$$ ( \ $displaystyle \ frac${ $x$} { N } \ $right$ )$=$ -$$1 $로서{\displaystyle }$ x${\displaystyle }$${\displaystyle z}$$$Z${\displaystyle }$, ${\displaystyle y0}$0 ( ${\displaystyle mod\mathrm{}}$2$$) \ $displaystyle y$\$$$in$ \ mathbbb$$${ Z$$}$$$、 \ $equiv$$}}\right)=$1$\}.$

m ${\displaystyle =}$ ${\displaystyle \frac{{x\mathrm{}}^{}}{}}$3 - ${\displaystyle \frac{{y\mathrm{}}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ x ${\displaystyle mod}$N ({$displaystyle$ m$=sq$ frac ${x^{3$}-$y^{2}})\mod$ N$$$m$ 0${\displaystyle }$( ${\displaystyle mod}$N$$){ $displaystyle$ m$\not$\ $equiv$ 0$pm$ pmod {$N}$ $)$를 선택합니다.

$Q{\displaystyle {}^{}}$ ${\displaystyle =}$ (${\displaystyle x}$ ,${\displaystyle y}$ )$${ $displaystyle$ Q ' = ($x$ ,$y$ ) }는${\displaystyle }$E : ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$3 - ${\displaystyle m}$x { \ $displaystyle$E : $y$^ {2} $= x$ {$3}$ - $mx$} 입니다.

Q ${\displaystyle =}$ ${\displaystyle {}^{}}$ Q $′$ { $displaystyle$ Q =$nQ$를 $계산$합니다. $Q{\displaystyle }$ ${\displaystyle \in }$ { \$$$displaystyle$Q \ $in$ E $}$이면 $N{\displaystyle }$ { \ $displaystyle$ N$}$은 컴포지트이고, 그렇지 않으면 (2)로 진행합니다.

(2) ${\displaystyle {초기값}_{}}$$Q{\displaystyle }$({$displaystyle$Q$\})$의 시퀀스로 Si$({$displaystyle $S_{i$})를 $설정$합니다.i $=$ {{$displaystyle$ i=}${\displaystyle }$1,${\displaystyle 2}$,${\displaystyle 3}$,${\displaystyle .,k}$ -$$({$display style$1,$2$, 3, $...k-1$에 대해$$({$displaystyle$ S_{i})를$$ $계산$합니다.

$gcd{\displaystyle }$( i , )$$>$${ $displaystyle$$\gcd$( { $S$_ {$i$ , $N$} >$1$ ） 。여기서 1${\displaystyle i}$ i${\displaystyle k}$ k -$$ { $displaystyle$1 \ $leq$i \ $leq$k -$$1 }이면$$N { $displaystyle$ N$$}은$$ 컴포지트입니다.그렇지 않으면 (3)으로 넘어갑니다.

(3) ${\displaystyle S_{}}$ k${\displaystyle {}_{}0}$0 ( ${\displaystyle mod}$N )$${ $displaystyle S_{k}\equiv$ 0 {\$pmod {N}}$이면 $N{\displaystyle {}_{}}$ ${\displaystyle$ N$}$은 $소수$이다.그렇지 않으면 N$(\displaystyle$ N$)$은 복합적입니다.이것으로 테스트가 완료되었습니다.

알고리즘의 정당화

(1)에서는 E상의 점 Q와 함께 Q의 x좌표가 2차 비잔류인 타원곡선 E가 선택된다.그렇다고 할 수 있다

${\displaystyle \left\frac {m}{N}\right}=\left({\frac {x}-y^{2}}{x}}{n}}\right)=\left({\frac {x}{N}\right})\left({\frac {x}-y}{N}}\right})}$

따라서 N이 소수일 경우 Q'는 정리 3에 의해 $({$$displaystyle$2$^{k$로 나누어질 수 있는 차수를 가지므로 Q'의 차수는 ${\displaystyle {}^{}}$d({$displaystyle$ 2^{$k}$$}$dn)이다.

즉, Q = nQ'의 $차수$는 $({$ 2$^{k$입니다.따라서 (1) N이 합성이라고 결론내린 경우, 그것은 진정한 합성이며 (2)와 (3) Q의 $차수$가 2 $(\$ 2$^{k$인지 확인한다.따라서 (2) 또는 (3)이 N이 합성이라고 결론내리면 합성이다.

알고리즘이 N을 소수라고 결론내린다면$$({$displaystyle S_{$1})은$$ $정리{\displaystyle {}_{}}$ 4의 조건을 만족하므로 N은 진정한 소수입니다.

n이 클 때의 알고리즘도 있습니다만, 이것에 대해서는 전술한 ^[16]기사를 참조해 주세요.

레퍼런스

외부 링크

• Atkin과 Morain에 의한 타원곡선과 원시성 증명.
• Weisstein, Eric W. "Elliptic Curve Primality Proving". MathWorld.
• Chris Caldwell, "Primality Providing 4.2: 타원 곡선과 ECPP 검정"
• 프랑수아 모랭, "ECPP 홈페이지" (일부 아키텍처의 오래된 ECP 소프트웨어 포함)
• Marcel Martin, "Primo" (64비트용 바이너리)
• PARI/GP, Atkin-Morain 및 Primo primality 증명서를 작성하는 함수를 가진 컴퓨터 대수 시스템
• GMP-ECPP, 무료 ECPP 실장
• LiDIA, ECP를 지원하는 Linux용 무료 C++ 라이브러리
• CM, ECPP 구현을 포함하는 다른 프리 라이브러리