15
правок
Изменения
Нет описания правки
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.
Используя его в качестве оракула, можно за полиномиальное время найти нетривиальные простые делители числа <math>n</math>.
Пусть функция '''f''' разрешает язык '''FACTOR''':
</math>
Тогда можно написать функцию '''p''', работающую не медленнее, чем за полином, от длины входа и возвращающую список ''A'' нетривиальных простых делителей '''n''':
<code>
p(n)
n' = n;
A = {};
'''forwhile'''(n' > 1) { '''if''' (!f(n', n')) { A.add(b n'); n' = 21; '''break'''; b < } r = n / '; l = 2; b++) // '''while'b - текущий простой делитель''(r > l + 1) { c = (l + r) / 2; '''whileif''' (f(n', b + 1c)) r = c; {'''else''' n' / l = bc; } A.add(bl); } n' = n' / l; }
'''return''' A;
}
