Подсчет точек на эллиптических кривых
-
Подсчет точек на эллиптических кривых
- Важен для теории чисел и криптографии
- Использует сложность задачи дискретного логарифмирования
-
Наивный подход
- Проходит по всем элементам поля
- Требует времени выполнения O(q)
-
Маленький шаг, гигантский шаг
- Выбирает элемент P и вычисляет y
- Требует времени выполнения O(4q^4)
-
Алгоритм Шуфа
- Использует теорему Хассе и китайскую теорему об остатке
- Время выполнения O(n^5+o(1))
-
Алгоритм Шуфа–Элкиса–Аткина
- Различает простые числа Элкиса и Аткина
-
Алгоритм SEA
- Алгоритм SEA использует j-инвариант для определения простого числа Элкиса.
- В случае Элкиса, дальнейшие вычисления с модульными многочленами используются для получения правильного множителя многочлена деления.
- Степень влияния этого фактора равна O(ℓ), а ψℓ имеет ученую степень O(ℓ2).
-
Реализация и сложность
- Алгоритм SEA обычно реализуется как вероятностный алгоритм, что делает поиск корней и другие операции более эффективными.
- В вычислительной сложности преобладают затраты на вычисление модульных многочленов Ψℓ(X,Y), которые могут быть вычислены один раз и использованы повторно.
- При эвристическом предположении о большом количестве простых чисел Элкиса, асимптотическое время работы алгоритма SEA равно O(n2M(n2)/logn) = O(n4+o(1)).
- Пространственная сложность алгоритма SEA составляет O(n3logn), но при использовании предварительно вычисленных модульных многочленов увеличивается до O(n4).
-
Связанные алгоритмы и темы
- Алгоритм Шуфа
- Криптография с эллиптической кривой
- Маленький шаг, гигантский шаг
- Криптография с открытым ключом
- Алгоритм Шуфа–Элкиса–Аткина
- Поллард ро
- Кенгуру Полларда
- Доказательство простоты эллиптической кривой
-
Библиография
- Я. Блейк, Дж. Серосси и Н. Smart: Эллиптические кривые в криптографии, издательство Кембриджского университета, 1999.
- A. Enge: Эллиптические кривые и их применение в криптографии: Введение. Издательство Kluwer Academic Publishers, Дордрехт, 1999.
- G. Musiker: Алгоритм Шуфа для подсчета очков на E(Fq). Доступно по адресу http://www.math.umn.edu/~musiker/schoof.pdf
- R. Школа: Подсчет точек на эллиптических кривых над конечными полями. J. Теор. Названия Бордо, 7: 219-254, 1995. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctg.pdf
- L. C. Вашингтон: Эллиптические кривые: теория чисел и криптография. Чапман и Холл/CRC, Нью-Йорк, 2003.