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

==Формулировка задачи==
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители. 
==Сведение задачи факторизации к языку FACTOR==
Рассмотрим язык <tex>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</tex>. 

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

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

<tex>
\mbox{f(n, x)}= 
\begin{cases}
\mbox{true}, ~(n, x) \in \mbox {FACTOR} \\
\mbox{false}, ~(n, x) \not\in \mbox{FACTOR}
\end{cases}
</tex>

Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''':
<code>
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;
}
</code>

==Принадлежность языка FACTOR классу NP==
<tex>\mbox{FACTOR} \in \mbox{NP}</tex>. 

Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
<code>
 R(<n, x>, y)
 {
  '''if''' ((y >= x) || (y <= 1))
      '''return''' false;
  '''if''' (n % y != 0)
      '''return''' false;
  '''return''' true;
 }
</code>

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