Jump to content

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

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

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

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

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

[ редактировать ]

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

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

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

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

Предложение

[ редактировать ]

Тесты на простоту эллиптических кривых основаны на критериях, аналогичных критерию Поклингтона, на котором основан этот тест: [6] [7] где группа заменяется на E правильно выбранная эллиптическая кривая. Теперь мы сформулируем предложение, на котором будет основан наш тест, который аналогичен критерию Поклингтона и приводит к форме Гольдвассера-Килиана-Аткина теста простоты эллиптической кривой.

Пусть N — целое положительное число, а E — множество, определяемое уравнением Рассмотрим E над используйте обычный закон сложения для E и напишите 0 для нейтрального элемента E. в

Пусть m — целое число. Если существует простое число q, которое делит m и больше, чем и существует точка P на E такая, что

(1) мП = 0

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

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

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

[ редактировать ]

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

и таким образом и существует целое число u со свойством, что

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

Теперь, если и тогда наше предыдущее предложение говорит нам, что N простое число. Однако есть одна возможная проблема — простота q . Это проверяется по тому же алгоритму. Итак, мы описали рекурсивный алгоритм , в котором простота N зависит от простоты q и даже меньших «вероятных простых чисел» до тех пор, пока не будет достигнут некоторый порог, при котором q считается достаточно малым, чтобы применить нерекурсивный детерминированный алгоритм. [9] [10]

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

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

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

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

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

Выберите дискриминанты D в последовательности возрастания h ( D ). Для каждого D проверьте, есть ли и можно ли 4 N записать как:

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

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

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

[ редактировать ]

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

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

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

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

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

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

или [1] [10] [12]

Обсуждение

[ редактировать ]

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

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

[ редактировать ]

Построим пример, доказывающий, что является простым с использованием теста ECPP Аткина-Морена. Сначала пройдитесь по набору из 13 возможных дискриминантов, проверяя, является ли символ Лежандра , а если 4 N можно записать как .

Для нашего примера выбран. Это потому, что а также, используя алгоритм Корнаккиа , мы знаем, что и, таким образом, a = 25 и b = 1.

Следующий шаг – вычисление m . Это легко сделать, как что дает Далее нам нужно найти вероятный простой делитель числа m , который обозначается как q . Оно должно удовлетворять условию, что

В данном случае m = 143 = 11×13. Поэтому, к сожалению, мы не можем выбрать 11 или 13 в качестве нашего q , поскольку оно не удовлетворяет необходимому неравенству. Нас спасает, однако, предложение, аналогичное тому, которое мы высказали перед алгоритмом Гольдвассера–Килиана, которое взято из статьи Морена. [13] В нем говорится, что, учитывая наше m , мы ищем s, которое делит m , , но не обязательно является простым, и проверьте, для каждого ли который делит s

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

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

Итак, в нашем случае мы выбираем s = m = 143. Таким образом, наши возможные это 11 и 13. Во-первых, ясно, что , и поэтому нам нужно только проверить значения

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

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

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

,

где k такое же, как описано ранее, а c неквадрат в . Итак, мы можем начать с

что дает

Теперь, используя точку P = (6,6) на E, можно убедиться, что

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

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

[ редактировать ]

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

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

Гипотеза

[ редактировать ]

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

для достаточно большого x .

Если принять эту гипотезу, то алгоритм Гольдвассера-Килиана завершается за ожидаемое полиномиальное время для каждого входного сигнала. Кроме того, если наш N имеет длину k , алгоритм создает сертификат размера что можно проверить в . [14]

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

Гипотеза 2

[ редактировать ]

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

больше, чем

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

[13]

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

для некоторых [3]

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

[ редактировать ]

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

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

[ редактировать ]

Мы возьмем E в качестве нашей эллиптической кривой, где E имеет вид для где является простым, и с странный.

Теорема 1. [7]
Теорема 2. или ли m в зависимости от того, является квадратичным вычетом по модулю p .
Теорема 3. Пусть Q = ( x , y ) на E таково, что x — квадратичный невычет по модулю p . Тогда порядок Q делится на в циклической группе

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

Теорема 4. Выберите и предположим
Тогда p является простым тогда и только тогда, когда существует Q = ( x , y ) на E такой, что для i = 1, 2, ..., k - 1 и где представляет собой последовательность с начальным значением .

Алгоритм

[ редактировать ]

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

(1) Выберите такой, что и найти такой, что .

Брать и .

Затем включен .

Рассчитать . Если затем является составным, иначе переходим к (2).

(2) Набор как последовательность с начальным значением . Рассчитать для .

Если для , где затем является составным. В противном случае перейдите к (3).

(3) Если затем является простым. В противном случае, является составным. На этом тест завершен.

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

[ редактировать ]

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

Таким образом, если N простое число, порядок Q' делится на , по теореме 3,и, следовательно, порядок Q' равен д | н .

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

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

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

  1. ^ Jump up to: Перейти обратно: а б с Анри Коэн, Герхард Фрей, изд. (2006). Справочник по криптографии эллиптических и гиперэллиптических кривых . Бока-Ратон: Чепмен и Холл/CRC.
  2. ^ Топ, Яап, Доказательство простоты эллиптической кривой , http://www.math.rug.nl/~top/atkin.pdf
  3. ^ Jump up to: Перейти обратно: а б с Аткин, AOL; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» . Математика вычислений . 61 (203): 29–68. дои : 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. ^ Jump up to: Перейти обратно: а б Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. стр. 187–188. ISBN  978-1-4704-1048-3 .
  7. ^ Jump up to: Перейти обратно: а б Вашингтон, Лоуренс К. , Эллиптические кривые: теория чисел и криптография , Chapman & Hall/CRC, 2003.
  8. ^ Jump up to: Перейти обратно: а б Коблиц, Нил, Введение в теорию чисел и криптографию , 2-е изд., Springer, 1994 г.
  9. ^ «Королевский университет Канады» (PDF) . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 22 января 2010 г.
  10. ^ Jump up to: Перейти обратно: а б Блейк, И.; Серусси, Г.; Смарт, Н. (1999). Эллиптические кривые в криптографии . дои : 10.1017/CBO9781107360211 . ISBN  9780521653749 .
  11. ^ Ленстра, Хендрик В., Эффективные алгоритмы в теории чисел , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf.
  12. ^ ECPP возвращается algo.inria.fr
  13. ^ Jump up to: Перейти обратно: а б Морейн, Ф. (1988). «Реализация алгоритма проверки простоты Аткина-Гольдвассера-Килиана» (PDF) . S2CID   118191463 .
  14. ^ Гольдвассер, Шафи, Килиан, Джо, Почти все простые числа могут быть быстро сертифицированы , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf. Архивировано 18 июля 2011 г. на Wayback. Машина
  15. ^ «Самое большое известное простое число по годам: краткая история» .
  16. ^ Jump up to: Перейти обратно: а б Цумура, Ю (2009). «Тесты на простоту с использованием эллиптических кривых». arXiv : 0912.5279v1 [ math.NT ].
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ef2b1fde646d2100da881b7d0754cf40__1721586660
URL1:https://arc.ask3.ru/arc/aa/ef/40/ef2b1fde646d2100da881b7d0754cf40.html
Заголовок, (Title) документа по адресу, URL1:
Elliptic curve primality - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)