Развитие квантовых компьютеров ставит под угрозу множество распространенных на данный момент криптосистем, основанных на задачах факторизации, дискретного логарифмирования и других, которые могут быть решены за полиномиальное время на квантовом компьютере.
Однако на данный момент не предложено алгоритмов, позволяющих за полиномиальное время решать NP-полные задачи квантовыми компьютерами. Мы рассматриваем две криптосистемы с открытым ключом, основанные на NP-полных задачах о сумме подмножеств и целочисленного программирования.
The development of quantum computers endangers the great number modern cryptosystems based on factorization problem, discrete logarithm problem and other, which can be solved in polynomial time on a quantum computer. However, quantum computing algorithms can't efficiently solve NP-hard problems at present. In this paper, we consider two public key cryptosystems based on NP-hard problems: subset sum and integer programming.