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

Алгори́тм Шу́фа — Е́лкіса — А́ткіна» (SEA) — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Є розширенням алгоритму Шуфа, яке запропонували Ноам Елкіс^[en] та А. О. Л. Аткін^[en], має кращу ефективність ніж оригінал (за евристичним припущенням).

Деталі

Розширення Елкіса-Аткіна алгоритму Шуфа полягає в обмежені множини простих чисел $S=\{l_{1},\ldots ,l_{s}\}$ до простих чисел певного виду. Просте число $l$ називається простим числом Елкіса, якщо характеристичне рівняння $\phi ^{2}-t\phi +q=0$ розкладається над $\mathbb {F} _{l}$ , а прості числа Аткіна – це прості числа, які не є простими Елкіса. Аткін показав як комбінувати інформацію, отриману з простих чисел Аткіна, з інформацією, отриманою з простих чисел Елкіса, що і привело до алгоритму Шуфа-Елкіса-Аткіна. Перша задача, яку потрібно вирішити, – чи є задане просте число простим Аткіна, чи простим Елкіса. Для цього використовуються модулярні поліноми^[en] $\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)$ , що робить його більш ефективнішим на практиці, ніж алгоритм Шуфа.