Сведение по Куку задачи факторизации к языку из 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)
{
 b = 2;
 t = 3; 
 A = {};
 while (t <= n/2 + 1)
 {
   while (f(n, t))
     {
      n /= b;
      A.add(b);
     }
   while ((t < n/2 + 1)&&(!f(n, t)))
     {
      t++;
     }
   b = t - 1;
 }
 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.