Алгоритм Шуфа – Элкиса – Аткина - 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}}(log ^{4}q)}$, что делает его более эффективным на практике, чем алгоритм Шуфа. Здесь ${displaystyle { ilde {O}}}$ обозначение является вариантом нотация большой O который подавляет элементы, являющиеся логарифмическими в основном члене выражения.

Реализации

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

внешняя ссылка

• «Шуф: подсчет точек на эллиптических кривых над конечными полями»
• статья о Mathworld
• «Замечания по алгоритму Шуфа-Элкиса-Аткина»
• "Алгоритм Шуфа-Элкиса-Аткина в характеристике 2"