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

Методы проверки простоты

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

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

Ранее известные методы доказательства простоты, такие как тест Поклингтона на простоту, требовали по крайней мере частичной факторизации для доказательства того, что является простым числом. В результате эти методы требовали некоторой удачи и, как правило, медленны на практике. ${\displaystyle N\pm 1}$ ${\displaystyle N}$

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

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

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

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

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

По состоянию на май 2023 года ^{[обновлять]}наибольшее простое число, доказанное с помощью метода ECPP, составляет . ^[5] Сертификация была проведена Андреасом Энге с использованием его программного обеспечения fastECPP CM . ${\displaystyle 5^{104824}+104824^{5}}$

Предложение

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

Пусть N — положительное целое число, а E — множество, определяемое уравнением Рассмотрим E, используя обычный закон сложения на E , и запишем 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) мП = 0

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

Тогда N — простое число.

Доказательство

Если N является составным, то существует простое число , которое делит N . Определим как эллиптическую кривую, определяемую тем же уравнением, что и E, но вычисленную по модулю  p, а не по модулю  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), поскольку вычисляется с использованием того же метода, что и mP , за исключением модуля  p, а не модуля  N (и ). ${\displaystyle mP_{p}}$ ${\displaystyle p\mid N}$

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

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

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

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

Выберите три случайных целых числа 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 . Если это удается, мы применяем критерий для принятия решения о том, является ли наша кривая E приемлемой. ${\displaystyle y^{2}=x^{3}+ax+b}$

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

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

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

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

Проблемы с алгоритмом

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

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

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

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

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

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

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

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

Для некоторых a, b . Если мы можем описать 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 ) порядка в равен 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. Обратите внимание, что если m не имеет большого простого множителя или не может быть разложено на множители достаточно быстро, можно сделать другой выбор D. ^[1]

Метод комплексного умножения

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

Предположим сначала, что и (эти случаи гораздо проще сделать). Необходимо вычислить эллиптические j-инварианты классов h ( 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] [10] [12]} ${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a}$

Обсуждение

Как и в случае с тестом Голдвассера–Киллиан, этот приводит к процедуре down-run. Опять же, виновником является 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 , поскольку это не удовлетворяет необходимому неравенству. Однако нас спасает аналогичное предложение тому, которое мы высказали перед алгоритмом Голдвассера–Килиана, которое взято из статьи Морейна. ^[13] Оно гласит, что, учитывая наше m , мы ищем s , которое делит m , , но не обязательно является простым, и проверяем, для каждого ли делящего 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 , то алгоритм создает сертификат размера , который может быть проверен за . ^[14] ${\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)}$^[13]

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

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

Простые числа специального вида

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

Групповая структураЭ(ФН)

Мы берем 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. ^[7] ${\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. Выберите и предположим ${\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}$

Вычислить . Если то является составным, в противном случае перейти к (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 | n . ${\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 велико; однако для этого мы отсылаем к вышеупомянутой статье. ^[16]

Ссылки

1. Henri Cohen, Gerhard Frey, ed. (2006). Справочник по эллиптической и гиперэллиптической криптографии . Boca Raton: Chapman & Hall/CRC.
2. Топ, Яап, Доказательство простоты эллиптической кривой , http://www.math.rug.nl/~top/atkin.pdf
3. Atkin, AOL; Morain, F. (1993). «Эллиптические кривые и доказательство простоты». Mathematics of Computation . 61 (203): 29–68. doi : 10.2307/2152935 . JSTOR  2152935.
4. Ленстра, АК; Ленстра, HW (1990). «Алгоритмы в теории чисел». Алгоритмы и сложность (PDF) . стр. 673–715. дои : 10.1016/B978-0-444-88071-0.50017-5. ISBN 9780444880710.
5. Колдуэлл, Крис. Двадцатка лучших: доказательство простоты эллиптической кривой из Prime Pages .
6. Сэмюэл С. Вагстафф-младший (2013). Радость факторизации. Провиденс, Род-Айленд: Американское математическое общество. стр. 187–188. ISBN 978-1-4704-1048-3.
7. Вашингтон, Лоуренс К. , Эллиптические кривые: теория чисел и криптография , Chapman & Hall/CRC, 2003
8. Koblitz, Neal, Введение в теорию чисел и криптографию , 2-е изд., Springer, 1994
9. "Queen's University Canada" (PDF) . Архивировано из оригинала (PDF) 2016-03-04 . Получено 2010-01-22 .
10. Блейк, И.; Серусси, Г.; Смарт, Н. (1999). Эллиптические кривые в криптографии . doi :10.1017/CBO9781107360211. ISBN 9780521653749.
11. Ленстра, Хендрик В., Эффективные алгоритмы в теории чисел , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf
12. ECPP возвращается algo.inria.fr
13. Морейн, Ф. (1988). "Реализация алгоритма проверки простоты Аткина-Гольдвассера-Килиана" (PDF) . S2CID  118191463.
14. Голдвассер, Шафи, Килиан, Джо, Почти все простые числа можно быстро сертифицировать , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Архивировано 18 июля 2011 г. на Wayback Machine
15. «Самое большое известное простое число по годам: краткая история».
16. Tsumura, Yu (2009). "Тесты простоты для использования эллиптических кривых". arXiv : 0912.5279v1 [math.NT]. ${\displaystyle 2^{k}n-1}$

Внешние ссылки

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