vlsergey/infosec — pull request #2351 by goriand (2014-12-27 08:53:42+00:00)
Title: Update Information Security.tex

Класс NP - задачи распознавания. То есть алгоритм выдает только 1 бит информации (да или нет). Задачи же факторизации и дискретного логарифмирования, применяющиеся в криптографии требуют не только ответа в один бит, но и само разложение числа на множители или нахождение дискретного логарифма. Поэтому их нельзя относить к классам задач распознавания.
См. https://en.wikipedia.org/wiki/Function_problem https://en.wikipedia.org/wiki/FNP_(complexity)