Сведение по Куку задачи факторизации к языку из NP

Формулировка задачи

Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.

Сведение задачи факторизации к языку FACTOR

Рассмотрим язык [math]\mbox{FACTOR} = \{(n, x) \mid \exists k\lt x, ~ k \neq 1,~ n~\vdots~k\}[/math].

Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа [math]n[/math].

Пусть функция f разрешает язык FACTOR:

[math] \mbox{f(n, x)}= \begin{cases} \mbox{true}, ~(n, x) \in \mbox {FACTOR} \\ \mbox{false}, ~(n, x) \not\in \mbox{FACTOR} \end{cases} [/math]

Тогда, воспользовавшись двоичным поиском, можно написать функцию p, работающую за полином от длины входа и возвращающую список A простых делителей n:

p(n)
{
 n' = n;
 A = {};
 while (n' >  1)
  {
   if (!f(n', n')) //если число простое - добавляем его в список делителей и завершаем цикл
    {
     A.add(n');
     n' = 1;
     break;
    }
   r = n';
   l = 2;
   while (r > l + 1) //находим наименьший простой делитель
    {
     c = (l + r) / 2;
     if (f(n', c))
       r = c;
     else
       l = c;
    }
   A.add(l);
   n' = n' / l;
  }
 return A;
}

Принадлежность языка FACTOR классу NP

[math]\mbox{FACTOR} \in \mbox{NP}[/math].

Сертификатом y является нетривиальный делитель числа n, а верификатором - функция, которая проверяет, является ли y делителем n и меньше ли он числа x:

R(<n, x>, y)
{
 if ((y >= x) || (y <= 1))
     return false;
 if (n % y != 0)
     return false;
 return true;
}

Таким образом, задача FACTORIZE сводится по Куку за полиномиальное время к языку FACTOR, принадлежащему классу NP.