Я ищу ссылку на следующий результат:
Добавление двух целых чисел в факторизованном представлении так же сложно, как и деление двух целых чисел в обычном двоичном представлении.
(Я уверен, что это там, потому что это то, что я когда-то задавался вопросом, а затем был взволнован, когда я наконец увидел это в печати.)
«Добавление двух целых чисел в факторизованном представлении» является проблемой: учитывая простые факторизации двух чисел и , выведите простую факторизацию . Обратите внимание, что простой алгоритм для этой проблемы использует факторизацию в стандартном двоичном представлении в качестве подпрограммы.у х + у
Обновление : спасибо Каве и Садеку за доказательства. Очевидно, чем больше доказательств, тем лучше, но я также хотел бы призвать больше помочь в поиске ссылки , которая, как я сказал, я вполне уверен, что существует. Я вспоминаю, как читал об этом в газете с другими интересными и не часто обсуждаемыми идеями, но я не помню, что это были за другие идеи или о чем была статья в целом.
Ответы:
Предположим, что мы можем решить эту проблему (давайте назовем ее FactSum) в классе сложности а C замкнут при лог- итерации (или рекурсии с ограниченным логарифмом ) (например, если мы можем вычислить x ∗ y, где ∗ - двоичная функция, мы можем вычисляется x 1 ∗ … ∗ x log n ) и содержит P (это последнее условие можно сделать более слабым). Мы покажем , что факторинг в также в C .C C log log x∗y ∗ x1∗…∗xlogn P C
Обратите внимание, что каждое число может быть записано как сумма степеней 2 . Каждый из них легко учесть.logn 2
Теперь, учитывая число, запишите его как сумму его степеней, затем запишите каждое слагаемое в представлении факторинга, а затем используйте алгоритм для суммирования их в представлении факторинга. Результатом будет факторинг входного числа.
Это показывает, что факторинг сводится к итерации вашей проблемы FactSum. Поэтому факторинг находится в P FactSum (и я думаю, что P можно заменить на N C 1 здесь).log PFactSum P NC1
источник
Я не знаю ссылки, но я думаю, что я нашел доказательство:
Предположим, у вас есть оракул который при вводе двух факторных чиселО
а также
выводит факторизацию .х + у
Имея доступ к , мы можем разложить любое число N за полиномиальное время, используя следующую рекурсивную процедуру.О N
ПРОЦЕДУРНЫЙ фактор ( )N
Анализ:
По теореме простых чисел для достаточно большого существует множество простых чисел между N / 2 и N - 1 . Если N настолько мало, что в этом интервале нет простого числа, вы можете легко вычислить N. Следовательно, шаг 1 проходит.N N/ 2 N- 1 N N
На шаге 2 вы можете использовать AKS или любой другой тест на простоту за полиномиальное время.
Число рекурсии просто , так как на каждом шаге N разрезается пополам (как минимум)O ( LG( N) ) = O ( | N| ) N
PS-1: Предположение, что гипотеза Гольдбаха может помочь в ускорении процедуры для четных (и, возможно, нечетных) целых чисел.
PS-2: Используемое сокращение - сокращение Кука. Кто-то может быть заинтересован в проведении доказательства с использованием редукций Карпа.
источник
Этот ответ не зависит от моего предыдущего ответа . Его цель - решить проблему @ Kaveh в комментариях:
У меня была похожая проблема:
(Сокращения Карпа предназначены для решения проблем. Здесь под сокращением Карпа я подразумеваю сокращение Кука одним запросом. Извините за нестандартную терминологию!)
Ответ ниже основан на обсуждениях здесь: /math/54580/factoring-some-integer-in-the-given-interval .
В этом ответе я приведу детерминированное сокращение Карпа за полиномиальное время от факторинга к факторизации суммы двух целых чисел, представленных их факторизациями . Однако есть одна загвоздка: в ходе доказательства я буду использовать следующее теоретико-числовое предположение:
источник