15
правок
Изменения
Нет описания правки
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители.
==Сведение задачи факторизации к языку FACTOR==
Рассмотрим язык <mathtex>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</mathtex>.
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>.
Пусть функция '''f''' разрешает язык '''FACTOR''':
<mathtex>
\mbox{f(n, x)}=
\begin{cases}
\mbox{false}, ~(n, x) \not\in \mbox{FACTOR}
\end{cases}
</mathtex>
Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''':
==Принадлежность языка FACTOR классу NP==
<mathtex>\mbox{FACTOR} \in \mbox{NP}</mathtex>.
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
