|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 04 Mar 2003 14:35:08
To : Sergey Kabikov
Subject : Хеш-функция с контролируемыми коллизиями
--------------------------------------------------------------------------------
Replying to a message of Sergey Kabikov to All:
SK> Hеобходимо построить функцию, y = f(x), где
SK> 0 <= x < 2^nx
SK> 0 <= y < 2^ny
SK> ny < nx
SK> Т.е. мощность множества значений результата меньше мощности множества
SK> значений аргумента, т.н. функцию с коллизиями.
SK> Основное требование к ней : для любого х, принадлежащего некоему
SK> заранее заданному множеству {x0}, результат функции должен быть некой
SK> величиной у0, а для любого х, не принадлежащего этому множеству -
SK> величиной, отличной от у0.
SK> Дополнительное требование : по виду самой функции должно быть
SK> невозможно определить правильные у0 и {x0}, т.е. должно существовать
SK> множество приблизительно равномощных пар yi и {xi}, в идеале 2^(nx -
SK> ny) таких пар. Поэтому типовой ответ
SK> if x in {x0}
SK> then y := y0
SK> else y := random(2^ny)
SK> не проходит.
В случае, когда |{x0}|/2^nx достаточно мало, а 2^ny достаточно велико очень даже
проходит. Вероятность получить y = yi для любого 0<=yi<2^ny, yi<>y0 примерно
равна (2^nx-|{x0}|)/2^ny ~= 2^(nx-ny).
И даже сильное отличие вероятности появления y0 смущать не должно, коль скоро ny
выбрано достаточно большим для невозможности осуществления статистического
анализа.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
