Почему целочисленная факторизация представляет собой неполиномиальное время?

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

Итак, целочисленная факторизация в настоящее время не является проблемой полиномиального времени, но тест примитивности. Предположим, что число, которое нужно проверить, равно n. Если мы запустим программу только для того, чтобы решить, может ли каждое число от 1 до sqrt (n) делить n, а если да, то сохраните номер. Я думаю, что эта программа является полиномиальным временем, не так ли?

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

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

Ответ 1

Случайные описания сложности, такие как "алгоритм полиномиального факторинга", обычно относятся к сложности по отношению к размеру ввода, а не к интерпретации ввода. Поэтому, когда люди говорят "нет известного алгоритма полиномиального факторинга", они означают, что нет известного алгоритма факторизации N-битовых натуральных чисел, который выполняется во временном многочлене относительно N. Не является полиномиальным относительно самого числа, которое может быть до 2 ^ N.

Ответ 2

Трудность факторизации - одна из тех прекрасных математических задач, которые просто понять и сразу же переходят к краю человеческого знания. Суммировать (сегодняшние) знания по этому вопросу: мы не знаем, почему это сложно, а не с какой-либо степенью доказательности, и с лучшими методами, которые мы проводили более чем за полиномиальное время (но также значительно меньше, чем экспоненциальное время). Результат, который тестирование приматов даже в P довольно недавний; см. связанную страницу Википедии.

Лучшее эвристическое объяснение, которое я знаю для трудности, состоит в том, что простые числа распределяются случайным образом. Одним из наиболее понятных результатов является теорема Дирихле. Эта теорема утверждает, что каждая арифметическая прогрессия содержит бесконечно много простых чисел, другими словами, вы можете думать о том, что простые числа являются плотными по отношению к прогрессиям, то есть вы не можете избежать столкновения с ними. Это простейшая из довольно большой коллекции таких результатов; во всех них простые числа выглядят так же, как и случайные числа.

Трудный факторинг, таким образом, аналогичен невозможности обращения вспять одноразовой площадки. В одноразовой клавиатуре мы немного не знаем XOR с другим, которого у нас нет. Мы получаем нулевую информацию об отдельном бите, зная результат XOR. Замените "бит" на "простое" и умноженное на XOR, и у вас есть проблема факторинга. Это как если бы вы умножили два случайных числа вместе, и вы получите очень мало информации из продукта (вместо нулевой информации).

Ответ 3

Если мы запустим программу, чтобы решить, может ли каждое число от 1 до sqrt (n) делить n, а если ответ да, то сохраните номер.

Даже игнорируя, что тест на делимость займет больше времени для больших чисел, этот подход занимает почти в два раза больше, если вы просто добавите одну (двоичную) цифру в n. (На самом деле это займет вдвое больше, если вы добавите две цифры)

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

Но обратите внимание, что это наблюдение относится только к предложенному алгоритму. Пока неизвестно, является ли целочисленная факторизация полиномиальной или нет. Криптографы надеются, что это не так, но есть и альтернативные алгоритмы, которые не зависят от сложной простой факторизации (например, криптографии с использованием эллиптической кривой), на всякий случай...