NP-полная задача


Математическая проблема, сложность которой растёт экспоненциально (суперэкспоненциально) и которая не поддаётся решению за полиномиальное время. Надёжность асимметричной криптографии основана на NP-полных задачах. В настоящее время в основном используется две: проблема дискретного логарифмирования в конечном поле и проблема разложения на множители больших чисел. Если какая-либо из них станет решаема за полиномиальное время, соответствующие криптосистемы потеряют свою нынешнюю стойкость.