Глава 14
Задача о рюкзаке
Задача
Имеется набор предметов, k шт. Каждый предмет имеет какой-то объём vi. Имеется ёмкость – рюкзак объёма V .
Как по объёму V определить состав упакованных предметов?
Диофантовы трудности
Диофантовы уравнения имеют следующий вид:
aixi = A,
i = 0, . . . k − 1
(14.1)
где ai и A – известны.
Общая постановка задачи о рюкзаке
Пусть задано множество {vi}, содержащее k натуральных чисел, и число V . Требуется найти такое k-разрядное
k−1
двоичное число n = {εk−1, εk−2, . . . , ε0} что n=0 εivi = V . При решении задачи возникают три случая:
· для конкретного набора vi, V решение отсутствует
· решение есть, но оно не единственно
· существует единственное решение
Задача о рюкзаке относится к N P -полным задачам (т.е. не существует полиномиального алгоритма её решения).
Она заложила основу криптосистем рюкзачного типа.
Задача о быстро растущем рюкзаке
Отличие от исходной задачи состоит в том, что задаётся v0 и известно, что vi > vi−1 +vi−2 +. . .+v0,
i = 1, . . . , k−1.
Пример. {2, 3, 7, 15, 31}.
Существует полиномиальный алгоритм решения этой задачи.
Алгоритм решения задачи о быстро растущем рюкзаке
Имеется быстрорастущий набор {vi}, V → {εk−1, . . . , ε0}, причём εi ∈ {0; 1}.
1. Пусть W – промежуточная переменная, ей присваивается значение V .
2. j – промежуточная переменная, ей присваивается значение k. Начиная с εj−1, последовательно уменьшаем j и
проверяем условие:
vj ≤ W
(14.2)
Если условие выполняется, то соответствующее значение εj = 1 и осуществляется переход на шаг 3, иначе εj = 0
и осуществляется переход на шаг 2.
3. W присваивается значение W − vj , затем переход на шаг 2.
Последовательность действий выполняется до тех пор, пока W не станет равным нулю.
Пример. {2, 3, 7, 15, 31},
V = 24.
{0, 1, 1, 0, 1}
24 − 15 = 9
9 − 7=2
2 − 2=0
Частный случай рюкзака
Легальный пользователь
Общая задача рюкзака
Нарушитель
14. Задача о рюкзаке
Система Меркля-Хеллмана
Алгоритм генерации быстрорастущего рюкзака {v0, . . . , vk−1}.
1. Создаётся k случайных чисел zi
2. Упорядочиваются в порядке возрастания {zi}i=0...k−1, zi ≤ zi−1
3. v0 = z0,
vi = zi + vi−1 + vi−2 . . . + v0
Рассмотрим криптосистему, основанную на этом алгоритме:
1. Создаётся случайный быстрорастущий набор {vi}
2. Определяется целое число m такое, что m >
3. Создаётся a, взаимно простое с m, 0 ≤ a ≤ m
4. Вычисляется b = a−1 (mod m) (b · a ≡ 1 (mod m))
5. На основании созданного быстрорастущего набора и значения a создаётся ещё один рюкзачный набор wi =
a · vi (mod m)
6. a, b, m, {vi} – секрет. {wi} – открытый ключ.
Расшифрование
{εk−1, εk−2, . . . , ε0},
εiwi = C
bC (mod m) = b
εiwi (mod m) =
εibwi (mod m) =
εivi (mod m)
Пример. {2, 3, 7, 15, 31} = {vi}. m = 61, 31 + 15 + 7 + 3 + 2 = 58. a = 17 ⇒ b = 18.
Зашифруем слово из трёх букв:
W HY = (10110)(00111)(11000)
(14.3)
Каждой букве поставим в соответствие число – номер буквы в алфавите.
Зашифрование произведём следующим образом: {wi} = 34, 51, 58, 11, 39 для одной буквы. W = 34 + 58 + 39 = 148.
Расшифрование: 148 · 18 (mod 61) = 41. Получаем (10110).
В 1983 г. Эди Шамир предложил алгоритм решения задачи расшифрования за полиномиальное время. Существуют
также LLL-алгоритмы(или L3-алгоритмы). Их модификация не взломана до сих пор.
53
vi