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

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

Деталі

Розширення Елкіса-Аткіна алгоритму Шуфа полягає в обмежені множини простих чисел $S=\{l_1,\dots ,l_s\}$ до простих чисел певного виду. Просте число $l$ називається простим числом Елкіса, якщо характеристичне рівняння ${\varphi }^2-t\varphi +q=0$ розкладається над ${𝔽}_l$, а прості числа Аткіна – це прості числа, які не є простими Елкіса. Аткін показав як комбінувати інформацію, отриману з простих чисел Аткіна, з інформацією, отриманою з простих чисел Елкіса, що і привело до алгоритму Шуфа-Елкіса-Аткіна. Перша задача, яку потрібно вирішити, – чи є задане просте число простим Аткіна, чи простим Елкіса. Для цього використовуються Шаблон:Не перекладено ${\mathrm{\Phi }}_l(X,Y)$, які параметризують пари $l$-ізогенних еліптичних кривих та залежать від j-інваріантів цих кривих (на практиці також можуть використовуватися інші модулярні поліноми з тією ж метою).

Якщо модулярний поліном ${\mathrm{\Phi }}_l(X,j(E))$ має корінь $j(E^{\prime })$ в ${𝔽}_q$, то $l$ є простим число Елкіса, тоді можна обчислити поліном $f_l(X)$, корені якого відповідають точкам ядра $l$-ізогенії з $E$ в $E^{\prime }$. Поліном $f_l$ є дільником відповідного полінома ділення, що використовується в алгоритмі Шуфа, і він має меншу степінь $O(l)$, а не $O(l^2)$. Для простих чисел Елкіса це дозволяє обчислити кількість точок на $E$ по модулю $l$ швидше, ніж алгоритм Шуфа. У випадку, коли $l$ є простим число Аткіна, є можливість отримати деяку інформацію із розкладу ${\mathrm{\Phi }}_l(X,j(E))$ в ${𝔽}_l[X]$, яка обмежує множину варіантів кількості точок по модулю $l$, однак асимптотична складність алгоритму повністю залежить від простих чисел Елкіса. При умові, що є достатньо багато малих простих чисел Елкіса (в середньому, очікується, що половина простих чисел $l$ буде простими Елкіса), це призводить до скорочення часу виконання. Отриманий алгоритм є імовірнісним (типу Лас-Вегаса), і очікуваний час його роботи, евристично, дорівнює $\tilde{O}({\log }^{4}q)$, що робить його більш ефективнішим на практиці, ніж алгоритм Шуфа.

Реалізації

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

Джерела

• Schoof: Counting points on elliptic curves over finite fields Шаблон:Webarchive
• Шаблон:MathWorld
• Remarks on the Schoof-Elkies-Atkin algorithm Шаблон:Webarchive
• The Schoof-Elkies-Atkin Algorithm in Characteristic 2 Шаблон:Webarchive