Оглавление
- 1 Первичность эллиптической кривой
- 1.1 Методы проверки простоты эллиптической кривой
- 1.2 История и развитие
- 1.3 Алгоритм ECPP
- 1.4 Предложение и доказательство
- 1.5 Алгоритм Голдвассера–Килиана
- 1.6 Проблемы с алгоритмом
- 1.7 Тест на первичность эллиптической кривой Аткина–Морена (ECPP)
- 1.8 Тест на простоту с помощью эллиптических кривых
- 1.9 Метод комплексного умножения
- 1.10 Пример ECPP Аткина–Морена
- 1.11 Сложность и время выполнения
- 1.12 Простые числа специальной формы
- 1.13 Обоснование алгоритма
- 1.14 Доказательство простоты 4.2: эллиптические кривые и тест ECPP
- 1.15 Домашняя страница ECPP
- 1.16 Primo
- 1.17 PARI/GP
- 1.18 GMP-ECPP
- 1.19 LiDIA
- 1.20 CM
- 1.21 Полный текст статьи:
- 2 Простота эллиптической кривой
Первичность эллиптической кривой
-
Методы проверки простоты эллиптической кривой
- Методы проверки простоты эллиптической кривой (ECPP) являются быстрыми и широко используемыми.
- Идея предложена Шафи Голдвассером и Джо Килианом в 1986 году.
- Алгоритм был улучшен Аткином и Франсуа Мореном в 1993 году.
-
История и развитие
- Концепция использования эллиптических кривых при факторизации разработана Н. W. Lenstra в 1985 году.
- Современные тесты на простоту основаны на эллиптических кривых.
- ECPP является самым быстрым известным алгоритмом для проверки простоты общих чисел.
-
Алгоритм ECPP
- ECPP работает аналогично другим тестам на первичность, но использует эллиптические кривые.
- Алгоритм генерирует сертификат первичности Аткина–Голдвассера–Килиана–Морена.
- Сертификат может быть быстро проверен, что позволяет провести проверку за короткое время.
-
Предложение и доказательство
- Тесты на первичность эллиптической кривой основаны на критерии, аналогичном критерию Поклингтона.
- Доказательство основано на теореме Хассе об эллиптических кривых.
-
Алгоритм Голдвассера–Килиана
- Алгоритм выбирает случайные числа a, x, y и определяет точку P на эллиптической кривой E.
- Подсчитывает количество точек на E с помощью алгоритма Шуфа.
- Если mP = 0 и kP ≠ 0, N считается простым числом.
-
Проблемы с алгоритмом
- Алгоритм Шуфа медленный и громоздкий.
- Трудно найти кривую E с подходящим количеством точек.
-
Тест на первичность эллиптической кривой Аткина–Морена (ECPP)
- ECPP использует комплексное умножение для построения кривой E.
- Количество точек на E легко вычислить.
- N делится на два элемента, если (D/N) = 1.
-
Тест на простоту с помощью эллиптических кривых
- Тест основан на выборе дискриминантов D и проверке их на простоту.
- Для каждого D проверяется, является ли (D/N) = 1 и можно ли записать 4N в виде a^2 + |D|b^2.
- Если m имеет простой множитель q, используется метод комплексного умножения для построения кривой E и точки P.
-
Метод комплексного умножения
- Для создания эллиптической кривой используется дискриминант D.
- Вычисляются эллиптические j-инварианты классов h(D).
- Создается монический многочлен H(X), корни которого соответствуют значениям h(D).
- Если N простое, H(X) разбивает по модулю N на произведение h(D) линейных множителей.
-
Пример ECPP Аткина–Морена
- Пример доказательства простоты числа N = 167 с использованием теста ECPP Аткина–Морена.
- Выбирается дискриминант D = -43, вычисляется m = 143.
- Проверяется, что m имеет простой множитель q = 11 × 13.
- Построение кривой E и точки P с помощью комплексного умножения.
- Проверка, что 143P = P∞, что подтверждает простоту N.
-
Сложность и время выполнения
- Алгоритм Голдвассера–Килиана завершается за полиномиальное время.
- Алгоритм Аткина–Морена создает сертификат размера O(k^2) и проверяет его за O(k^4).
-
Простые числа специальной формы
- Числа Мерсенна можно доказать простыми с помощью эллиптических кривых.
- Для чисел вида N = 2^kn-1 используется эллиптическая кривая E(FN).
- Алгоритм основан на теоремах 3 и 4, проверяет порядок точки Q на E.
-
Обоснование алгоритма
- Если N простое, Q’ имеет порядок, кратный 2^k, согласно теореме 3.
- Если (1) заключает, что N составное, то оно действительно составное.
- Если (2) или (3) заключают, что N составное, то оно действительно составное.
- Если алгоритм приходит к выводу, что N простое, то это означает, что S1 удовлетворяет условию теоремы 4.
-
Доказательство простоты 4.2: эллиптические кривые и тест ECPP
- Крис Колдуэлл, “Доказательство простоты 4.2” на Prime Pages
- Включает эллиптические кривые и тест ECPP
-
Домашняя страница ECPP
- Франсуа Морен, “Домашняя страница ECPP”
- Включает старое программное обеспечение ECPP для некоторых архитектур
-
Primo
- Марсель Мартин, “Primo”
- Двоичный код для 64-разрядной версии Linux
-
PARI/GP
- Система компьютерной алгебры с функциями создания сертификатов первичности Аткина-Морена и Primo
-
GMP-ECPP
- Бесплатная реализация ECPP
-
LiDIA
- Бесплатная библиотека C++ для Linux с поддержкой ECPP
-
CM
- Еще одна бесплатная библиотека, содержащая реализацию ECPP