ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Обратные значения по модулю

Теоретическая часть

Модулярная арифметика

В общем случае, , если при некотором целом k. Если а неотрицательно, а b находится между 0 и п, можно рассматривать b как остаток от деления а на п. Иногда b называетсявычетом по модулю п, а иногда называют сравнимымс b по модулю п (знак тождества, , обозначает сравнимость). Это просто разные способы записать одно и то же.

Модулярная арифметика во многом подобна обычной арифметике. Так, она тоже коммутативна, ассоциативна и дистрибутивна. Кроме того, приведение каждого промежуточного результата по модулю п дает такой же результат, что и выполнение всего вычисления с последующим приведением конечного результата по модулю n:

;

Модулярные вычисления нашли широкое применение в криптографии, поскольку вычисление дискретных логарифмов и квадратных корней по модулю п может оказаться нелегкой задачей. К тому же, модулярную арифметику проще реализовать на компьютерах, так как она ограничивает диапазон промежуточных значений и результата. Для k-битовых модулей п длина промежуточных результатов любой операции сложения, вычитания или умножения не превышает 2k бит. Поэтому с помощью модулярной арифметики можно выполнить возведение в степень без огромных промежуточных результатов.

Вычисление степени некоторого числа по модулю другого числа

представляет собой простую последовательность операций умножения и деления, однако известны методы их ускорения. Поскольку операции дистрибутивны, возведение в степень выполняется быстрее как поток последовательных умножений, каждый раз получая вычеты. Например, вычисляя 8 mod n, нет необходимости выполнять семь умножений и одно огромное приведение по модулю: (а*а*а*а*а*а*а*а) mod n. Вместо этого можно выполнить три меньших умножения и три меньших приведения по модулю:

((a² mod n)² mod n)² mod n.

Вычисление , где х не является степенью 2, несколько сложнее. Двоичная запись позволяет представить х в виде суммы степеней числа 2. Так, число 25 в двоичной системе счисления записывается как 11001, так что 25 =2⁴ + 2³ + 2°. Поэтому

что при разумном сохранении промежуточных результатов требует всего шести операций умножения:

Этот прием называютаддитивной цепочкой (addition chain), или методом двоичных квадратов и умножений. Алгоритм для расчета выглядит следующим образом

Обратные значения по модулю

В обычной арифметике обратное значение числа 4 равно 1/4, поскольку 4*1/4=1. В модулярной арифметике это понятие несколько сложнее:

Это уравнение эквивалентно поиску таких значений x и k,что

где x и k – целые числа.

Общая задача состоит в определении такого значения x, что

Последнее равенство можно записать в виде

Задача вычисления обратных значений по модулю немного труднее обычной. Иногда у нее есть решение, иногда - нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14. В общем случае, уравнение имеет единственное решение, если а и п взаимно просты.

Для поиска обратного значения по модулю п можно воспользоваться следующим алгоритмом, который получил название расширенного алгоритма Евклида.