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

Schoof–Elkies–Atkin algorithm

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

Подробности

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

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