Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

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


 Это универсальный алгоритм, что означает, что не зависит чисел особойформы. В настоящее время ECPP на практике является самым быстрым изизвестных алгоритмов для проверки простоты чисел, но время выполнения вхудшем случае (максимальное время, за которое задача может бытьвыполнена на конкретной аппаратной платформе) не известно. ЕСРР работаетза время:
O((logn)5+ε)
 для некоторых ε>0 . Этот показатель из эвристическихсоображений может быть уменьшен до 4+ε для некоторыхслучаев. ЕСРР работает так же, как большинство других тестов простоты,находит группу и показывает, что её размер таков, что p простое. ДляЕСРР группой является эллиптическая кривая над конечным наборомквадратичных форм, таких, что p1 тривиально относительно факторагруппы*(?).
 ЕСРР генерирует сертификат простоты Аткина-Гольдвасера-Килиана-Морейна спомощью рекурсии, а затем пытается проверить сертификат. Шагом, которыйзанимает больше всего времени у процессора, является генерациясертификата, потому что необходимо выполнить факторизацию над полемкласса. Сертификат может быть подтвержден быстро, из-за чего задержка наэту операцию займет очень мало времени.
 По состоянию на сентябрь 2015 года, наибольшим простым числом, котороебыло найдено методом ЕСРР, является 30950-знаковое величина, котораяобозначается в терминах последовательности Люка как:
V(148091).
 Его сертификация при помощи Primo (программного обеспечения МарселяМартина) заняла 9 месяцев у Пола Андервуда.

Утверждение


 Пусть N целое положительное число, а Е множество, котороеопределяется по формуле y2=x3+ax+b(modN). РассмотримE над Z/NZ, используя обычный закон сложенияна Е, и запишем 0 как нейтральный элемент на Е.
 Пусть m целое. Если есть простое число q, которое являетсяделителем m, и большее, чем (N1/4+1)2 и существует точкаP на E такая, что
 (1) mP = 0
 2) (m/q)P определено и не равно 0
 Тогда N — простое число.

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


 Если N составное, то существует простое число pN,которое делит N. Определим Ep как эллиптическую кривую,определенную тем же уравнением, что и Е, но определим по модулюр, а не по модулю N. Определим mp как порядок группыEp. По теореме Хассе об эллиптических кривых мы знаем
mpp+1+2p=(p+1)2(N1/4+1)2<q
 и, таким образом, НОД(q,mp)=1, и существует целое число u сосвойством
uq1(modmp)
 Пусть Pp есть точка P оцененная по модулю р. Такимобразом, на Ep мы имеем
(m/q)Pp=uq(m/q)Pp=umPp=0
 используя (1), т.к. mPp высчитано с использованием тех же методов,что и mP, за исключением модуля р, а не модуля NpN).
 Это противоречит (2), потому что, если (m/q)Р определен ине равно 0 (mod N), то тот же метод рассчитывается по модулюр, а не по модулю N даст
(m/q)Pp0

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


 Из этого утверждения может быть построен алгоритм для доказательстватого, что целое число N является простым. Это делается следующимобразом:
 Выберем три случайных целых числа а, х, у и зададим
by2x3ax(modN)
 Пусть теперь P = (x,y) точка, принадлежащаяЕ, где Е определено как y2=x3+ax+b. Далее намнужен алгоритм для подсчета количества точек на Е. Применимо кЕ этот алгоритм (Коблиц и другие ученые предлагают алгоритм Шуфa[алгоритм подсчета точек эллиптической кривой над конечным полем])даст число m, выражающее количество точек на кривой Е надFN, при условии, что N простое.Затем, у нас есть критерий для принятия решения о том, является ли нашакривая Е приемлемой.
 Если мы можем написать m в виде m=kq, где k2 небольшойцелое число, а q вероятно простое (например, оно прошло некоторыепредыдущие вероятностные тесты простоты), то мы не отбрасываем Е.Если же невозможно записать m в этой форме, то мы отбрасываемнашу кривую и случайным образом выбираем другую тройку (а, х, у),чтобы начать снова.
 Предположим, что мы нашли кривую, которая проходит под критерий, тогдаприступим к вычислению mP и kP. Если на любом этаперасчетов мы сталкиваемся с неопределенным выражением (из расчетаР или в алгоритме подсчета количества точек), это дает намнетривиальный фактор N.
 Если mP0, то становится ясно, что N не является простым,потому что, если бы N было простое, то Е имела бы порядокm, и любой элемент E станет 0 при умножении на m.Если Kp = 0, то мы попали в тупик и должны начать снова с другойтройкой.
 Теперь, если mP=0 и kP0, тогда наша предыдущее утверждениеговорит нам, что N является простым. Тем не менее, есть однавозможная проблема, которая заключается в простоте q. Это должнобыть проверено, используя тот же алгоритм. Таким образом, мы описалипошаговую процедуру, где простота N может быть доказана с помощьюпростоты q и небольших вероятно простых чисел, повторяющуюся покамы не достигли определенных простых чисел и не закончили.

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


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

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


 В статье 1993 года, Аткин и Морейн описали алгоритм ЕСРР, которыйизбегает трудностей, возникающих при использовании алгоритма, которыйопирается на громоздкое вычисление количества точек (алгоритм Шуфа).Алгоритм по-прежнему опирается на утверждения, описанные выше, но вместогенерирования эллиптических кривых случайным образом и последующегопоиска правильного m, их идея заключается в построении кривойE, на которой легко вычислить число точек. Комплексное умножениеявляется ключевым в строительстве кривой.
 Теперь, взяв определенное N, простота которого должна бытьдоказана, мы должны найти подходящие m и q, так же, как валгоритме Гольдвасер-Килиана, которые будут удовлетворять теореме идоказывать простоту N. (конечно, точка P и сама кривая,Е, также должны быть найдены)
 ЕСРР использует комплексное умножение для построения кривой E,такой способ позволяет легко вычислить m (количество точек наЕ). Теперь опишем этот метод:
 Использование комплексного умножения требует отрицательный дискриминант,D, такой, что D может быть записан в виде произведениядвух элементов D=πˉπ, или, что полностью эквивалентно, мыможем написать уравнение:
a2+|D|b2=4N
 Для некоторых a, b. Если мы может описать N в терминахлюбой из этих форм, мы можем создать эллиптическую кривую E наZ/NZ с комплексным умножением (подробно описанониже), и число точек определяется по формуле:
|E(Z/NZ)|=N+1πˉπ=N+1a.
 Для того, чтобы разделить N на два элемента, нам нужно, чтобы(DN)=1 (где (DN)обозначает символ Лежандра). Это является необходимым условием, и мыдостигнем достаточности, если порядок группы h(D) вQ(D) равен 1. Это происходит только для 13 значений D,которые являются элементами \{-3, -4, -7, - 8, -11, -12, -16, -19, -27,-28, -43, -67, -163\}