Ссылка для оптимального алгоритма факторинга Левина?

В « Совете начинающему аспиранту » Мануэля Блума :

Леонид Левин верит, как я это делаю, какой бы ни был ответ на P = NP? проблема, это не будет так, как вы думаете, должно быть. И он привел несколько замечательных примеров. Например, он дал ФАКТОРИНГОВЫЙ АЛГОРИТМ, который оказался оптимально оптимальным, вплоть до мультипликативной константы. Он доказывает, что если его алгоритм экспоненциальный, то каждый алгоритм FACTORING экспоненциальный. Эквивалентно, если какой-либо алгоритм для факторинга является поли-временем, то его алгоритм является поли-временем. Но мы не смогли определить время работы его алгоритма, потому что, в строгом смысле, время его работы не анализируется.

Страница публикаций Левина возвращает 404, DBLP не показывает ничего, связанного с факторингом, а поиск «Фактор Леонида Левина» в Google Scholar не дает ничего интересного, что я мог бы найти. AFAIK обобщенное сито - самый быстрый алгоритм, известный для факторинга. О чем говорит Мануэль Блюм? Может кто-нибудь связать меня с бумагой?

ds.algorithms reference-request factoring Кристофер Монсанто
источник

Ответы:

Мануэль Блум говорит о применении универсального алгоритма поиска Левина к задаче факторизации целых чисел. Идея алгоритма поиска Универсальной Левина в равной степени применимо к любой проблеме в . $NP$

Вот цитата из заметок лекций, данных Блумом по БЕЗОПАСНОСТИ и КРИПТОГРАФИИ:

АЛГОРИТМ ОПТИМАЛЬНОГО ЧИСЛЕННОГО (ФАКТОРИРОВАНИЯ) Леонида ЛЕВИНА. Пусть SPLIT обозначает любой алгоритм, который вычисляет INPUT: положительное составное (т.е. не простое) целое число n. ВЫХОД: нетривиальный фактор n.

Теорема: существует «оптимальный» алгоритм разделения чисел, который мы называем OPTIMAL-SPLIT. Этот алгоритм является ОПТИМАЛЬНЫМ в том смысле, что: для каждого алгоритма разделения чисел SPLIT существует (довольно большая, но фиксированная) постоянная C, такая, что для каждого положительного составного целочисленного входа n «время выполнения» OPTIMAL-SPLIT на входе n равно самое большее C время работы SPLIT на входе n.

Вот оптимальный алгоритм факторинга Левина :

ОПТИМАЛЬНО-РАЗДЕЛЕННЫЙ АЛГОРИТМ: НАЧАЛО Перечислите все алгоритмы в порядке размера, лексикографически в пределах каждого размера. Запустите все алгоритмы так, чтобы в любой момент времени i-й алгоритм получал [1 / (2 ^ i)] часть времени для выполнения. Когда алгоритм останавливается с некоторым выходным целым числом m в диапазоне 1 <m <n, проверьте, делит ли m n (т.е. если n mod m = 0). Если так, верните m. КОНЕЦ

Мухаммед Аль-Туркистани
источник

Может кто-нибудь объяснить, почему дробь должна быть 1 / (2 ^ i), а не что-то более простое, как 1 / i?

netvope

@netvope: бесконечная сумма 1 / i расходится. Вы могли бы сделать это с 1 / i ^ 2, но 1/2 ^ i намного проще.

Сурьма

$NP \cap coNP$ проблема. Вот эскиз для факторинга в частности.

Учитывая число, которое мы хотим фактор Н.

Является ли N простым? Если это так, выведите «PRIME» еще:

За $i = 1...\infty$

За $P = 1...i$

Запустите программу P для i шагов с вводом N

Если P выводит два целых числа (L, M) и $L \neq 1$ и $M \neq 1$ и $N = L*M$ затем вывод $(L,M)$

Артем Казнатчеев
источник

Вы не можете использовать известный тест первичности, потому что он не известен как более быстрый, чем оптимальный факторинг. Помимо этого, я не понимаю один момент. Чтобы доказать, что это оптимально для факторизации до постоянного множителя, я думаю, что мы должны доказать, что умножение на последнем шаге не является доминирующим слагаемым во временной сложности. Если я правильно помню, самый быстрый из известных алгоритмов умножения в асимптотике основан на БПФ и занимает O (n log n log log n) времени для n-разрядных целых чисел. Можно ли доказать, что оптимальный факторинг занимает как минимум столько времени, сколько это?

Tsuyoshi Ito

@Tsuyoshi: я думаю, что вы правы в том, что этот алгоритм не может быть оптимальным, если известные тесты умножения / простоты сложнее, чем факторинг. Однако, если вы прочитаете цитату Блюма выше, он скажет только, что алгоритм Левина является полиномиальным тогда и только тогда, когда оптимальный алгоритм является решением этой проблемы. Две другие вещи: (1) как можно избежать использования известного теста простоты в этом алгоритме? (2) Я думаю, что этот алгоритм сформулирован не совсем правильно в том смысле, что время выполнения не распределено должным образом между различными программами; см. ответ Al-Turkistany для правильной формулировки.

Питер Шор

@Peter: Хорошо, цитата Блума говорит, что «он [Левин] дал ФАКТОРИНГОВЫЙ АЛГОРИТМ, который доказуемо оптимален, вплоть до мультипликативной константы». Но, учитывая, что мы даже не знаем, занимает ли факторинг больше линейного времени или нет, в это утверждение трудно поверить как есть.

Tsuyoshi Ito

@ Tsuyoshi: я вижу, я читал неправильную цитату Блума.

Питер Шор