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

В математике эллиптических кривых методы проверки простоты или доказательство простоты эллиптических кривых (ECPP) являются одними из самых быстрых и широко используемых методов доказательства простоты. Эту идею выдвинули Шафи Голдвассер и Джо Килиан в 1986 году и в том же году превратили в алгоритм AOL Atkin . Впоследствии алгоритм был изменен и улучшен несколькими сотрудниками, в частности Аткином и Франсуа Мореном в 1993 году. Идея использования эллиптических кривых при факторизации была разработана Х.В. Ленстрой в 1985 году, и последствия ее использования при проверке (и доказательстве) простоты последовали быстро.

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

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

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

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

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

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

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

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

Предложение

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

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

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

(1) мП = 0

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

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

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

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

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

и таким образом $\gcd(q,m_{p})=1$ и существует целое число u со свойством, что

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

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

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

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

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

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

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

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

Выберите случайным образом три целых числа: a, x, y и установите

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тест

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

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

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

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

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

Комплексный метод умножения

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

Предположим сначала, что $D\neq -3$ и $D\neq -4$ (эти случаи гораздо проще сделать). Необходимо вычислить эллиптические j-инварианты классов h ( D ) порядка дискриминанта D как комплексные числа . Для их расчета существует несколько формул.

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

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

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

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

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

$|E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a$ или $|E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a$

Обсуждение

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

Пример ECPP Аткина-Морена

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

что дает

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

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

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

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

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

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

простых входов.

Гипотеза

Позволять $\pi (x)$ количество простых чисел, меньших x

$\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 , алгоритм создает сертификат размера $O(k^{2})$ что можно проверить в $O(k^{4})$.

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

Гипотеза 2

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

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

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

$O(\log ^{10+c_{2}}n)$

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

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

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

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

Групповая структура E (F _N )

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

Теорема 1. $|E(\mathbb {F} _{p})|=p+1.$

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

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

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

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

$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 такой, что $\gcd {(S_{i},p)}=1$ для i = 1, 2, ..., k - 1 и $S_{k}\equiv 0{\pmod {p}},$ где $S_{i}$ представляет собой последовательность с начальным значением $S_{0}=x$.

Алгоритм

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

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

Брать $m={\frac {x^{3}-y^{2}}{x}}\mod N$ и $m\not \equiv 0{\pmod {N}}$.

Затем $Q'=(x,y)$ включен $E:y^{2}=x^{3}-mx$.

Рассчитать $Q=nQ'$. Если $Q\in E$ затем $N$ является составным, иначе переходим к (2).

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

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

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

Обоснование алгоритма

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

$\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' делится на $2^{k}$, по теореме 3,и, следовательно, порядок Q' равен $2^{k}d$ д | н .

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

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

Существует также алгоритм для случаев, когда n велико; однако для этого мы обратимся к вышеупомянутой статье.

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

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