Простота эллиптической кривой
В математике эллиптических кривых методы проверки простоты или доказательство простоты эллиптических кривых (ECPP) являются одними из самых быстрых и широко используемых методов доказательства простоты. [1] Эту идею выдвинули Шафи Голдвассер и Джо Килиан в 1986 году и в том же году превратили в алгоритм AOL Atkin . Впоследствии алгоритм был изменен и улучшен несколькими сотрудниками, в частности Аткином и Франсуа Мореном в 1993 году. [2] Идея использования эллиптических кривых при факторизации была разработана Х.В. Ленстрой в 1985 году, и последствия ее использования при проверке (и доказательстве) простоты последовали быстро.
Тестирование на простоту — это область, существующая со времен Ферма , во времена которого большинство алгоритмов были основаны на факторинге, который становится громоздким при больших входных данных. [ сломанный якорь ] ; современные алгоритмы решают проблемы определения того, является ли число простым и каковы его делители по отдельности. Практическое значение это приобрело с появлением современной криптографии. Хотя многие текущие тесты дают вероятностный результат ( N либо составное, либо, вероятно, простое число, например, с помощью теста простоты Бэйли-ПСВ или теста Миллера-Рабина ), тест эллиптической кривой доказывает простоту (или составность) с быстрым проверяемый сертификат. [3]
Ранее известные методы доказательства простых чисел, такие как критерий простоты Поклингтона, требовали хотя бы частичной факторизации чисел. чтобы доказать это является простым. В результате эти методы требовали некоторой удачи и, как правило, на практике работали медленно.
Доказательство простоты эллиптической кривой
[ редактировать ]Это алгоритм общего назначения , то есть он не зависит от того, имеет ли число специальную форму. ECPP в настоящее время на практике является самым быстрым известным алгоритмом проверки простоты общих чисел, но время выполнения в худшем случае неизвестно. ECPP эвристически работает во времени:
для некоторых . [4] Этот показатель можно уменьшить до для некоторых версий эвристическими аргументами. ECPP работает так же, как и большинство других тестов на простоту : находит группу и показывает, что ее размер таков, что является простым. Для ECPP группа представляет собой эллиптическую кривую над конечным набором квадратичных форм такую, что факторизовать группу тривиально.
ECPP генерирует Аткина - Гольдвассера -Килиана-Морена сертификат простоты путем рекурсии , а затемпытается проверить сертификат. Шаг, который занимает больше всего процессорного времени, — это генерация сертификата, поскольку факторизацию по полю класса необходимо выполнить . Сертификат можно быстро проверить, что позволяет проверке работоспособности занять очень мало времени.
По состоянию на май 2023 г. [update], наибольшее простое число, доказанное методом 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 . Мы имеем мощность этих кривых как
Обсуждение
[ редактировать ]Как и в случае с тестом Гольдвассера-Киллиана, этот метод приводит к процедуре нисходящего пробега. Опять же, виновником является 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 за ожидаемое время
Для алгоритма Аткина-Морена заявленное время работы составляет
- для некоторых [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]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Анри Коэн, Герхард Фрей, изд. (2006). Справочник по криптографии эллиптических и гиперэллиптических кривых . Бока-Ратон: Чепмен и Холл/CRC.
- ^ Топ, Яап, Доказательство простоты эллиптической кривой , http://www.math.rug.nl/~top/atkin.pdf
- ^ Jump up to: Перейти обратно: а б с Аткин, AOL; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» . Математика вычислений . 61 (203): 29–68. дои : 10.2307/2152935 . JSTOR 2152935 .
- ^ Ленстра, АК; Ленстра, HW (1990). «Алгоритмы в теории чисел». Алгоритмы и сложность (PDF) . стр. 673–715. дои : 10.1016/B978-0-444-88071-0.50017-5 . ISBN 9780444880710 .
- ^ Колдуэлл, Крис. Двадцатка лучших: доказательство простоты эллиптической кривой с Prime Pages .
- ^ Jump up to: Перейти обратно: а б Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. стр. 187–188. ISBN 978-1-4704-1048-3 .
- ^ Jump up to: Перейти обратно: а б Вашингтон, Лоуренс К. , Эллиптические кривые: теория чисел и криптография , Chapman & Hall/CRC, 2003.
- ^ Jump up to: Перейти обратно: а б Коблиц, Нил, Введение в теорию чисел и криптографию , 2-е изд., Springer, 1994 г.
- ^ «Королевский университет Канады» (PDF) . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 22 января 2010 г.
- ^ Jump up to: Перейти обратно: а б Блейк, И.; Серусси, Г.; Смарт, Н. (1999). Эллиптические кривые в криптографии . дои : 10.1017/CBO9781107360211 . ISBN 9780521653749 .
- ^ Ленстра, Хендрик В., Эффективные алгоритмы в теории чисел , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf.
- ^ ECPP возвращается algo.inria.fr
- ^ Jump up to: Перейти обратно: а б Морейн, Ф. (1988). «Реализация алгоритма проверки простоты Аткина-Гольдвассера-Килиана» (PDF) . S2CID 118191463 .
- ^ Гольдвассер, Шафи, Килиан, Джо, Почти все простые числа могут быть быстро сертифицированы , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf. Архивировано 18 июля 2011 г. на Wayback. Машина
- ^ «Самое большое известное простое число по годам: краткая история» .
- ^ Jump up to: Перейти обратно: а б Цумура, Ю (2009). «Тесты на простоту с использованием эллиптических кривых». arXiv : 0912.5279v1 [ math.NT ].
Внешние ссылки
[ редактировать ]- Эллиптические кривые и доказательство простоты Аткина . и Морена
- Вайсштейн, Эрик В. «Доказательство простоты эллиптической кривой» . Математический мир .
- Крис Колдуэлл, «Доказательство простоты 4.2: эллиптические кривые и тест ECPP» на Prime Pages .
- Франсуа Морен, «Домашняя страница ECPP» (включает старое программное обеспечение ECPP для некоторых архитектур).
- Марсель Мартин, «Primo» (двоичный файл для 64-разрядной версии Linux)
- PARI/GP , система компьютерной алгебры с функциями для создания сертификатов простоты Аткина-Морена и Примо.
- GMP-ECPP , бесплатная реализация ECPP
- LiDIA , бесплатная библиотека C++ для Linux с поддержкой ECPP.
- CM , еще одна бесплатная библиотека, содержащая реализацию ECPP.