|
Но Диффи и Хеллман не интересовались двусторонними функциями. Они обратили свое внимание на односторонние функции. Как следует из названия, одностороннюю функцию легко вычислить в прямом направлении, но очень сложно в обратном. Другими словами, двусторонние функции обратимы, а односторонние функции необратимы. И опять-таки самый простой способ показать, что такое односторонняя функция, — это рассмотреть ее на примере повседневной деятельности. Смешивание желтой и синей красок для получения зеленой краски является односторонней функцией, поскольку краски смешать несложно, но вот разделить их после этого снова на исходные невозможно. Односторонней функцией также будет разбивание яйца: разбить яйцо легко, но вернуть его в исходное состояние уже невозможно. Из-за этого односторонние функции иногда называются функциями Шалтай-Болтая. Модулярная арифметика , иногда в школе называемая арифметикой, оперирующей с абсолютными значениями чисел , является разделом математики, который богат односторонними функциями. В модулярной арифметике математики имею дело с циклически замкнутыми конечными группами чисел, подобно числам на циферблате часов. Например, на рис. 64 показан циферблат часов с модулем 7, на котором имеется только 7 цифр от 0 до 6. Чтобы вычислить 2 + 3 по модулю 7 (или mod 7), мы возьмем в качестве отправной точки 2 и передвинемся на 3 позиции, получив в результате 5, то есть получим тот же самый ответ, что и в обычной арифметике. Чтобы вычислить 2 + 6 по модулю 7, мы возьмем в качестве начальной точки 2 и передвинемся на 6 позиций, но на сей раз мы обойдем весь циферблат и окажемся на 1, а это уже не тот результат, который мы получили бы в обычной арифметике. Эти результаты могут быть выражены в следующем виде: 2 + 3 = 5 (mod 7) и 2 + 6 = 1 (mod 7) Модулярная арифметика сравнительно проста, и на самом деле мы пользуемся ею ежедневно, когда говорим о времени. Если сейчас 9 часов, а у нас назначена встреча, которая состоится через 8 часов, мы скажем, что встреча произойдет в 5, а не в 17 часов. Мы в уме сосчитали 9 + 8 по (mod 12). Представьте себе, циферблат часов, посмотрите на 9, а затем отсчитайте 8 делений, и вы остановитесь на 5: 9 + 8 = 5 (mod 12) Математики, вместо того чтобы представлять себе циферблаты на часах, часто выбирают кратчайший путь, выполняя модулярные вычисления следующим образом. Вначале вычисление проводится по правилам обычной арифметики. Затем, если мы хотим узнать ответ по (mod x ), мы делим результат, полученный на предыдущем этапе, на x и записываем остаток. Этот остаток и является ответом по (mod x ). Чтобы найти ответ в примере 11 x 9 (mod 13), мы поступим следующим образом: — 188 —
|