Введение

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

Подробности

Расширение Элкиса — Аткина к алгоритму Шуфа работает путем ограничения множества рассматриваемых простых чисел простыми числами определенного типа. Эти простые числа стали называться соответственно простыми числами Элкиса и простыми числами Аткина. Простое число называется числом Элкиса, если его характеристическое уравнение распадается на множители в , а простое число называется числом Аткина, если оно не является числом Элкиса. Аткин показал, как объединить информацию, полученную из простых чисел Аткина, с информацией, полученной из простых чисел Элкиса, чтобы создать эффективный алгоритм, который стал известен как алгоритм Шуфа — Элкиса — Аткина. Первая задача — определить, является ли данное простое число числом Элкиса или Аткина. Для этого мы используем модульные многочлены, которые параметризуют пары изогенных эллиптических кривых в терминах их j-инвариантов (на практике также могут использоваться альтернативные модульные многочлены, но для той же цели). Если у заданного многочлена есть корень в , то это число Элкиса, и мы можем вычислить многочлен, корни которого соответствуют точкам в ядре изогении из в . Этот многочлен является делителем соответствующего многочлена деления, используемого в алгоритме Шуфа, и имеет значительно меньшую степень, а именно, по сравнению с . Для простых чисел Элкиса это позволяет вычислить количество точек на модуле более эффективно, чем в алгоритме Шуфа. В случае простого числа Аткина мы можем получить некоторую информацию из структуры разложения в , которая ограничивает возможные значения количества точек по модулю , но асимптотическая сложность алгоритма полностью зависит от простых чисел Элкиса. При условии, что существует достаточно много малых простых чисел Элкиса (в среднем, ожидается, что половина простых чисел являются числами Элкиса), это приводит к сокращению времени работы. Полученный алгоритм является вероятностным (типа Лас-Вегаса), и его ожидаемое время работы, эвристически, составляет , что делает его более эффективным на практике, чем алгоритм Шуфа. Здесь обозначение является вариантом нотации «большое O», которое подавляет слагаемые, логарифмически зависящие от основного члена выражения.

Реализация

Алгоритм Шуфа — Элкиса — Аткина реализован в компьютерной алгебраической системе PARI/GP в GP-функции ellap.