Книга Кому нужна математика? Понятная книга о том, как устроен цифровой мир, страница 37. Автор книги Нелли Литвак, Андрей Райгородский

Разделитель для чтения книг в онлайн библиотеке

Онлайн книга «Кому нужна математика? Понятная книга о том, как устроен цифровой мир»

Cтраница 37

Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Это так называемый двойной экспоненциальный закон. Двойка в формуле, та самая двойка – вторая степень – из выражения (П.10). Точно так же мы могли бы выбирать не из двух, а из r серверов и получили бы


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Интересно заметить, что при тех же предположениях, но случайном выборе одного сервера, изменятся выражения (П.10) и, соответственно, (П.11). Действительно, на этот раз заявка выбирает только один сервер и вероятность попасть на сервер с k или больше заявками равна просто иk. Тогда вместо (П.12) получаем классическое уравнение баланса:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

решение которого задается известной формулой Эрланга:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Очевидно, что иk в формуле (П.13) убывает гораздо быстрее.

Именно эти формулы мы использовали в табл. 5.1 . В нашем случае λ = 0,9, и в таблице мы привели значения fk. В первой колонке – значения k, во второй – значения fk, подсчитанные по формуле (П.14), в третьей – значения fk, подсчитанные по формуле (П.13).

Назад к Главе 5

Приложения к главе 6

1. Схема Диффи – Хеллмана

Для начала введем обозначения. Пусть р – заданное простое число, g – заданное натуральное число, g < p. На самом деле g это так называемый первообразный корень числа р. Об этом мы расскажем ниже, в приложении 2 и приложении 3 к главе 6. Цель данного раздела – доказать, что в схеме Диффи – Хеллмана Алиса и Боб действительно получают один и тот же ключ.

Для любых натуральных чисел n и р мы воспользуемся стандартным обозначением для остатка от деления n на р:


n(mod p) = [остаток от деления n на p].


(Читается «n по модулю p».)

Итак, Алиса задумала число х, а Боб число у. Схема Диффи – Хеллмана состоит из двух шагов.


Шаг 1. Алиса передает Бобу


a = (gx) (mod p).


Боб передает Алисе


b = (gy) (mod p).


Шаг 2. Алиса вычисляет ключ


KA = (bx) (mod p).


Боб вычисляет ключ


KB = (ay) (mod p).


Утверждение. Боб и Алиса получили один и тот же ключ K = KA = KB.

Доказательство. Нам нужно доказать, что KA = KB. Поскольку а и b – это остатки от деления на р, то существуют такие целые числа k и l, при которых


a = gx kp, b = gy lp.


Подставив эти выражения в формулы для ключей, получаем:


KA = (gy lp)x (mod p),

KB = (gx kp)y (mod p).


Заметим, что в выражении для KA можно расписать (gylp)x следующим образом:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

где А – это целое число, то есть рА делится на р. Таким образом получаем


KA = ((gy lp)x) (mod p) = ((gy)x + pA) (mod p) = (gy)x (mod p).


Совершенно аналогично для какого-то целого числа B получаем


KB = ((gx kp)y) (mod p) = ((gx)y + pB) (mod p) = (gx)y (mod p).


Результат теперь очевиден, поскольку


(gy)x = gyx = gxy = (gx)y.

2. Дискретное логарифмирование

Вспомним, что логарифм числа у по основанию g – это такое число х, для которого выполняется


gx = y.


Легко заметить, что очень похожая операция лежит в основе схемы Диффи – Хеллмана.

После возведения в степень мы берем остаток от деления на р. Как мы уже упоминали выше, в математике такая операция обозначается gx (mod p) (читается «g в степени х по модулю р»). При этом, естественно, g и х натуральные числа и у g нет общих делителей с р.

Вход
Поиск по сайту
Ищем:
Календарь
Навигация