О детерминированном поиске элемента высокого порядка по модулю составного числа

Основная информация

• ID статьи: 2506.07668
• Название: On Deterministically Finding an Element of High Order Modulo a Composite
• Авторы: Ziv Oznovich, Ben Lee Volk (Школа компьютерных наук Эфи Араци, Университет Райхмана, Израиль)
• Классификация: cs.DS (Структуры данных и алгоритмы), math.NT (Теория чисел)
• Дата подачи: 11 июня 2025 г. (arXiv v3)
• Ссылка на статью: https://arxiv.org/abs/2506.07668

Аннотация

В данной работе предложен детерминированный алгоритм, который при заданном составном числе $N$ и целевом порядке $D \geq N^{1/6}$ работает за время $D^{1/2+o(1)}$ и либо находит элемент $a \in \mathbb{Z}_N^*$ с мультипликативным порядком не менее $D$, либо находит нетривиальный делитель $N$. Алгоритм улучшает результат Hittmeir'а, который требовал более строгого условия $D \geq N^{2/5}$. Когда $N$ имеет делители, являющиеся $r$-ми степенями ($r \geq 2$), алгоритм обеспечивает те же гарантии при условии $D \geq N^{1/6r}$.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Сложность факторизации целых чисел: Факторизация целых чисел является центральной проблемой вычислительной теории чисел. Лучшие известные рандомизированные алгоритмы (такие как решето числового поля) имеют субэкспоненциальную сложность, тогда как лучшие детерминированные алгоритмы до недавнего времени имели сильно экспоненциальную сложность.
2. Значимость детерминированных алгоритмов: Хотя теоретически считается, что каждый рандомизированный алгоритм может быть смоделирован детерминированным алгоритмом с полиномиальным замедлением, получение безусловных результатов дерандомизации остаётся важным в теории сложности и разработке алгоритмов.
3. Роль элементов высокого порядка: Прорывная работа Hittmeir'а и Harvey показала, что детерминированный поиск элементов с большим мультипликативным порядком является ключевым для разработки эффективных детерминированных алгоритмов факторизации.

Исследовательская мотивация

1. Улучшение диапазона параметров: Алгоритм Hittmeir'а требует $D \geq N^{2/5}$, что является относительно строгим условием, ограничивающим область применения алгоритма.
2. Ускорение алгоритма факторизации: В алгоритме факторизации Harvey-Hittmeir этап поиска элемента высокого порядка работает за время $N^{1/5+o(1)}$, являясь одним из узких мест алгоритма.
3. Теоретическое значение: Дерандомизация является важной проблемой теоретической информатики, а её реализация в алгоритмах теории чисел имеет глубокое теоретическое значение.

Основные вклады

1. Улучшение параметров: Снижение требования к целевому порядку с $D \geq N^{2/5}$ до $D \geq N^{1/6}$, значительно расширяя область применения алгоритма.
2. Сохранение времени выполнения: При ослаблении требований к параметрам сохраняется временная сложность $D^{1/2+o(1)}$.
3. Оптимизация для $r$-х степеней: Когда $N$ имеет делители, являющиеся $r$-ми степенями, требование дополнительно снижается до $D \geq N^{1/6r}$.
4. Улучшение алгоритма факторизации: Предоставлены новые подпрограммы факторизации, улучшающие методы факторизации при известной информации о остаточных классах.
5. Теоретические инструменты: Доказаны более точные границы количества элементов в последовательных целых числах, удовлетворяющих определённым условиям сравнения.

Подробное описание методов

Определение задачи

Вход: Составное число $N$ и целевой порядок $D \geq N^{1/6}$Выход: Либо элемент $a \in \mathbb{Z}_N^*$ с мультипликативным порядком не менее $D$, либо нетривиальный делитель $N$Временная сложность: $D^{1/2+o(1)}$

Архитектура алгоритма

Структура основного алгоритма (Algorithm 4.1)

Алгоритм использует стратегию итеративного поиска, включающую следующие этапы:

1. Предварительная обработка: Проверка малых делителей методом Strassen
2. Итеративный поиск: Поиск для $a = 2, 3, 4, \ldots$
3. Вычисление порядка: Использование улучшенного метода Baby-step Giant-step
4. Накопление информации: Ведение переменной $M$ для записи наименьшего общего кратного порядков проверенных элементов
5. Финальная факторизация: Использование нового алгоритма факторизации при достаточно большом $M$

Основные технические улучшения

1. Улучшенная граница для последовательных корней (Claim 2.6)

Для больших целых чисел N, ℓ, если N имеет простой делитель p > 2ℓ,
то среди m = 10√ℓ последовательных целых чисел {a, a+1, ..., a+m}
существует элемент b такой, что b^ℓ ≢ 1 (mod N)

Это улучшает сложность поиска в алгоритме Hittmeir'а с $O(M)$ до $O(\sqrt{M})$.

2. Алгоритм факторизации по остаточным классам (Theorem 3.2) При заданных $N$ и $s \geq N^α$ ($α \leq 1/(4r)$, $\gcd(N,s) = 1$), алгоритм может за время $N^{1/(4r)-α+o(1)}$ найти все $r$-е степени делителей, удовлетворяющие $p \equiv 1 \pmod{s}$.

Технические инновации

1. Улучшение конструкции полиномов

На основе алгоритма Harvey-Hittmeir базовый полином $f(x) = x + P$ улучшен до: $g(x) = x + s' + s'(P - \tilde{P})$ где $s'$ — обратный элемент $s$ по модулю $N$, $\tilde{P}$ — остаток $P$ по модулю $s$.

2. Сокращение пространства поиска

Используя информацию о простых делителях $p \equiv 1 \pmod{s}$, размер поиска корней сокращается с $H$ до примерно $H/s$, уменьшая количество интервалов поиска в $s$ раз.

3. Применение LLL-редукции базиса решётки

Построение системы полиномов: