|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Lorinets Roman 2:5020/400 04 Feb 2003 12:48:39
To : Alexander Zatvornitskiy
Subject : Re: Задача о pанце.
--------------------------------------------------------------------------------
"Alexander Zatvornitskiy"
<Alexander.Zatvornitskiy@p131.f3.n5025.z2.fidonet.org> wrote in message
news:1044317314@p131.f3.n5025.z2.ftn...
> Привет Lorinets!
>
> 03 февраля 2003 в 13:27, Lorinets Roman в своем письме к Aleksey Zelenin
писал:
> ...skipped...
> LR> рюкзак, чтобы суммарная ценность снаряжения была максимальной.
>
> LR> Есть еще в криптографии задача об укладке ранца:
> LR> Задан вектор С=|c1,c2,...,cn| который используется для шифрования
> LR> сообщения, каждый символ si которого представлен
> LR> последовательностью из n бит si=|x1,x2,...,xn|**t, Xk пp.
> LR> {0,1}. Шифртекст получается как скалярное произведение Сsi.
>
> А почему последняя так называется?
>
Последняя основана на предидущей. В первой задаче (упрощенной),
задан вектор An={a1,...an}и число b. Hужно найти такие элементы массива,
чтобы их сумма была равна b. Если массив An является неубывающим,
то решение находится легко (иначе придется перебирать2^n вариантов).
Hа основе этой задачи Мэркли и Хеллманом был разработан алгоритм
шифрования. Частью зактытого ключа является массив An.
ИМХО через 6 лет его взломали, если не ошибаюсь, авторы RSA. Причем
ключ был не равен закрытому.
--- ifmail v.2.15dev5
* Origin: Ukranian Academic Research Network (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
