Простота эллиптической кривой

В математике , эллиптической кривой на простоту тестирования методов, или эллиптическая кривая доказательство простоты чисел (ЕКПП), являются одними из самых быстрых и наиболее широко используемых методов в прувинга простоты чисел. ^[1] Эта идея была выдвинута Шафи Голдвассером и Джо Килианом в 1986 году и в том же году преобразована в алгоритм AOL Atkin . Впоследствии алгоритм был изменен и улучшен несколькими сотрудниками, в частности Аткином и Франсуа Мореном  [ де ] , в 1993 году. ^[2] Концепция использования эллиптических кривых в факторизации была разработана HW Lenstraв 1985 году, и вскоре последовали выводы для его использования в тестировании (и доказательстве) примитивности.

Тестирование на примитивность - это область, которая существует со времен Ферма , когда большинство алгоритмов основывались на факторинге, который становился громоздким с большими входными данными ; современные алгоритмы решают проблемы определения того, является ли число простым и каковы его множители по отдельности. Это приобрело практическое значение с появлением современной криптографии. Хотя многие текущие тесты приводят к вероятностному выходу ( N либо показано составным, либо, вероятно, простым, как, например, с тестом на простоту Бейли – PSW или тестом Миллера – Рабина ), тест эллиптической кривой доказывает простоту (или составность) с помощью быстрого проверяемый сертификат. ^[3]

Доказательство простоты эллиптической кривой обеспечивает альтернативу (среди прочего) тесту простоты Поклингтона , который может быть трудно реализовать на практике.

Доказательство простоты эллиптической кривой [ править ]

Это универсальный алгоритм , то есть он не зависит от числа особой формы. ECPP в настоящее время на практике является самым быстрым из известных алгоритмов для проверки простоты общих чисел, но время выполнения наихудшего случая неизвестно. ECPP эвристически работает во времени:

${\ Displaystyle О ((\ журнал п) ^ {5+ \ varepsilon}) \,}$

для некоторых . ^[4] Этот показатель может быть уменьшен для некоторых версий с помощью эвристических аргументов. ECPP работает так же, как и большинство других тестов на простоту , обнаруживая группу и показывая, что ее размер является простым. Для ECPP группа - это эллиптическая кривая над конечным набором квадратичных форм, факторизация которой по группе тривиальна.${\ displaystyle \ varepsilon> 0}$${\ displaystyle 4+ \ varepsilon}$${\ displaystyle p}$${\ displaystyle p-1}$

ЕКПП генерирует Аткин - Гольдвасер -Kilian-морену сертификат из простоты по рекурсии , а затем пытается проверить сертификат. Шаг, который занимает больше всего процессорного времени, - это создание сертификата, потому что необходимо выполнить факторинг по полю класса . Сертификат можно быстро проверить, поэтому проверка работоспособности займет очень мало времени.

По состоянию на февраль 2020 года наибольшее простое число, подтвержденное методом ECPP, состояло из 40000 цифр. ^[5] Сертификация Пола Андервуда заняла 21,5 месяца с использованием программного обеспечения Primo Марселя Мартина.

Предложение [ править ]

