Модулярная арифметикаМодулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня 3 + 14=5(mod12) или (3+14) mod 12 = 5 Это арифметика по модулю 12 Обычная запись в модулярной арифметике а º b(mod n) читается так " а сравнимо с b по модулю n " Это соотношение справедливо для целых значении a b и n и n¹0, если и только если а = b + k´n для некоторого целого k Отсюда, в частности, следует n|(a-b) Это читается как n делит (a-b) Если а º b(mod n) то b называют вычетом числа а по модулю n. Операцию нахождения вычета числа а по модулю n a(mod n) называют приведением числа а по модулю n или приведением по модулю. В нашем примере (3+14) mod 12 = 17 mod 12 =5 или 17º5(mod l2), число 5 является вычетом числа 17 по модулю 12. Набор целых чисел от 0 до (n -1) называют полным набором вычетов по модулю n. Это означает что для любого целого а (а>0) его вычет r по модулю n, есть некоторое целое число в интервале от 0 до (n -1) определяемое из соотношения r = a+ k´n, где k - целое число. Например, для n = 12 полный набор вычетов {0,1,2 11} Обычно предпочитают использовать вычеты rÎ{0,1,2 n-1}, но иногда полезны вычеты в диапазоне целых
Заметим что -12(mod 7) º-5(mod 7) º 2(mod 7) º 9(mod 7) и т.д. Модулярная арифметика аналогична во многом обычной арифметике, она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операции сложения и умножения, образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности. Фактически мы можем либо сначала приводить по модулю n, а затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n. (а + b) mod n = [a(mod n) + D(mod n)] mod n (a - b) mod n = [a(mod n) - D(mod n)] mod n (a ´ b) mod n = [a(mod n) ´ b(mod n)] mod n [a ´ (b + c)] mod n = {[a ´ b(mod n)] + [a ´ c(mod n)]} mod n Криптография использует множество вычислений по модулю n, потому что задачи, типа вычисления дискретных логарифмов и квадратных корней, очень трудны. Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2k бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов. Вычисление степени числа а по модулю n ах mod n можно выполнить как ряд умножений и делений. Существуют способы сделать это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более). Например, если нужно вычислить a8 mod п, не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа (а´а´а´а´а´а´а´а) mod п Вместо этого выполняют три малых умножения и три малых приведения по модулю. ((a2 mod п)2 mod п)2 mod n Тем же способом вычисляют a16 mod n= (((a2 mod n)2 mod n2 mod n)2 mod n Вычисление аx mod n, где х не является степенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2. х = 25 (10)®1 1 0 0 1(2), поэтому 25 = 24 + 23 + 20 Тогда a25 mod n = (а´a24) mod п=(а´а8´а16) mod п = = а´((а2)2)2 ´(((a2)2}2)2 mod n - ((((а2 * а)2)2)2´a) mod n. При разумном накоплении промежуточных результатов потребуется только шесть умножений: (((((((a2 mod n)´a) mod n)2 mod n)2 mod n)2 mod п)´a) mod п. Этот метод уменьшает трудоемкость вычислении до 1,5хk операций в среднем, где k -длина числа в битах. Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю п, целесообразно использовать алгоритмы быстрого возведения в степень.
|
