Комментарии 7
В реальных условиях пpимер будет иметь, скажем, 300
Поиск среди2**300подмножеств не поддается обработке
Можно "немного" быстрее, чем 2**300 == O(2**n), а именно O(n x 2**(n/2)) по времени и O(2**(n/2)) по памяти: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle
Немного добавлю от себя. Как правильно замечено в конце статьи, для криптографических применений необходима сложность в среднем (average case hardness), а не худшем случае (worst case hardness). Задача о ранце была первой попыткой привязать сложность к NP-полноте. Сейчас эта идея получила существенное развитие в криптографии на решетках. В 2005 году Regev предложил задачу LWE (Learning with errors) и доказал, что она имеет сложность в среднем, как задача GapSVP (NP-полная задача при определенных условиях) в худшем случае. Сейчас LWE и его модификации очень широко используются в криптографии на решетках. Но есть нюанс. В зависимости от параметров одна и та же задача может лежать в разных классах сложности. Те варианты LWE, которые используются на практике, лежат в пересечении NP и coNP, но они не обладают NP-полнотой. И более того, скорей всего, построить такую криптосистему, чтобы NP-полная GapSVP сводилась к LWE, не получится. (Это не доказано, но существует множество аргументов в пользу этого). Так что вопрос "а можем ли мы построить криптосистему, сложность которой основана на NP-полной задаче?" остается открытым и пока результаты не утешительные.
… открытый ключ должен получаться из секретного ключа при помощи преобразования ( односторонней функции), обладающего следующими двумя свойствами:
* B=f(A), зная A, вычислить саму функцию легко
* A=f^(-1)(B), а вычислить обратную функцию трудно
Не обязательно. Например в RSA нельзя из приватного ключа вычислить открытый.
В более общем случае открытый и приватный ключи вычисляются вместе из некого изначального секрета. Это не значит что можно потом зная только приватный ключ вычислить открытый.
Задача о рюкзаке формулируется так
Я, конечно, извиняюсь, но это называется «Задача линейного раскроя». В задаче о рюкзаке присутствуют ещё и стоимости (весовые коэффициенты). А цель — набрать наибольшую сумму, не выходя за предел веса (причём максимальность веса — необязательна).
Да, для решения задачи линейного раскроя можно использовать методы решения задачи о рюкзаке (в просторечии, правда, это называется «из пушки по воробьям»), но нельзя наоборот. Задача линейного раскроя — она ПРОЩЕ, она — частный случай задачи о рюкзаке. Это именно задача о рюкзаке в одном частном её случае, при равных всех весовых коэффициентах, превращается в задачу линейного раскроя.
Задача о ранце в криптографии (Knapsack problem in cryptography)