Сведение по Куку задачи факторизации к языку из 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)
{
 A = {};
 while (n > 1)
  {
   if (!f(n, n)) //если число простое - добавляем его в список делителей и завершаем цикл
    {
     A.add(n);
     n = 1;
     break;
    }
   // Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R
   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.