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

12

Учитывая композит NN общего числа поля решета является наиболее известным алгоритмом факторизации для целого факторизации N . Это рандомизированный алгоритм, и мы получаем ожидаемую сложность O(e649(logN)13(loglogN)23)к факторуN.

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

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

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


источник

Ответы:

14

Сито числового поля никогда не подвергалось строгому анализу. Сложность, которую вы цитируете, просто эвристическая. Единственным субэкспоненциальным алгоритмом, который был тщательно проанализирован, является алгоритм факторизации Диксона , который очень похож на квадратичное сито. Согласно Википедии, алгоритм Диксона работает за время . Алгоритм Диксона рандомизирован.eO(22lognloglogn)

Все (эвристически) известные субэкспоненциальные алгоритмы требуют рандомизации. Алгоритм Диксона должен найти целые числа такие что является гладким (может быть преобразован в произведение небольших простых чисел) и «случайным», а сито с числовым полем имеет аналогичные, но более сложные требования. Методу эллиптической кривой необходимо найти эллиптическую кривую по модулю , порядок которой по модулю некоторого множителя является гладким. В обоих случаях, кажется, сложно дерандомизировать алгоритмы.xn nx2(modn)nn

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

Юваль Фильмус
источник
1
Так как вы также коснулись ECM: мы знаем рандомизированный алгоритм подвыражения для вычисления за времени с использованием ECM, где неизвестно и рандомизировано. У вас есть оценка, сколько испытаний этого алгоритма достаточно, чтобы получить и где ? O ( e x p ( n!rrn! рн! s(r,s)=1O(exp(logn))rn!rn!s(r,s)=1
1
Я понятия не имею, что такое , но, вообще говоря, при выборе параметров в ECM мы балансируем между вероятностью того, что кривая достаточно гладкая, и временем требуемым для тестирования каждой кривой. Обычно точка баланса - это когда . Таким образом, ожидаемое количество испытаний должно быть . p T 1 / p T O ( exp n!rpT1/pTO(explogn)
Юваль Фильмус
n n ! р р н ! р н ! s ( n ! r , n ! s ) = n ! ( r , s ) = 1n!является факториалом . Это открытая проблема, чтобы получить прямую сложность факториала. Мы знаем, как вычислить где неизвестно во время субэкспозиции. Если мы знаем два разных и , мы можем получитьв подэкспрессе, если . nn!rrn!rn!s(n!r,n!s)=n!(r,s)=1
Я помню подсчет некоторое время назад. Я не думаю, что смог бы добиться улучшения, так как был подвох, и я не помню деталей.
последний абзац кажется странным и может быть уточнен. Вы говорите о сценарии, в котором ГСЧ "сломан" в том смысле, что он не определяет общее пространство распределения? но тогда не поможет ли параллелизм? потому что это будет тот же «сломанный» ГСЧ параллельно? или идея в том, что параллельно будет работать другой ГСЧ? на самом деле параллельная сложность алгоритмов факторинга - это совсем другая сложная тема, например, некоторые могут быть распараллелены лучше, чем другие, big-O может не совсем подходить и т. д.
vzn
6

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

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

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

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

djao
источник
1
Можете ли вы дать более полную ссылку, где мы можем узнать больше, с названием, автором и где опубликовано, так что ответ по-прежнему полезен, даже если ссылка перестает работать?
DW
Поскольку результат был объявлен только недавно, я считаю, что он в настоящее время пересматривается, как указано в моем ответе, и поэтому еще не опубликован. Я обновлю свой ответ в будущем, когда будет доступна информация о публикации.
джао
FWIW это, кажется, не на arxiv.org. Тем не менее, автором является Ramarathnam Venkatesan, который может помочь в будущих поисках, если они будут необходимы.
Питер Тейлор
На самом деле это работа с двумя авторами (Дж. Д. Ли и Р. Венкатесан): cmi.ac.in/activities/…
Сари