Добавить целые числа, представленные их факторизацией, так же сложно, как и факторинг? Справочный запрос

22

Я ищу ссылку на следующий результат:

Добавление двух целых чисел в факторизованном представлении так же сложно, как и деление двух целых чисел в обычном двоичном представлении.

(Я уверен, что это там, потому что это то, что я когда-то задавался вопросом, а затем был взволнован, когда я наконец увидел это в печати.)

«Добавление двух целых чисел в факторизованном представлении» является проблемой: учитывая простые факторизации двух чисел и , выведите простую факторизацию . Обратите внимание, что простой алгоритм для этой проблемы использует факторизацию в стандартном двоичном представлении в качестве подпрограммы.у х + уxyx+y

Обновление : спасибо Каве и Садеку за доказательства. Очевидно, чем больше доказательств, тем лучше, но я также хотел бы призвать больше помочь в поиске ссылки , которая, как я сказал, я вполне уверен, что существует. Я вспоминаю, как читал об этом в газете с другими интересными и не часто обсуждаемыми идеями, но я не помню, что это были за другие идеи или о чем была статья в целом.

Джошуа Грохов
источник
6
Я думаю, что лучшим названием будет «Факторизация суммы двух целых чисел, представленных их факторизацией, так же сложно, как факторинг?»
MS Dousti
1
Хороший вопрос Если мы можем записать данное целое число в виде суммы двух простых в множителях, то, что вы хотите, следует. Это легко сделать , если мы хотим logn чисел, но я не вижу , как это сделать , даже с loglogn чисел. Возможно, стоит взглянуть на классы чисел, которые легко учесть.
Каве
1
некоторые связанные вопросы по МО и математике: 1 , 2 , 3
Каве

Ответы:

15

Предположим, что мы можем решить эту проблему (давайте назовем ее FactSum) в классе сложности а C замкнут при лог- итерации (или рекурсии с ограниченным логарифмом ) (например, если мы можем вычислить x y, где - двоичная функция, мы можем вычисляется x 1x log n ) и содержит P (это последнее условие можно сделать более слабым). Мы покажем , что факторинг в также в C .CCloglogxY*x1*...*ИксжурналNпС

Обратите внимание, что каждое число может быть записано как сумма степеней 2 . Каждый из них легко учесть.журналN2

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

Это показывает, что факторинг сводится к итерации вашей проблемы FactSum. Поэтому факторинг находится в P FactSum (и я думаю, что P можно заменить на N C 1 здесь).журналпFactSumпNС1

Кава
источник
10

Я не знаю ссылки, но я думаю, что я нашел доказательство:

Предположим, у вас есть оракул который при вводе двух факторных чиселО

Иксзнак равноΠязнак равно1Nпяαя

а также

Yзнак равноΠязнак равно1мQяβя,

выводит факторизацию .Икс+Y

Имея доступ к , мы можем разложить любое число N за полиномиальное время, используя следующую рекурсивную процедуру.ОN

ПРОЦЕДУРНЫЙ фактор ( )N

  1. Найдите такое простое число , что N / 2 x N - 1 , и пусть y = N - x .ИксN/2ИксN-1Yзнак равноN-Икс
  2. Если не простое число, получите факторизацию y с помощью фактора рекурсивного вызова ( y ) и выведите O ( x , f a c t o r ( y ) ) .YYYО(Икс,еaсTор(Y))
  3. Иначе вывод .О(Икс,Y)

Анализ:

По теореме простых чисел для достаточно большого существует множество простых чисел между N / 2 и N - 1 . Если N настолько мало, что в этом интервале нет простого числа, вы можете легко вычислить N. Следовательно, шаг 1 проходит.NN/2N-1NN

На шаге 2 вы можете использовать AKS или любой другой тест на простоту за полиномиальное время.

Число рекурсии просто , так как на каждом шаге N разрезается пополам (как минимум)О(Л.Г.(N))знак равноО(|N|)N


PS-1: Предположение, что гипотеза Гольдбаха может помочь в ускорении процедуры для четных (и, возможно, нечетных) целых чисел.

PS-2: Используемое сокращение - сокращение Кука. Кто-то может быть заинтересован в проведении доказательства с использованием редукций Карпа.

М.С. Дусти
источник
3
Я думаю, что открыто, если мы сможем найти простое число в заданном диапазоне эффективно, поэтому я не вижу, как у вас дела 1.
Каве
1
@Kaveh: Ты прав! С некоторыми дополнительными шагами, я думаю, я могу изменить алгоритм, чтобы не требовать, чтобы был простым, а затем разложить его как y ; или мы можем предположить, что уменьшение является вероятностным (поскольку в вероятностном полиномиальном времени мы можем найти простое число в данном диапазоне). ИксY
MS Dousti
2
Да, я думаю, что у нас была та же идея, то есть мы хотели найти простые для вычисления целых чисел, которые суммируют с вводом, вы пытались использовать простые числа, я использовал степени 2. :) Я до сих пор не знаю, сможем ли мы сделать это с меньше, чем логарифмическое количество запросов к оракулу, и это, кажется, связано с интересным и естественным вопросом теории чисел (запись чисел как суммы простых для факторных чисел).
Каве
5

Этот ответ не зависит от моего предыдущего ответа . Его цель - решить проблему @ Kaveh в комментариях:

Это легко сделать , если мы хотим чисел, но я не вижу , как это сделать , даже с лог - лог п чисел.журналNжурналжурналN

У меня была похожая проблема:

Используемое сокращение - сокращение Кука. Кто-то может быть заинтересован в проведении доказательства с использованием редукций Карпа.

(Сокращения Карпа предназначены для решения проблем. Здесь под сокращением Карпа я подразумеваю сокращение Кука одним запросом. Извините за нестандартную терминологию!)


Ответ ниже основан на обсуждениях здесь: /math/54580/factoring-some-integer-in-the-given-interval .


В этом ответе я приведу детерминированное сокращение Карпа за полиномиальное время от факторинга к факторизации суммы двух целых чисел, представленных их факторизациями . Однако есть одна загвоздка: в ходе доказательства я буду использовать следующее теоретико-числовое предположение:

pNpn+1pn+1pn=O(log2pn)

NNзнак равно|N|знак равноО(журналN)N[N-журнал3N,N]журнал3Nзнак равноО(N3)

Икс[N-журнал3N,N]Yзнак равноN-Икс

0Yжурнал3N|Y|знак равноО(журналжурналN)знак равноО(журналN)Y

(Икс,Y)Nзнак равноИкс+Y

М.С. Дусти
источник
Спасибо Sadeq, но условные результаты не то, что я просил. PS: меня интересуют интересные представления чисел, и представление, которое можно получить из вашего ответа (вычеркивая большое простое число), не выглядит для меня очень интересным. Для придания аромата того, что мне было бы интересно: каждое натуральное число - это сумма четырех квадратов .
Каве