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

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

Деталі

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

Реалізації

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

Джерела

• 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.]