%
Алгоритм Рюкзака

Меню сайта

Статистика
Рейтинг@Mail.ru Яндекс.Метрика

Варианты рюкзака

 После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографических методов.

Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.

  1. Рюкзак 0-1 (0-1 Knapsack Problem) : не более одного экземпляра каждого предмета
  2. Ограниченный рюкзак (Bounded Knapsack Problem) : не более заданного числа экземпляров каждого предмета
  3. Неограниченный рюкзак (целочисленный рюкзак)(Unbounded Knapsack Problem (integer knapsack)) : произвольное количество экземпляров каждого предмета
  4. Рюкзак с мультивыбором (Multiple-choice Knapsack Problem)
  5. Мультипликативный рюкзак (Multiple Knapsack Problem) : есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
  6. Многомерный рюкзак (Multy-dimensional knapsack problem) : вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна.

 Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны. Криптосистема Lu-Lee была взломана, ее модификация также оказалась небезопасной. Вскрытия. Криптосистема Pieprzyk была взломана аналогичным образом.

 Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest, несмотря на "специализированное вскрытие" - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен. Более того, учитывая легкость с которой пали все остальные варианты, доверять устоявшим пока вариантом, по видимому, неосторожно.

 
Назад Домой Вперед
Друзья сайта
  • Группа AR в ВК.
  • Группа AR в FB.
  • Группа AR в OK.
  • Алгебра Логики.
  • Альтернатива Групп.

  • Алгоритм Рюкзака © 2017 created AD.