Тест простоты с использованием эллиптических кривых

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

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

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

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

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

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

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

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

По состоянию на сентябрь 2015 года, наибольшим простым числом^[6], которое было найдено методом ЕСРР, является 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}$ ^[7]

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

Из этого утверждения может быть построен алгоритм для доказательства того, что целое число 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 и небольших вероятно простых чисел, повторяющуюся пока мы не достигли определенных простых чисел и не закончили.^[8][9]

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

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

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

В статье 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, http://www.math.rug.nl/~top/atkin.pdf Архивная копия от 25 января 2014 на Wayback Machine
3. Frank Li. An Overview of Elliptic Curve Primality Proving  (неопр.) (15 декабря 2011). Дата обращения: 17 ноября 2015. Архивировано 5 июля 2017 года.
4. Washington, Lawrence C., Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003
5. Lenstra, Jr., A. K.; Lenstra, Jr., H. W. Algorithms in number theory (англ.) // Theoretical Computer Science^[англ.]. — Amsterdam and New York: The MIT Press, 1990. — Vol. A. — P. 673—715.
6. Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof Архивная копия от 10 декабря 2008 на Wayback Machine from the Prime Pages.
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, https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Архивная копия от 26 июля 2007 на Wayback Machine

Литература

• Elliptic Curves and Primality Proving by Atkin and Morain.
• Weisstein, Eric W. Elliptic Curve Primality Proving (англ.) на сайте Wolfram MathWorld.
• Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" at the Prime Pages.
• François Morain, "The ECPP home page" (includes old ECPP software for some architectures).
• Marcel Martin, "Primo" (binary for Linux 64-bit)
• GMP-ECPP, a free ECPP implementation