Сведение по Куку задачи факторизации к языку из NP — различия между версиями
| Строка 4: | Строка 4: | ||
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>. | Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>. | ||
| − | Используя его в качестве оракула, можно за полиномиальное время найти | + | Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>. |
Пусть функция '''f''' разрешает язык '''FACTOR''': | Пусть функция '''f''' разрешает язык '''FACTOR''': | ||
| Строка 16: | Строка 16: | ||
</math> | </math> | ||
| − | Тогда можно написать функцию '''p''', работающую | + | Тогда можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': |
<code> | <code> | ||
p(n) | p(n) | ||
| Строка 22: | Строка 22: | ||
n' = n; | n' = n; | ||
A = {}; | 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; | '''return''' A; | ||
} | } | ||
Версия 16:26, 19 марта 2010
Формулировка задачи
Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.
Сведение задачи факторизации к языку FACTOR
Рассмотрим язык .
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа .
Пусть функция f разрешает язык FACTOR:
Тогда можно написать функцию 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
.
Сертификатом 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.
