Алгоритм Шуфа

Алгоритм Шуфа — это детерминированный полиномиальный алгоритм подсчёта количества точек на эллиптической кривой над конечным полем, разработанный нидерландским математиком Рене Шуфом (René Schoof) в 1985 году. Алгоритм решает задачу нахождения порядка (числа точек) группы эллиптической кривой \(E\) над полем \(\mathbb{F}_q\) (где \(q = p^n\), \(p\) — простое число) за время \(O(\log^6 q)\) или \(O(\log^8 q)\) в зависимости от реализации, что является полиномиальным относительно размера входных данных (логарифма \(q\)). До появления алгоритма Шуфа не существовало эффективных методов для вычисления порядка эллиптической кривой над большими полями, что ограничивало применение кривых в криптографии. Алгоритм Шуфа стал основой для современных методов, таких как алгоритм SEA (Schoof–Elkies–Atkin), и широко используется в криптографии на эллиптических кривых (ECC) и теории чисел.

История

Предпосылки

Эллиптические кривые над конечными полями изучались с середины XX века, но их практическое применение в криптографии началось в 1980-х годах после предложения Виктора Миллера (1985) и Нила Коблица (1987) использовать их для построения криптосистем с открытым ключом. Для безопасности таких криптосистем необходимо знать порядок группы кривой, чтобы избежать уязвимостей, связанных с малыми подгруппами или атаками на основе дискретного логарифма. До 1985 года порядок кривой вычисляли либо перебором (для малых полей), либо с помощью теоремы Хассе, которая даёт оценку \(| \#E(\mathbb{F}_q) - (q+1) | \leq 2\sqrt{q}\), но не точное значение. Для полей с большим \(q\) (например, \(q \approx 2^{256}\)) перебор невозможен.

Публикация и признание

В 1985 году Рене Шуф опубликовал статью «Elliptic Curves over Finite Fields and the Computation of Square Roots mod p» в журнале Mathematics of Computation, где впервые описал алгоритм, работающий за полиномиальное время. Алгоритм использовал модулярные символы и теорию кручения на эллиптических кривых. Позднее, в 1990-х годах, Ноам Элкис и Артур Аткин предложили улучшения (алгоритм SEA), которые ускорили вычисления за счёт использования изогений и комплексного умножения, но базовая идея осталась неизменной.

Основные понятия

Эллиптическая кривая над конечным полем

Эллиптическая кривая \(E\) над полем \(\mathbb{F}_q\) (где \(q = p^n\), \(p\) — простое число, \(p \neq 2,3\) для упрощения) задаётся уравнением Вейерштрасса: \[ y^2 = x^3 + ax + b, \quad a, b \in \mathbb{F}_q, \quad 4a^3 + 27b^2 \neq 0. \] Множество точек кривой \(E(\mathbb{F}_q)\) вместе с бесконечно удалённой точкой \(O\) образует абелеву группу. Порядок этой группы \(\#E(\mathbb{F}_q)\) — число точек, которое нужно вычислить.

Теорема Хассе

Теорема Хассе (1933) утверждает, что \[ |\#E(\mathbb{F}_q) - (q+1)| \leq 2\sqrt{q}. \] Таким образом, \(\#E(\mathbb{F}_q) = q + 1 - t\), где \(t\) — след Фробениуса, целое число, удовлетворяющее \(|t| \leq 2\sqrt{q}\). Алгоритм Шуфа находит \(t\) по модулю различных простых чисел \(\ell\), а затем восстанавливает \(t\) с помощью китайской теоремы об остатках.

Эндоморфизм Фробениуса

Эндоморфизм Фробениуса \(\pi: E \to E\) определяется как \(\pi(x, y) = (x^q, y^q)\). Он является эндоморфизмом кривой и удовлетворяет характеристическому уравнению: \[ \pi^2 - t \pi + q = 0, \] где \(t\) — след Фробениуса. Для любой точки \(P \in E(\overline{\mathbb{F}}_q)\) выполняется: \[ \pi^2(P) - t \cdot \pi(P) + q \cdot P = O. \] Алгоритм Шуфа использует это уравнение для вычисления \(t\) по модулю \(\ell\).

Описание алгоритма

Общая схема

1. Выбор простых чисел \(\ell\): Выбирается набор различных простых чисел \(\ell_1, \ell_2, \dots, \ell_k\) таких, что произведение \(L = \prod \ell_i > 4\sqrt{q}\). Это гарантирует, что \(t\) можно однозначно восстановить по его остаткам по модулю \(\ell_i\).
2. Вычисление \(t \mod \ell\): Для каждого \(\ell\) (кроме \(\ell = 2\) и \(\ell = p\)) вычисляется остаток \(t_\ell\) с помощью анализа точек порядка \(\ell\) (кручения).
3. Восстановление \(t\): С помощью китайской теоремы об остатках находится \(t\) как целое число в интервале \([-2\sqrt{q}, 2\sqrt{q}]\).
4. Вычисление порядка: \(\#E(\mathbb{F}_q) = q + 1 - t\).

Вычисление \(t \mod \ell\) для \(\ell \neq 2, p\)

Для простого \(\ell\) рассматривается множество точек \(\ell\)-кручения \(E[\ell] = \{P \in E(\overline{\mathbb{F}}_q) : \ell P = O\}\). Это двумерное векторное пространство над \(\mathbb{F}_\ell\). Эндоморфизм Фробениуса \(\pi\) действует на \(E[\ell]\) как линейное преобразование, и его характеристический многочлен — это \(x^2 - t x + q \mod \ell\). Для вычисления \(t \mod \ell\) алгоритм проверяет, при каких значениях \(\tau \in \{0, 1, \dots, \ell-1\}\) выполняется: \[ \pi^2(P) - \tau \cdot \pi(P) + q \cdot P = O \] для всех \(P \in E[\ell]\). Это эквивалентно проверке, что \(\tau\) является следом Фробениуса по модулю \(\ell\). Для этого используются так называемые «модулярные многочлены» \(\Phi_\ell(x, y)\), которые задают соотношение между \(j\)-инвариантами \(\ell\)-изогенных кривых. Вычисление происходит в кольце многочленов \(\mathbb{F}_q[x, y]/(\Phi_\ell(x, j(E)))\), что позволяет работать с точками кручения, не находя их явно.

Особые случаи

• \(\ell = 2\): Для \(\ell = 2\) след \(t \mod 2\) вычисляется по формуле \(t \equiv 1 + \#E(\mathbb{F}_q) \mod 2\), где \(\#E(\mathbb{F}_q) \mod 2\) определяется по наличию точек порядка 2 (то есть корней многочлена \(x^3 + ax + b\)).
• \(\ell = p\): Если \(p\) — характеристика поля, то \(\ell = p\) не рассматривается, так как \(p\)-кручение тривиально (кривая суперсингулярна). Вместо этого используется отдельная проверка на суперсингулярность.

Сложность и улучшения

Временная сложность

Оригинальный алгоритм Шуфа имеет сложность \(O(\log^6 q)\) или \(O(\log^8 q)\) в зависимости от реализации операций с многочленами. Основной вклад в сложность даёт работа с модулярными многочленами \(\Phi_\ell(x, y)\), степень которых по \(x\) равна \(\ell+1\), а по \(y\) — \(\ell+1\). Для каждого \(\ell\) требуется выполнять операции в кольце \(\mathbb{F}_q[x, y]/(\Phi_\ell(x, j(E)))\), что требует \(O(\ell^2 \log q)\) битовых операций. Поскольку \(\ell\) пробегают значения порядка \(O(\log q)\), общая сложность — полиномиальная.

Алгоритм SEA (Schoof–Elkies–Atkin)

В 1990-х годах Ноам Элкис и Артур Аткин предложили улучшения:

• Метод Элкиса: Использует изогении для уменьшения степени модулярных многочленов, что ускоряет вычисления для \(\ell\), при которых \(\ell\) делит \(q-1\) (ординарные кривые).
• Метод Аткина: Использует комплексное умножение для ускорения вычислений для \(\ell\), при которых \(\ell\) делит \(q+1\) (суперсингулярные кривые).

Алгоритм SEA имеет сложность \(O(\log^4 q)\) или \(O(\log^5 q)\) и является стандартным для практических вычислений.

Применение

Криптография на эллиптических кривых (ECC)

Алгоритм Шуфа и его улучшения используются для генерации безопасных эллиптических кривых, используемых в криптосистемах, таких как ECDSA, EdDSA, ECDH и других. Знание порядка кривой необходимо для:

• Проверки, что порядок является большим простым числом (или содержит большой простой множитель), чтобы избежать атак Полига–Хеллмана.
• Выбора кривых с заданными свойствами (например, кривые с комплексным умножением, такие как кривые NIST или Curve25519).

Теория чисел

Алгоритм используется для вычисления числа точек на эллиптических кривых в теоретических исследованиях, например, для проверки гипотезы Берча–Свиннертон-Дайера или изучения распределения следов Фробениуса.

Пример

Рассмотрим эллиптическую кривую \(E: y^2 = x^3 + 2x + 3\) над полем \(\mathbb{F}_{13}\). Порядок кривой можно вычислить вручную: точки: \(O, (0,4), (0,9), (1,5), (1,8), (2,2), (2,11), (3,1), (3,12), (4,3), (4,10), (5,5), (5,8), (6,0), (7,6), (7,7), (8,4), (8,9), (9,2), (9,11), (10,1), (10,12), (11,3), (11,10), (12,0)\) — всего 25 точек. След \(t = q+1 - \#E = 13+1-25 = -11\). Алгоритм Шуфа для такого малого поля неэффективен, но для больших полей (например, \(q \approx 2^{256}\)) он позволяет вычислить порядок за секунды.

Критика и ограничения

• Сложность реализации: Алгоритм требует работы с модулярными многочленами, которые имеют большие коэффициенты и высокую степень, что делает реализацию нетривиальной.
• Ограничение на малые характеристики: Для полей характеристики 2 и 3 существуют отдельные методы, но алгоритм Шуфа в исходной версии требует \(p \neq 2,3\).
• Альтернативные методы: Для некоторых классов кривых (например, суперсингулярных) существуют более быстрые методы, такие как алгоритм Сато (Satoh) для полей малой характеристики.

Интересные факты

• Алгоритм Шуфа был одним из первых примеров использования модулярных многочленов в вычислительной теории чисел.
• Рене Шуф получил за эту работу премию Лектура (Lektr) в 1995 году.
• Алгоритм SEA (Schoof–Elkies–Atkin) является основой для большинства современных библиотек ECC, таких как OpenSSL и libsecp256k1.

Источники

• Schoof, R. (1985). «Elliptic Curves over Finite Fields and the Computation of Square Roots mod p». Mathematics of Computation, 44(170), 483–494.
• Elkies, N. D. (1998). «Elliptic and modular curves over finite fields and related computational issues». Computational Perspectives on Number Theory, 21–76.
• Atkin, A. O. L. (1992). «The number of points on an elliptic curve over a finite field». Proceedings of the 1992 International Congress of Mathematicians.
• Коблиц, Н. (2001). «Курс теории чисел и криптографии». Springer.
• Блейк, И., Серусси, Г., Смарт, Н. (2005). «Advances in Elliptic Curve Cryptography». Cambridge University Press.