Метод эллиптических кривых

Метод эллиптических кривых (МЭК) — это алгоритм факторизации целых чисел, основанный на свойствах эллиптических кривых над конечными полями. Относится к классу субэкспоненциальных методов факторизации и является одним из наиболее эффективных способов нахождения нетривиальных делителей больших составных чисел, особенно в диапазоне от 10^20 до 10^40. Метод был предложен американским математиком Хендриком Ленстрой-младшим в 1985 году.

История

Идея использования эллиптических кривых для факторизации чисел возникла как развитие более ранних методов, таких как метод факторизации Полларда (ρ-алгоритм) и метод квадратичного решета. В 1985 году Хендрик Ленстра-младший опубликовал статью «Factoring integers with elliptic curves», в которой впервые описал алгоритм, использующий группу точек эллиптической кривой над кольцом вычетов по модулю факторизуемого числа.

До появления МЭК основным инструментом для факторизации чисел промежуточного размера был метод квадратичного решета, который требовал значительных объёмов памяти. МЭК, напротив, использует небольшой объём оперативной памяти и хорошо распараллеливается, что сделало его привлекательным для распределённых вычислений.

В 1990-е годы метод был значительно усовершенствован: были разработаны способы выбора оптимальных кривых, улучшены процедуры обработки кручения и введены методы ускорения арифметики на эллиптических кривых (например, координаты Монтгомери). В 2000-х годах МЭК стал основой для ряда рекордных факторизаций, в том числе для чисел, имеющих более 80 десятичных знаков.

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

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

Эллиптическая кривая над полем K задаётся уравнением Вейерштрасса:

\[ y^2 = x^3 + ax + b \]

где a и b — элементы поля K, причём дискриминант \( \Delta = -16(4a^3 + 27b^2) \) не равен нулю. Точки на кривой вместе с бесконечно удалённой точкой O образуют абелеву группу. Групповая операция — сложение точек — определяется геометрически (правило хорд и касательных) и алгебраически через координаты.

Кольцо вычетов по модулю n

При факторизации числа n рассматривается эллиптическая кривая над кольцом \( \mathbb{Z}/n\mathbb{Z} \). Если n — составное число, то это кольцо не является полем, и групповая операция может быть не определена для некоторых пар точек. Однако алгоритм использует тот факт, что если при вычислении суммы точек возникает деление на число, не взаимно простое с n, то это позволяет найти делитель n.

Алгоритм

Общая схема

1. Выбирается случайная эллиптическая кривая E над \( \mathbb{Z}/n\mathbb{Z} \) и случайная точка P на ней.
2. Вычисляется точка \( kP \) для некоторого большого целого k, которое является произведением всех простых чисел до некоторой границы B (или их степеней).
3. Если при вычислении возникает ситуация, когда знаменатель координаты не обратим по модулю n (то есть имеет общий делитель с n), то этот делитель и является искомым нетривиальным делителем n.
4. Если делитель не найден, выбирается новая кривая и/или увеличивается граница B.

Выбор параметров

Ключевым параметром является граница гладкости B. Число k выбирается как \( k = \prod_{p \le B} p^{e_p} \), где \( e_p \) — наибольшее целое, такое что \( p^{e_p} \le B \). Типичные значения B для чисел размером 10^30–10^40 лежат в диапазоне 10^6–10^8.

Обработка кручения

Если порядок группы точек эллиптической кривой над \( \mathbb{F}_p \) (где p — простой делитель n) является B-гладким (то есть все его простые делители не превосходят B), то алгоритм с высокой вероятностью найдёт p. Если порядок не является гладким, алгоритм не сработает для данной кривой, и нужно выбрать другую.

Сложность

Ожидаемая сложность метода эллиптических кривых оценивается как:

\[ O\left( \exp\left( \sqrt{2 \ln p \ln \ln p} \right) \right) \]

где p — наименьший простой делитель n. Это субэкспоненциальная сложность, которая зависит от размера наименьшего делителя, а не от размера всего числа. Для чисел, у которых все делители велики (например, для чисел вида n = pq, где p и q близки по величине), МЭК может быть менее эффективен, чем метод квадратичного решета или решета числового поля.

Применение

Факторизация больших чисел

МЭК широко используется для факторизации чисел, которые не поддаются более простым методам. Он особенно эффективен для чисел, имеющих небольшой простой делитель (до 10^40). В криптоанализе МЭК применяется для атаки на RSA-модули, если они содержат слабые простые множители.

Распределённые вычисления

Благодаря малому потреблению памяти и возможности независимого перебора кривых, МЭК идеально подходит для распределённых проектов. Наиболее известный проект — ECMNET (Elliptic Curve Method Network), координируемый Полом Циммерманом. В рамках проекта были факторизованы многие числа, в том числе из списка трудных чисел Каннингема.

Проверка простоты

МЭК может использоваться как часть алгоритмов проверки простоты, например, в тесте простоты на эллиптических кривых (ECPP — Elliptic Curve Primality Proving). Однако в этом случае кривые строятся над полем, а не над кольцом вычетов.

Примеры

• В 1995 году с помощью МЭК был факторизован 99-значный делитель числа Ферма \( F_{10} = 2^{2^{10}} + 1 \).
• В 2010 году методом эллиптических кривых было факторизовано 79-значное число, входившее в список трудных чисел Каннингема.
• В 2020 году распределённый проект ECMNET завершил факторизацию 83-значного числа, которое было частью задачи RSA Factoring Challenge.

Сравнение с другими методами

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

Основным недостатком МЭК является его вероятностная природа: успех алгоритма зависит от случайного выбора кривой и точки. Для чисел, у которых все простые делители велики и не являются гладкими, может потребоваться перебор очень большого числа кривых, что делает метод непрактичным.

Кроме того, МЭК не гарантирует нахождение делителя за конечное время — в худшем случае он может работать экспоненциально долго. Однако на практике для чисел с делителями до 10^40 метод работает достаточно быстро.

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

• Хендрик Ленстра-младший разработал МЭК в возрасте 36 лет, работая в Калифорнийском университете в Беркли.
• Метод эллиптических кривых стал первым алгоритмом факторизации, который использует некоммутативную алгебраическую структуру (группу точек эллиптической кривой).
• В 2013 году был установлен рекорд факторизации с помощью МЭК: найдено 83-значное простое число, являвшееся делителем 2^1024 + 1.
• МЭК используется не только для факторизации, но и для вычисления дискретного логарифма на эллиптических кривых, хотя в этой области он менее эффективен, чем специализированные алгоритмы.

Источники

• Lenstra, H. W. (1987). «Factoring integers with elliptic curves». Annals of Mathematics, 126(3), 649–673.
• Silverman, J. H., & Tate, J. (1992). «Rational Points on Elliptic Curves». Springer.
• Crandall, R., & Pomerance, C. (2005). «Prime Numbers: A Computational Perspective». Springer.
• Zimmermann, P., & Dodson, B. (2006). «20 years of ECM». Lecture Notes in Computer Science, 4076, 1–20.
• ECMNET — The Elliptic Curve Method Network (координатор П. Циммерман).