Тесты простоты эллиптической кривой основаны на критериях, аналогичных критерию Поклингтона, на котором основан этот тест ^[6], где группа заменяется на, а E - правильно выбранная эллиптическая кривая. Теперь мы сформулируем предложение, на котором будет основан наш тест, который аналогичен критерию Поклингтона и дает начало форме Голдвассера – Килиана – Аткина для проверки простоты эллиптической кривой.${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$${\displaystyle E(\mathbb {Z} /n\mathbb {Z} ),}$

Пусть N быть положительным целым числом, и Е множество , которое определяется уравнением Рассмотрим Е над использовать обычный закон сложения на Е , и писать 0 для нейтрального элемента на E .${\displaystyle y^{2}=x^{3}+ax+b{\bmod {N}}.}$${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$

Пусть m - целое число. Если существует простое число q, которое делит m , больше и существует точка P на E такая, что${\displaystyle \left({\sqrt[{4}]{N}}+1\right)^{2}}$

(1) mP = 0

(2) ( m / q ) P определено и не равно 0

Тогда N простое.

Доказательство [ править ]

Если N составное, то существует простое число , которое делит N . Определить , как эллиптической кривой , определяемой тем же уравнением , как Е , но оцениваемой по модулю  р , а не по модулю  N . Определите как порядок группы . По теореме Хассе об эллиптических кривых мы знаем${\displaystyle p\leq {\sqrt {N}}}$${\displaystyle E_{p}}$${\displaystyle m_{p}}$${\displaystyle E_{p}}$

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

и, следовательно, существует целое число u со свойством, что${\displaystyle \gcd(q,m_{p})=1}$

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

Позвольте быть точкой P, вычисленной по модулю p . Таким образом, мы имеем${\displaystyle P_{p}}$${\displaystyle E_{p}}$

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

согласно (1), as вычисляется с использованием того же метода, что и mP , за исключением того, что по модулю  p, а не по модулю  N (и ).${\displaystyle mP_{p}}$${\displaystyle p\mid N}$

Это противоречит (2), потому что если ( m / q ) P определено и не равно 0 (mod  N ), то тот же метод, вычисленный по модулю  p вместо модуля  N , даст: ^[7]

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

Алгоритм Гольдвассера – Килиана [ править ]

Из этого предложения можно построить алгоритм, чтобы доказать, что целое число N является простым. Это делается следующим образом:

Выберите наугад три целых числа a, x, y и установите

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

Теперь P = ( x , y ) - точка на E , где E определяется как . Далее нам нужен алгоритм для подсчета количества точек на E . Применительно к E этот алгоритм (Коблиц и другие предлагают алгоритм Шуфа ) дает число m, которое представляет собой количество точек на кривой E над F _N , при условии, что N является простым. Если алгоритм подсчета точек останавливается на неопределенном выражении, это позволяет определить нетривиальный множитель N${\displaystyle y^{2}=x^{3}+ax+b}$. Если это удается, мы применяем критерий для определения приемлемости нашей кривой E.

Если мы можем записать т в виде , где есть небольшое число и д вероятная простой (оно прошло некоторый предыдущий вероятностный тест простоты , к примеру), то мы не выбрасывайте E . В противном случае мы отбрасываем нашу кривую и случайным образом выбираем другую тройку (a, x, y), чтобы начать заново. Идея здесь состоит в том, чтобы найти m , которое делится на большое простое число q . Это простое число будет иметь примерно ту же величину, что и m для достаточно большого m .${\displaystyle m=kq}$${\displaystyle k\geq 2}$

Предположим , что мы находим кривую , которая проходит по критерию, к вычислению тР и кП . Если какие - либо из двух расчетов производит неопределенное выражение, мы можем получить нетривиальный фактор N . Если оба расчета успешны, мы исследуем результаты.

Если ясно, что N не является простым числом, потому что если бы N было простым, то E имел бы порядок m , и любой элемент E стал бы 0 при умножении на m . Если kP = 0, то алгоритм отбрасывает E и начинает заново с другой тройкой a, x, y .${\displaystyle mP\neq 0}$

Теперь, если, а затем наше предыдущее предложение говорит нам, что N простое число. Однако есть одна возможная проблема - простота q . Это проверяется с использованием того же алгоритма. Итак, мы описали рекурсивный алгоритм , в котором простота N зависит от простоты q и меньших «вероятных простых чисел» до тех пор, пока не будет достигнут некоторый порог, при котором q считается достаточно малым для применения нерекурсивного детерминированного алгоритма. ^{[8] [9]}${\displaystyle mP=0}$${\displaystyle kP\neq 0}$

Проблемы с алгоритмом [ править ]

Аткин и Морейн заявляют, что «проблема с GK состоит в том, что алгоритм Шуфа кажется почти невозможным для реализации». ^[3] Очень медленно и громоздко подсчитывать все точки на E с использованием алгоритма Шуфа, который является предпочтительным алгоритмом для алгоритма Голдвассера – Килиана. Однако исходный алгоритм Шуфа недостаточно эффективен, чтобы обеспечить количество баллов за короткое время. ^[10] Эти комментарии следует рассматривать в историческом контексте, до того, как Элкис и Аткин усовершенствовали метод Шуфа.

Вторая проблема, которую отмечает Коблиц, - это трудность нахождения кривой E , количество точек которой имеет форму kq , как указано выше. Не существует известной теоремы, которая гарантирует, что мы сможем найти подходящее E за полиномиально много попыток. Распределение простых чисел на интервале Хассе , который содержит m , не то же самое, что распределение простых чисел в групповых порядках, считая кривые с кратностью. Однако на практике это не является серьезной проблемой. ^[7]${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$

Тест простоты эллиптической кривой Аткина – Морана (ECPP) [ править ]

В статье 1993 года Аткин и Морейн описали алгоритм ECPP, который позволяет избежать проблем, связанных с громоздким алгоритмом подсчета точек (Schoof's). Алгоритм по-прежнему основывается на утверждении, изложенном выше, но вместо того, чтобы произвольно генерировать эллиптические кривые и искать собственное m , их идея состояла в том, чтобы построить кривую E, количество точек которой легко вычислить. Комплексное умножение - ключ к построению кривой.

Теперь, дал N , для которых потребность простоты будет доказана , мы должны найти подходящие м и д , так же , как в тесте Гольдвасер-Килиан, который будет выполнять предложение и доказать простоты N . (Конечно, также должны быть найдены точка P и сама кривая E. )

ECPP использует комплексное умножение для построения кривой E , делая это таким образом, чтобы можно было легко вычислить m (количество точек на E ). Теперь опишем этот метод:

Использование комплексного умножения требует отрицательного дискриминанта , D , такие , что D может быть записан как произведение двух элементов , или полностью эквивалентным образом , мы можем записать уравнение:${\displaystyle D=\pi {\bar {\pi }}}$

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

Для некоторых а, б . Если мы можем описать N в терминах любой из этих форм, мы можем создать эллиптическую кривую E на комплексном умножении (подробно описанном ниже), а количество точек определяется следующим образом:${\displaystyle \mathbb {Z} /N\mathbb {Z} }$

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

Чтобы N разделился на два элемента, нам это нужно (где обозначает символ Лежандра ). Это необходимое условие, и мы достигаем достаточности, если номер класса h ( D ) порядка in равен 1. Это происходит только для 13 значений D , которые являются элементами {−3, −4, −7, - 8, −11, −12, −16, −19, −27, −28, −43, −67, −163}${\displaystyle \left({\frac {D}{N}}\right)=1}$${\displaystyle \left({\frac {D}{N}}\right)}$ ${\displaystyle \mathbb {Q} ({\sqrt {D}})}$

Тест [ править ]

Выбираем дискриминанты D в порядке возрастания h ( D ). Для каждого D проверьте , можно ли записать 4 N как:${\displaystyle \left({\frac {D}{N}}\right)=1}$

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

Эта часть может быть проверена с помощью алгоритма Корнаккьи . После обнаружения приемлемых D и a произведите расчет . Теперь, если у m есть простой делитель q размера${\displaystyle m=N+1-a}$

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

используйте метод комплексного умножения, чтобы построить кривую E и точку P на ней. Тогда мы можем использовать наше предложение для проверки простоты N . Обратите внимание , что если м не имеет большой простой множитель или не могут быть разложены достаточно быстро, другой выбор D может быть сделан. ^[1]

Метод сложного умножения [ править ]

Для полноты картины мы предоставим обзор комплексного умножения , способа, которым может быть создана эллиптическая кривая с учетом нашего D (которое может быть записано как произведение двух элементов).

Предположим сначала, что и (эти случаи намного легче сделать). Это необходимо , чтобы вычислить эллиптические J-инварианты на час ( D ) классов порядка дискриминантной D в качестве комплексных чисел. Для их расчета существует несколько формул.${\displaystyle D\neq -3}$${\displaystyle D\neq -4}$

Затем создайте монический многочлен , корни которого соответствуют значениям h ( D ). Обратите внимание, что это полином класса . Из теории комплексного умножения мы знаем, что у него есть целые коэффициенты, что позволяет нам достаточно точно оценить эти коэффициенты, чтобы определить их истинные значения.${\displaystyle H_{D}(X)}$${\displaystyle H_{D}(X)}$${\displaystyle H_{D}(X)}$

Теперь, если N простое, CM сообщает нам, что разбивает по модулю  N на произведение h ( D ) линейных множителей, основываясь на том факте, что D было выбрано так, что N разбивается как произведение двух элементов. Теперь, если j является одним из корней h ( D ) по модулю N, мы можем определить E как:${\displaystyle H_{D}(X)}$

${\displaystyle y^{2}=x^{3}-3kc^{2r}x+2kc^{3r},{\text{ where }}k={\frac {j}{j-1728}},}$

c - любой квадратичный невычет по модулю N , а r равно 0 или 1.

Для данного корня j существует только два возможных неизоморфных выбора E , по одному для каждого выбора r . Мощность этих кривых равна

${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a}$или ^{[1] [9] [11]}${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a}$

Обсуждение [ править ]

Как и в случае с тестом Голдвассера – Киллиана, этот тест ведет к процедуре спуска. Опять же, виноват q . Как только мы находим q, который работает, мы должны проверить его на простоту, так что фактически мы проводим весь тест для q . С другой стороны, нам, возможно, придется выполнить тест на множители q . Это приводит к вложенному сертификату, где на каждом уровне у нас есть эллиптическая кривая E , m и сомнительное простое число  q .

Пример ECPP Аткина – Морейна [ править ]

Мы построим пример, чтобы доказать, что это простое число, используя тест ECPP Аткина – Морейна. Сначала просмотрите набор из 13 возможных дискриминантов, проверяя, можно ли записать символ Лежандра и 4 N как .${\displaystyle N=167}$${\displaystyle (D/N)=1}$${\displaystyle 4N=a^{2}+|D|b^{2}}$

Для нашего примера выбран. Это потому, что, а также, используя алгоритм Корнаккьи , мы знаем это, и, следовательно, a = 25 и b = 1.${\displaystyle D=-43}$${\displaystyle (D/N)=(-43/167)=1}$${\displaystyle 4\cdot (167)=25^{2}+(43)(1^{2})}$

Следующим шагом будет вычисление m . Это легко сделать, что дает. Далее нам нужно найти вероятный простой делитель числа m , который был обозначен как q . Он должен удовлетворять условию, что${\displaystyle m=N+1-a}$${\displaystyle m=167+1-25=143.}$${\displaystyle q>(N^{1/4}+1)^{2}.}$

В данном случае m = 143 = 11 × 13. Так что, к сожалению, мы не можем выбрать 11 или 13 в качестве q , поскольку это не удовлетворяет необходимому неравенству. Однако нас спасает утверждение, аналогичное тому, которое мы сформулировали перед алгоритмом Голдвассера – Килиана, которое взято из статьи Морейна. ^[12] В нем говорится, что учитывая м , мы ищем с которой делит м , , но не обязательно простое, и проверить, для каждого , который делит s${\displaystyle s>(N^{1/4}+1)^{2}}$${\displaystyle p_{i}}$

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

для некоторой точки P на нашей еще не построенной кривой.

Если s удовлетворяет неравенству, а его простые множители удовлетворяют указанным выше условиям, то N простое число.

Итак, в нашем случае мы выбираем s = m = 143. Таким образом, наши возможные значения - 11 и 13. Во-первых, это ясно , поэтому нам нужно только проверить значения${\displaystyle p_{i}}$${\displaystyle 143>(167^{1/4}+1)^{2}}$

${\displaystyle (143/11)P=13P\qquad {\text{ and }}\qquad (143/13)P=11P.}$

Но прежде чем мы сможем сделать это, мы должны построить нашу кривую, и выберем точку P . Чтобы построить кривую, мы используем комплексное умножение. В нашем случае мы вычисляем J-инвариант

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

Далее мы вычисляем

${\displaystyle k={\frac {j}{1728-j}}{\pmod {167}}\equiv 158{\pmod {167}}}$

и мы знаем, что наша эллиптическая кривая имеет вид:

${\displaystyle y^{2}=x^{3}+3kc^{2}x+2kc^{3}}$,

где k , как описано ранее, а c - не квадрат в . Итак, мы можем начать с${\displaystyle \mathbb {F} _{167}}$

${\displaystyle {\begin{aligned}r&=0\\3k&\equiv 140{\pmod {167}}\\2k&\equiv 149{\pmod {167}}\end{aligned}}}$

который дает

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

Теперь, используя точку P = (6,6) на E, можно проверить, что${\displaystyle 143P=P_{\infty }.}$

Несложно проверить, что 13 (6, 6) = (12, 65) и 11 P = (140, 147), а значит, по предложению Морана N простое число.

Сложность и время выполнения [ править ]

Алгоритм доказательства простоты эллиптических кривых Голдвассера и Килиана завершается за ожидаемое полиномиальное время как минимум в течение

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

основных входов.

Гипотеза [ править ]

Пусть будет количество простых чисел меньше x${\displaystyle \pi (x)}$

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

при достаточно большом x .

Если принять эту гипотезу, то алгоритм Голдвассера – Килиана завершается за ожидаемое полиномиальное время для каждого входа. Кроме того, если наше N имеет длину k , тогда алгоритм создает сертификат размера, который можно проверить . ^[13]${\displaystyle O(k^{2})}$${\displaystyle O(k^{4})}$

Теперь рассмотрим другую гипотезу, которая даст нам оценку общего времени работы алгоритма.

Гипотеза 2 [ править ]

Предположим, что существуют положительные константы и такие, что количество простых чисел в интервале${\displaystyle c_{1}}$${\displaystyle c_{2}}$

${\displaystyle [x,x+{\sqrt {2x}}],x\geq 2}$ больше чем ${\displaystyle c_{1}{\sqrt {x}}(\log x)^{-c_{2}}}$

Затем алгоритм Гольдвассера-Килиана доказывает простоту N за ожидаемое время

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

Для алгоритма Аткина – Морана заявленное время работы составляет

${\displaystyle O((\log N)^{6+\epsilon })}$для некоторых ^[3]${\displaystyle \epsilon >0}$

Простые числа особой формы [ править ]

Для некоторых форм чисел можно найти «короткие пути» к доказательству простоты. Так обстоит дело с числами Мерсенна . Фактически, из-за их особой структуры, которая позволяет упростить проверку простоты, шесть наибольших известных простых чисел являются числами Мерсенна. ^[14] Некоторое время использовался метод проверки простоты чисел Мерсенна, известный как тест Лукаса-Лемера . В этом тесте не используются эллиптические кривые. Однако мы представляем результат, в котором числа вида где , n нечетное можно доказать простыми (или составными) с помощью эллиптических кривых. Конечно, это также обеспечит метод доказательства простоты чисел Мерсенна, которые соответствуют случаю, когда n${\displaystyle N=2^{k}n-1}$${\displaystyle k,n\in \mathbb {Z} ,k\geq 2}$= 1. Существует метод проверки этой формы чисел без эллиптических кривых (с ограничением на размер k), известный как тест Лукаса – Лемера – Ризеля . Следующий метод взят из статьи Ю. Цумуры « Тест на простоту для использования эллиптических кривых${\displaystyle 2^{k}n-1}$ ». ^[15]

Структура группы ${\displaystyle E(\mathbb {F} _{N})}$[ править ]

Мы возьмем E в качестве нашей эллиптической кривой, где E имеет вид для где простое и с нечетным.${\displaystyle y^{2}=x^{3}-mx}$${\displaystyle m\in \mathbb {Z} ,m\not \equiv 0{\bmod {p}},}$${\displaystyle p\equiv 3{\bmod {4}}}$${\displaystyle p+1=2^{k}n,}$${\displaystyle k\in \mathbb {Z} ,k\geq 2,n}$

Теорема 1. ^[6] ${\displaystyle E(\mathbb {F} _{p})=p+1.}$

Теорема 2. или в зависимости от того, является ли m квадратичным вычетом по модулю p .${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}}$${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2}\oplus \mathbb {Z} _{2^{k-1}n}}$

Теорема 3. Пусть Q = ( x , y ) на E таково, что x квадратичный невычет по модулю p . Тогда порядок Q делится на в циклической группе${\displaystyle 2^{k}}$${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}.}$

Сначала мы представим случай, когда n относительно мало , и для этого потребуется еще одна теорема:${\displaystyle 2^{k}}$

Теорема 4. Выберем a и предположим${\displaystyle \lambda >1}$

${\displaystyle n\leq {\frac {\sqrt {p}}{\lambda }}\qquad {\text{and}}\qquad \lambda {\sqrt {p}}>\left({\sqrt[{4}]{p}}+1\right)^{2}.}$

Тогда p является простым числом тогда и только тогда, когда существует Q = ( x , y ) на E , такое, что для i = 1, 2, ..., k  - 1 и где - последовательность с начальным значением${\displaystyle \gcd {(S_{i},p)}=1}$${\displaystyle S_{k}\equiv 0{\pmod {p}},}$${\displaystyle S_{i}}$${\displaystyle S_{0}=x}$

Алгоритм [ править ]

Мы предлагаем следующий алгоритм, который в основном опирается на теоремы 3 и 4. Чтобы проверить простоту данного числа , выполните следующие шаги:${\displaystyle N}$

(1) Выберите такое, что , и найдите такое, что .${\displaystyle x\in \mathbb {Z} }$${\displaystyle \left({\frac {x}{N}}\right)=-1}$${\displaystyle y\in \mathbb {Z} ,y\not \equiv 0{\pmod {2}}}$${\displaystyle \left({\frac {x^{3}-y^{2}}{N}}\right)=1}$

Возьми и .${\displaystyle m={\frac {x^{3}-y^{2}}{x}}\mod N}$${\displaystyle m\not \equiv 0{\pmod {N}}}$

Тогда идет .${\displaystyle Q'=(x,y)}$${\displaystyle E:y^{2}=x^{3}-mx}$

Рассчитайте . Если then составное, в противном случае переходите к (2).${\displaystyle Q=nQ'}$${\displaystyle Q\in E}$${\displaystyle N}$

(2) Установить как последовательность с начальным значением . Рассчитать для .${\displaystyle S_{i}}$${\displaystyle Q}$${\displaystyle S_{i}}$${\displaystyle i=}$${\displaystyle 1,2,3,...,k-1}$

Если для разряда , то где тогда составной. В противном случае переходите к (3).${\displaystyle \gcd({S_{i},N})>1}$${\displaystyle i}$${\displaystyle 1\leq i\leq k-1}$${\displaystyle N}$

(3) Если то простое. В противном случае - составной. На этом тест завершен.${\displaystyle S_{k}\equiv 0{\pmod {N}}}$${\displaystyle N}$${\displaystyle N}$

Обоснование алгоритма [ править ]

В (1) выбрана эллиптическая кривая E вместе с точкой Q на E так , что координата x кривой Q является квадратичным невычетом. Мы можем сказать

${\displaystyle \left({\frac {m}{N}}\right)=\left({\frac {\frac {x^{3}-y^{2}}{x}}{N}}\right)=\left({\frac {x}{N}}\right)\left({\frac {x^{3}-y^{2}}{N}}\right)=-1\cdot 1=-1.}$

Таким образом, если N простое число, Q ' имеет порядок, кратный по теореме 3, и, следовательно, порядок Q' равен d | п .${\displaystyle 2^{k}}$${\displaystyle 2^{k}d}$

Это означает, что Q = nQ ' имеет порядок . Следовательно, если (1) заключает, что N составное, оно действительно составное. (2) и (3) проверяют, имеет ли Q порядок . Таким образом, если (2) или (3) заключают, что N составное, оно составное.${\displaystyle 2^{k}}$${\displaystyle 2^{k}}$

Теперь, если алгоритм приходит к выводу, что N является простым числом, это означает, что удовлетворяет условию теоремы 4, и поэтому N действительно простое число.${\displaystyle S_{1}}$

Также существует алгоритм для случаев, когда n велико, однако для этого мы ссылаемся на вышеупомянутую статью. ^[15]

Ссылки [ править ]

Внешние ссылки [ править ]

• Эллиптические кривые и простоты Доказывание по Аткин и морене.
• Вайсштейн, Эрик В. "Доказательство примитивности эллиптической кривой" . MathWorld .
• Крис Колдуэлл, «Доказательство первичности 4.2: эллиптические кривые и тест ECPP» на Prime Pages .
• Франсуа Морен, «Домашняя страница ECPP» (включает старое программное обеспечение ECPP для некоторых архитектур).
• Марсель Мартин, "Primo" (двоичный код для 64-разрядной версии Linux)
• PARI / GP , система компьютерной алгебры с функциями для создания сертификатов примитивности Аткин-Морейна и Primo
• GMP-ECPP , бесплатная реализация ECPP
• LiDIA , бесплатная библиотека C ++ для Linux с поддержкой ECPP