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

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

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

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

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

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

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

Приложения к главе 61. Схема Диффи – Хеллмана

Для начала введем обозначения. Пусть р – заданное простое число, 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 можно расписать (gy − lp)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 нет общих делителей с р.