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

Меню сайта

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

Практические реализации

Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовательность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов. Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов. Для получения этих значений практические реализации используют генераторы случайной последовательности.

Вскрывать подобные рюкзаки при помощи грубой силы бесполезно. Если компьютер может проверять миллион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10 лет. Даже миллион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую звезду.

Безопасность метода рюкзака

Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов. Сначала был раскрыт единственный бит открытого текста. Затем Шамир показал, что в определенных обстоятельствах рюкзак может быть взломан. Были и другие достижения - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel), обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II.

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

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