Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 39

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 33 34 35 36 37 38 < 39 > 40 41 42 43 44 45 .. 311 >> Следующая

t(i + 1) = t(i)ffs(*W(mod^(modp) для i = 0,1,2,... (3.6.3)
Допустим, что кенгуру Т делает п прыжков, а потом останавливается. Требуется определить, сколько прыжков должен сделать кенгуру Т, чтобы поймать кенгуру W. После п-го прыжка счетчик пути, пройденного кенгуру Г, показывает величину
п
d(n) = J^e(t(i)(mod J)).
i=0
Используя это значение, мы можем переписать выражение (3.6.3) для следов кенгуру Т в следующем виде.
t(n) = 96+d("-1)(modp).
110
Часть II. Математические основы
Кенгуру W начинает свой путь из неизвестной точки гио = ^(modp). Этой неизвестной точкой является число х, и именно поэтому кенгуру W считается диким. Его путь описывается следующей формулой.
w{j + 1) = w(j)5s(,j;(i)(modJ»(modр) для J = 0,1,2,... (3.6.4)
Счетчик пути, пройденного кенгуру W, регистрирует величину
з
к=0
Аналогично выражению (3.6.3) выражение (3.6.4) для следов кенгуру W можно переписать в следующем виде.
w(j) = ^^-^(modp).
Очевидно, что следы обоих кенгуру, t(i) и w(j), представляют собой случайные функции. Первая из этих функций задается в точках г, а вторая — в точках j. Согласно парадоксу дней рождений после пту/Ь — а прыжков, сделанных кенгуру ThW соответственно, при некоторых значениях ? ^ п и -п ^ п должна произойти коллизия t(?) = w(rf). Именно в этот момент кенгуру Г и W встретятся в одной точке, т.е. кенгуру W попадет в капкан, установленный кенгуру Т. Итак, кенгуру W пойман. Если количество случайных прыжков, сделанных обоими кенгуру, превышает \/Ь — а, вероятность коллизии быстро стремится к единице.
В соответствии с формулами (3.6.3) и (3.6.4), когда возникает коллизия *(?) = = w{rj), выполняются равенства i(f + 1) = w(i] + l),i(f + 2) = w(i] + 2),... и т.д. Иначе говоря, при некоторых числах п « m в конце концов будет выполнено равенство w[m) = t(n). Поскольку после встречи оба кенгуру продолжают прыгать по одному и тому же пути, ведущему к равенству w(m) = t(n), коллизию t(?) = w(7]) можно интерпретировать как точку, в которой пересекаются две палочки греческой буквы Л (напомним, что кенгуру Г выполняет фиксированное количество прыжков п). По этой причине алгоритм получил название "Л-метод".
После возникновения коллизии выполняется равенство
дх = gb+d{n-l)-D(m~l){modp)
Отсюда следует, что
x = b + d(n-l)- D{m - 1).
Поскольку оба счетчика показывают величины d(m — 1) и D{n — 1) соответственно, величину х можно вычислить, используя длину пути, пройденного каждым кенгуру. При этом возможна ситуация, когда оба кенгуру пройдут слишком длинный путь до встречи, и поэтому искомая величина индекса может оказаться
Глава 3. Теория вероятностей и теория информации
111
равной х + о, где число о удовлетворяет равенству g°modp — 1. В этом случае можно считать, что, что ответом задачи является величина х + о.
Следует отметить, что описанный алгоритм является вероятностным (probabilistic), т.е. он может не обнаружить коллизию (иначе говоря, вычислить искомую величину индекса). Несмотря на это, благодаря высокой вероятности обнаружить коллизию вероятность отказа можно сделать достаточно малой. Смещая стартовую точку кенгуру W на известную величину 5 и повторяя алгоритм, после нескольких итераций мы обязательно обнаружим коллизию.
Условием, обеспечивающим практическую целесообразность А-алгоритма, является относительная малость величины \/6 — а. Следовательно, при п = л/Ь — а (где п — количество прыжков, сделанных кенгуру Т) алгоритм выполняется за время, которое необходимо для вычислений \/Ъ — а операций возведения в степень по модулю. Требования к памяти компьютера тривиальны: необходимо хранить лишь J = |k)g(6 — a) J элементов. Временное ограничение, равное у/Ь — а, означает, что данный алгоритм нельзя применять для вычисления больших индексов. Как образно сказал Поллард, кенгуру не может проскакать через весь континент.
В соответствии с определением, данным Шенноном (Shannon) в работах [262, 263], энтропия (entropy) источника сообщения представляет собой меру объема информации, содержащейся в источнике. Эта мера принимает вид функции распределения вероятностей во множестве сообщений, которые может порождать источник.
Пусть L = {oi, 02,..., ап} — язык, состоящий из п разных символов. Предположим, что источник S может порождать эти символы с независимыми вероятностями
3.7 Теория информации
Prob[ai], РгоЬ[аг],..., Prob[an],
причем эти вероятности удовлетворяют условию
п
(3.7.1)
г=1
Энтропия источника S равна
(3.7.2)
Функция энтропии H(S), определенная формулой (3.7.2), выражает величину, которую можно назвать "средним количеством бит в сообщении, порожденном источником".
112
Часть II. Математические основы
Понятие энтропии можно проиллюстрировать следующим примером. Представим себе, что источник S не имеет памяти, поэтому мы должны записывать все символы, которые он порождает. Естественным решением было бы просто записывать все символы, порождаемые источником S. Однако в соответствии с формулой (3.7.1) источник S может порождать символы а\, а,2,.-.,апс известными вероятностями. Было бы неинтересно и неэффективно просто записывать все подряд. Итак, вопрос заключается в следующем: как эффективно записать сообщение источника S, представляющее какой-либо интерес?
Предыдущая << 1 .. 33 34 35 36 37 38 < 39 > 40 41 42 43 44 45 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed