В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving , сокр. ЕСРР ) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993 . Концепция использования факторизации с помощью эллиптических кривых была разработана Хендриком Ленстрой в 1985 году, и в скором времени последовало её использование для проверки и доказательства чисел на простоту.

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

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

Доказательство простоты с помощью эллиптических кривых

Это универсальный алгоритм , что означает, что он не зависит от чисел особой формы. В настоящее время ECPP на практике является самым быстрым из известных алгоритмов для проверки простоты чисел, но время выполнения в худшем случае (максимальное время, за которое задача может быть выполнена на конкретной аппаратной платформе) не известно. ЕСРР работает за время:

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

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

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

По состоянию на сентябрь 2015 года, наибольшим простым числом , которое было найдено методом ЕСРР, является 30950-знаковая величина, которая обозначается в терминах последовательности Люка как:

${\displaystyle V(148091).}$

Его сертификация при помощи Primo (программного обеспечения Марселя Мартина) заняла 9 месяцев у Пола Андервуда.

Утверждение

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

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

(1) mP = 0

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

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

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

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

${\displaystyle m_{p}\leq p+1+2{\sqrt {p}}=({\sqrt {p}}+1)^{2}\leq (N^{1/4}+1)^{2}<q}$

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

${\displaystyle uq\equiv 1{\pmod {m_{p}}}}$

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

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

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

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

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

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

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

Выберем три случайных целых числа а, х, у и зададим

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

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

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

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

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

Теперь, если ${\displaystyle mP=0}$ и ${\displaystyle kP\neq 0}$ , тогда наша предыдущее утверждение говорит нам, что N является простым. Тем не менее, есть одна возможная проблема, которая заключается в простоте q . Это должно быть проверено, используя тот же алгоритм. Таким образом, мы описали пошаговую процедуру, где простота N может быть доказана с помощью простоты q и небольших вероятно простых чисел, повторяющуюся пока мы не достигли определенных простых чисел и не закончили.

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

Аткин и Морейн говорили, что "проблема с алгоритмом Гольдвассер-Килиана заключается в том, что алгоритм Шуфa почти невозможно реализовать". Очень медленно и громоздко рассчитывать все точки на Е , используя алгоритм Шуфа, который является предпочтительным алгоритмом для алгоритма Гольдвассер-Килиана. Тем не менее, оригинальный алгоритм Шуфа недостаточно эффективный, чтобы обеспечить вычисления количества точек в короткий промежуток времени. Эти комментарии должны рассматриваться в историческом контексте, до улучшения Элкисом и Аткином метода Шуфа.

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

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

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

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

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

Примечания

1. Handbook of Elliptic and Hyperelliptic Curve Cryptography (англ.) / Henri Cohen, Gerhard Frey. — Boca Raton: Chapman & Hall/CRC, 2006.
2. Top, Jaap, Elliptic Curve Primality Proving , от 25 января 2014 на Wayback Machine
3. Frank Li. (неопр.) (15 декабря 2011). Дата обращения: 17 ноября 2015. 5 июля 2017 года.
4. , Elliptic Curves: Number Theory and Cryptography , Chapman & Hall/CRC, 2003
5. Lenstra, Jr., A. K.; Lenstra, Jr., H. W. Algorithms in number theory (англ.) // (англ.) ( . — Amsterdam and New York: The MIT Press, 1990. — Vol. A . — P. 673—715 .
6. Caldwell, Chris. от 10 декабря 2008 на Wayback Machine from the .
7. Koblitz, Neal, Introduction to Number Theory and Cryptography , 2nd Ed, Springer, 1994
8. (неопр.) . Дата обращения: 17 ноября 2015. Архивировано из 4 марта 2016 года.
9. Blake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Elliptic Curves in Cryptography , Cambridge University Press, 1999
10. Atkin, A.O.L., Morain, F., Elliptic Curves and Primality Proving , (неопр.) . Дата обращения: 27 января 2010. 18 июля 2011 года.
11. Lenstra, Hendrik W., Efficient Algorithms in Number Theory , от 26 июля 2007 на Wayback Machine

Литература

• by and Morain.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Chris Caldwell, at the .
• François Morain, (includes old ECPP software for some architectures).
• Marcel Martin, (binary for Linux 64-bit)
• , a free ECPP implementation