Алгори́тм Шу́фа — Е́лкіса — А́ткіна (SEA) — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій. Є розширенням алгоритму Шуфа, яке запропонували та , має кращу ефективність ніж оригінал (за евристичним припущенням).
Деталі Розширення Елкіса — Аткіна алгоритму Шуфа полягає в обмежені множини простих чисел до простих чисел певного виду. Просте число називається простим числом Елкіса, якщо характеристичне рівняння розкладається над , а прості числа Аткіна – це прості числа, які не є простими Елкіса. Аткін показав як комбінувати інформацію, отриману з простих чисел Аткіна, з інформацією, отриманою з простих чисел Елкіса, що і привело до алгоритму Шуфа — Елкіса — Аткіна. Перша задача, яку потрібно вирішити, – чи є задане просте число простим Аткіна, чи простим Елкіса. Для цього використовуються , які параметризують пари -ізогенних еліптичних кривих та залежать від j-інваріантів цих кривих (на практиці також можуть використовуватися інші модулярні поліноми з тією ж метою).
Якщо модулярний поліном має корінь в то є простим число Елкіса, тоді можна обчислити поліном , корені якого відповідають точкам ядра -ізогенії з в . Поліном є дільником відповідного полінома ділення, що використовується в алгоритмі Шуфа, і він має меншу степінь , а не Для простих чисел Елкіса це дозволяє обчислити кількість точок на по модулю швидше, ніж в алгоритмі Шуфа. У випадку, коли є простим число Аткіна, є можливість отримати деяку інформацію із розкладу в яка обмежує множину варіантів кількості точок по модулю , однак асимптотична складність алгоритму повністю залежить від простих чисел Елкіса. При умові, що є достатньо багато малих простих чисел Елкіса (в середньому, очікується, що половина простих чисел буде простими Елкіса), це призводить до скорочення часу виконання. Отриманий алгоритм є імовірнісним (типу Лас-Вегаса), і очікуваний час його роботи, евристично, дорівнює що робить його більш ефективнішим на практиці, ніж алгоритм Шуфа.
Реалізації Реалізація алгоритму Шуфа-Елкіса-Аткіна є в системі комп'ютерної алгебри .
Джерела Schoof: Counting points on elliptic curves over finite fields
Remarks on the Schoof-Elkies-Atkin algorithm The Schoof-Elkies-Atkin Algorithm in Characteristic 2