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

Поскольку заявок в единицу времени поступает λ п, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на

Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:

Результат, приведенный в работе {34}, говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:

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

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

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

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

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

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

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

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

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

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

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

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

a = ( g x ) (mod p ).

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

b = ( g y ) (mod p ).

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

K A = ( b x ) (mod p ).

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

K B = ( a y ) (mod p ).

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

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

a = g x − kp, b = g y − lp .

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

K A = ( g y − lp ) x (mod p ),