Алгоритм Шуфа — Елкіса — Аткіна

Алгори́тм Шу́фа — Е́лкіса — А́ткіна» (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$ швидше, ніж алгоритм Шуфа. У випадку, коли $l$ є простим число Аткіна, є можливість отримати деяку інформацію із розкладу $\Phi _{l}(X,j(E))$ в $\mathbb {F} _{l}[X]$, яка обмежує множину варіантів кількості точок по модулю $l$, однак асимптотична складність алгоритму повністю залежить від простих чисел Елкіса. При умові, що є достатньо багато малих простих чисел Елкіса (в середньому, очікується, що половина простих чисел $l$ буде простими Елкіса), це призводить до скорочення часу виконання. Отриманий алгоритм є імовірнісним (типу Лас-Вегаса), і очікуваний час його роботи, евристично, дорівнює ${\tilde {O}}(\log ^{4}q)$, що робить його більш ефективнішим на практиці, ніж алгоритм Шуфа.

Реалізації

Реалізація алгоритму Шуфа-Елкіса-Аткіна є в системі комп'ютерної алгебри PARI/GP.

Джерела

• Schoof: Counting points on elliptic curves over finite fields [Архівовано 16 грудня 2011 у Wayback Machine.]
• Weisstein, Eric W. Schoof-Elkies-Atkin Algorithm(англ.) на сайті Wolfram MathWorld.
• Remarks on the Schoof-Elkies-Atkin algorithm [Архівовано 1 грудня 2008 у Wayback Machine.]
• The Schoof-Elkies-Atkin Algorithm in Characteristic 2 [Архівовано 18 березня 2006 у Wayback Machine.]