Какова наихудшая сложность числового поля сита?

Учитывая композит $N\in\Bbb N$ общего числа поля решета является наиболее известным алгоритмом факторизации для целого факторизации $N$ . Это рандомизированный алгоритм, и мы получаем ожидаемую сложность $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ к фактору $N$ .

Я искал информацию о сложности наихудшего случая по этому рандомизированному алгоритму. Однако я не могу найти информацию.

(1) Какова сложность в наихудшем случае сита числового поля?

(2) Также можно ли убрать случайность здесь, чтобы получить детерминистический субэкспоненциальный алгоритм?

reference-request derandomization factoring average-case-complexity worst-case
источник

Ответы:

Сито числового поля никогда не подвергалось строгому анализу. Сложность, которую вы цитируете, просто эвристическая. Единственным субэкспоненциальным алгоритмом, который был тщательно проанализирован, является алгоритм факторизации Диксона , который очень похож на квадратичное сито. Согласно Википедии, алгоритм Диксона работает за время . Алгоритм Диксона рандомизирован. $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

Все (эвристически) известные субэкспоненциальные алгоритмы требуют рандомизации. Алгоритм Диксона должен найти целые числа такие что является гладким (может быть преобразован в произведение небольших простых чисел) и «случайным», а сито с числовым полем имеет аналогичные, но более сложные требования. Методу эллиптической кривой необходимо найти эллиптическую кривую по модулю , порядок которой по модулю некоторого множителя является гладким. В обоих случаях, кажется, сложно дерандомизировать алгоритмы. $x$ $x^2 \pmod{n}$ $n$ $n$

Номинальная сложность всех этих алгоритмов в худшем случае равна бесконечности: в случае квадратичного сита и сита числового поля вы всегда можете генерировать один и тот же , а в методе эллиптической кривой вы всегда можете генерировать одну и ту же эллиптическую кривую. , Есть много способов обойти это, например, запустить алгоритм экспоненциального времени параллельно. $x$

Юваль Фильмус
источник

Так как вы также коснулись ECM: мы знаем рандомизированный алгоритм подвыражения для вычисления за времени с использованием ECM, где неизвестно и рандомизировано. У вас есть оценка, сколько испытаний этого алгоритма достаточно, чтобы получить и где ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Я понятия не имею, что такое , но, вообще говоря, при выборе параметров в ECM мы балансируем между вероятностью того, что кривая достаточно гладкая, и временем требуемым для тестирования каждой кривой. Обычно точка баланса - это когда . Таким образом, ожидаемое количество испытаний должно быть .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Юваль Фильмус

n!

$n!$ является факториалом . Это открытая проблема, чтобы получить прямую сложность факториала. Мы знаем, как вычислить где неизвестно во время субэкспозиции. Если мы знаем два разных и , мы можем получитьв подэкспрессе, если .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Я помню подсчет некоторое время назад. Я не думаю, что смог бы добиться улучшения, так как был подвох, и я не помню деталей.

последний абзац кажется странным и может быть уточнен. Вы говорите о сценарии, в котором ГСЧ "сломан" в том смысле, что он не определяет общее пространство распределения? но тогда не поможет ли параллелизм? потому что это будет тот же «сломанный» ГСЧ параллельно? или идея в том, что параллельно будет работать другой ГСЧ? на самом деле параллельная сложность алгоритмов факторинга - это совсем другая сложная тема, например, некоторые могут быть распараллелены лучше, чем другие, big-O может не совсем подходить и т. д.

vzn

В последние несколько месяцев была тщательно проанализирована версия сита числового поля: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Как время работы в худшем случае составляет безоговорочно и в режиме GRH. Это не для "классического" сита числового поля, а слегка модифицированная версия, которая рандомизирует больше шагов, чтобы облегчить анализ сложности. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Я считаю, что соответствующий документ все еще находится на рассмотрении.

Обновление: бумага выходит. Джонатан Д. Ли и Рамаратнам Венкатесан, «Строгий анализ поля чисел с рандомизированными числами», Журнал теории чисел 187 (2018), с. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
источник

Можете ли вы дать более полную ссылку, где мы можем узнать больше, с названием, автором и где опубликовано, так что ответ по-прежнему полезен, даже если ссылка перестает работать?

Поскольку результат был объявлен только недавно, я считаю, что он в настоящее время пересматривается, как указано в моем ответе, и поэтому еще не опубликован. Я обновлю свой ответ в будущем, когда будет доступна информация о публикации.

джао

FWIW это, кажется, не на arxiv.org. Тем не менее, автором является Ramarathnam Venkatesan, который может помочь в будущих поисках, если они будут необходимы.

Питер Тейлор

На самом деле это работа с двумя авторами (Дж. Д. Ли и Р. Венкатесан): cmi.ac.in/activities/…

Сари