Сведение по Куку задачи факторизации к языку из NP — различия между версиями
| Строка 18: | Строка 18: | ||
Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': | Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': | ||
<code> | <code> | ||
| − | + | p(n) { | |
| − | |||
A = {}; | A = {}; | ||
| − | '''while''' (n > 1) | + | '''while''' (n > 1) { |
| − | + | '''if''' (!f(n, n)) { //''если число простое - добавляем его в список делителей и завершаем цикл'' | |
| − | '''if''' (!f(n, n)) //''если число простое - добавляем его в список делителей и завершаем цикл'' | ||
| − | |||
A.add(n); | A.add(n); | ||
n = 1; | n = 1; | ||
'''break'''; | '''break'''; | ||
| − | + | } | |
// ''Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R'' | // ''Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R'' | ||
R = n; | R = n; | ||
L = 2; | L = 2; | ||
| − | '''while''' (R > L + 1) //''находим наименьший простой делитель'' | + | '''while''' (R > L + 1) { //''находим наименьший простой делитель'' |
| − | |||
c = (L + R) / 2; | c = (L + R) / 2; | ||
'''if''' (f(n, c)) | '''if''' (f(n, c)) | ||
| Строка 39: | Строка 35: | ||
'''else''' | '''else''' | ||
L = c; | L = c; | ||
| − | + | } | |
A.add(L); | A.add(L); | ||
n = n / L; | n = n / L; | ||
| − | + | } | |
'''return''' A; | '''return''' A; | ||
| − | + | } | |
</code> | </code> | ||
Версия 18:57, 19 марта 2010
Формулировка задачи
Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.
Сведение задачи факторизации к языку FACTOR
Рассмотрим язык .
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа .
Пусть функция f разрешает язык FACTOR:
Тогда, воспользовавшись двоичным поиском, можно написать функцию 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
.
Сертификатом 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.
