Как можно P =? NP усиливают целочисленную факторизацию

Если действительно равен , как это улучшит наши алгоритмы, чтобы быстрее вычислять целые числа? Другими словами, какое понимание даст нам этот факт для лучшего понимания целочисленной факторизации?${\sf P}$${\sf NP}$

Если , и у нас есть алгоритм, который может решить проблему k-SAT за полиномиальное время, тогда целочисленная факторизация может быть просто сведена к k-SAT, описывая факторинг как проблему в k-SAT.$P=NP$

По сути, это работает следующим образом: вы создаете кучу переменных, каждая из которых представляет биты , и . Тогда вы формулируете задачу k-SAT как$p$$q$$n$ . Поскольку n известно, вы можете установить эти значения. Тогда удовлетворительное присваивание опишет действительные p и q . Чтобы описать умножение в k-SAT, вы можете использовать любой из известных алгоритмов умножения и описать его логическую схему в k-SAT. Для получения дополнительной информации о сокращении факторинга до k-SAT, смотритездесь.$p*q=n$$n$$p$$q$

Что касается лучшего понимания факторинга, это, вероятно, потребует дополнительных исследований и анализа магического алгоритма (который может решить NP-полные задачи за детерминированный полиномиальный момент времени) и, возможно, специализирования его для постановки целочисленного факторинга задачи k-SAT (которая, очевидно, имеет очень специфическая структура, в зависимости от используемого алгоритма умножения).

Решающей задачей для факторинга является и факторинг можно свести к нему за детерминированный полиномиальный момент времени.$\mathsf{NP}$

Если то любая задача в N P, включая факторинг, будет иметь алгоритм полиномиального времени.$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$

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