Простота эллиптической кривой - Elliptic curve primality

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

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

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

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

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

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

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

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

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

Предложение

Тесты простоты эллиптической кривой основаны на критериях, аналогичных критерию Поклингтона, на котором основан этот тест, где группа заменяется на, а E - правильно выбранная эллиптическая кривая. Теперь мы сформулируем предложение, на котором будет основан наш тест, который аналогичен критерию Поклингтона и дает начало форме Голдвассера – Килиана – Аткина для проверки простоты эллиптической кривой. ${\ Displaystyle (\ mathbb {Z} / п \ mathbb {Z}) ^ {*}}$${\ Displaystyle Е (\ mathbb {Z} / п \ 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 \ вправо) ^ {2} <q}$

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

${\ Displaystyle uq \ эквив 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 , даст:

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

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

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

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

${\ Displaystyle б \ эквив у ^ {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}$

Если мы можем записать т в виде , где представляет собой небольшое целое число , а д большой вероятности того штрих (число , которое проходит вероятностный тест простоты , например), то мы не выбрасывайте E . В противном случае мы отбрасываем нашу кривую и случайным образом выбираем другую тройку (a, x, y), чтобы начать заново. Идея здесь состоит в том, чтобы найти m , которое делится на большое простое число q . Это простое в несколько цифр меньше , чем м (или N ) , поэтому д будет легче доказать , чем простое N . ${\ displaystyle m = kq}$${\ Displaystyle к \ 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 считается достаточно малым для применения нерекурсивного детерминированного алгоритма. ${\ displaystyle mP = 0}$${\ Displaystyle КП \ neq 0}$

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

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

Вторая проблема, которую отмечает Коблиц, - это трудность нахождения кривой E , количество точек которой имеет форму kq , как указано выше. Не существует известной теоремы, которая гарантирует, что мы сможем найти подходящее E за полиномиально много попыток. Распределение простых чисел на интервале Хассе , который содержит m , не то же самое, что распределение простых чисел в групповых порядках, считая кривые с кратностью. Однако на практике это не является серьезной проблемой. ${\ displaystyle [п + 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 а ^ {2} + | D | b ^ {2} = 4N \,}$

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

${\ Displaystyle | Е (\ 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 а ^ {2} + | D | b ^ {2} = 4N \,}$

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

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

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

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

Для полноты картины мы предоставим обзор комплексного умножения , способа, которым может быть создана эллиптическая кривая с учетом нашего 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 | Е (\ mathbb {Z} / N \ mathbb {Z}) | = N + 1-а}$ или ${\ Displaystyle | Е (\ mathbb {Z} / N \ mathbb {Z}) | = N + 1 + а}$

Обсуждение

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

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

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

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

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

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

${\ Displaystyle (м / р_ {я}) п \ 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}} \ Equ 107 {\ pmod {167}}.}$

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

${\ Displaystyle к = {\ гидроразрыва {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 {выровненный} r & = 0 \\ 3k & \ эквив 140 {\ pmod {167}} \\ 2k & \ эквив 149 {\ pmod {167}} \ конец {выровненный}}}$

который дает

${\ 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 \ пи (х)}$

${\ Displaystyle \ существует c_ {1}, c_ {2}> 0: \ pi (x + {\ sqrt {x}}) - \ pi (x) \ geq {\ frac {c_ {2} {\ sqrt {x }}} {\ log ^ {c_ {1}} x}}}$

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

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

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

Гипотеза 2

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

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

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

${\ Displaystyle О (\ log ^ {10 + c_ {2}} п)}$

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

${\ Displaystyle О ((\ журнал N) ^ {6+ \ epsilon})}$ для некоторых ${\ displaystyle \ epsilon> 0}$

Простые числа особой формы

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

Групповая структура ${\ Displaystyle E (\ mathbb {F} _ {N})}$

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

Теорема 1. ${\ 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_ {к} \ эквив 0 {\ pmod {p}},}$${\ displaystyle S_ {i}}$${\ displaystyle S_ {0} = x}$

Алгоритм

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

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

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

Тогда идет . ${\ Displaystyle Q '= (х, у)}$${\ 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 я \ Leq к-1}$${\ displaystyle N}$

(3) Если то простое. В противном случае - составной. На этом тест завершен. ${\ Displaystyle S_ {к} \ эквив 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 велико, однако для этого мы ссылаемся на вышеупомянутую статью.

использованная литература

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

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