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