Алгоритм Шуфа – Элкиса – Аткина

Алгоритм Шуфа -Элкиса-Аткина (SEA) — это алгоритм, используемый для определения порядка или вычисления количества точек на эллиптической кривой над конечным полем . Его основное применение — криптография на эллиптических кривых . Алгоритм является расширением алгоритма Шуфа, разработанным Ноамом Элкисом и АОЛ Аткином, с целью значительного повышения его эффективности (при эвристических предположениях).

Подробности

Расширение Элкиса-Аткина алгоритма Шуфа работает за счет ограничения набора простых чисел. $S=\{l_{1},\ldots ,l_{s}\}$ считаются простыми числами определенного вида. Их стали называть простыми числами Элкиса и простыми числами Аткина соответственно. Премьер $l$ называется простым числом Элкиса, если характеристическое уравнение: $\phi ^{2}-t\phi +q=0$ раскалывается $\mathbb {F} _{l}$ , а простое число Аткина — это простое число, не являющееся простым числом Элкиса. Аткин показал, как объединить информацию, полученную из простых чисел Аткина, с информацией, полученной из простых чисел Элкиса, для создания эффективного алгоритма, который стал известен как алгоритм Шуфа – Элкиса – Аткина. Первая проблема, которую необходимо решить, — определить, является ли данное простое число Элкисом или Аткином. Для этого воспользуемся модульными полиномами. $\Phi _{l}(X,Y)$ которые параметризуют пары $l$ - изогенные эллиптические кривые в терминах их j-инвариантов (на практике могут использоваться и альтернативные модульные полиномы, но с той же целью).

Если конкретизированный полином $\Phi _{l}(X,j(E))$ имеет корень $j(E')$ в $\mathbb {F} _{q}$ затем $l$ — простое число Элкиса, и мы можем вычислить полином $f_{l}(X)$ корни которого соответствуют точкам ядра $l$ -изогения от $E$ к $E'$ . Полином $f_{l}$ является делителем соответствующего полинома деления, используемого в алгоритме Шуфа, и имеет значительно меньшую степень, $O(l)$ против $O(l^{2})$ . Для простых чисел Элкиса это позволяет вычислить количество точек на $E$ модуль $l$ более эффективно, чем в алгоритме Шуфа. В случае простого числа Аткина мы можем получить некоторую информацию из шаблона факторизации $\Phi _{l}(X,j(E))$ в $\mathbb {F} _{l}[X]$ , что ограничивает возможности количества точек по модулю $l$ , но асимптотическая сложность алгоритма полностью зависит от простых чисел Элкиса. При условии, что существует достаточно много маленьких простых чисел Элкиса (в среднем мы ожидаем, что половина простых чисел $l$ быть простыми числами Элкиса), это приводит к сокращению времени работы. Полученный алгоритм является вероятностным ( типа Лас-Вегаса ), и его ожидаемое время работы эвристически равно ${\tilde {O}}(\log ^{4}q)$ , что делает его на практике более эффективным, чем алгоритм Шуфа. Здесь ${\tilde {O}}$ нотация — это вариант нотации большого О , который подавляет логарифмические термины в основном термине выражения.