Студопедия — Модулярная арифметика
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 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 -длина числа в битах.

Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю п, целесообразно использовать алгоритмы быстрого возведения в степень.







Дата добавления: 2015-10-15; просмотров: 1018. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Оценка качества Анализ документации. Имеющийся рецепт, паспорт письменного контроля и номер лекарственной формы соответствуют друг другу. Ингредиенты совместимы, расчеты сделаны верно, паспорт письменного контроля выписан верно. Правильность упаковки и оформления....

БИОХИМИЯ ТКАНЕЙ ЗУБА В составе зуба выделяют минерализованные и неминерализованные ткани...

Типология суицида. Феномен суицида (самоубийство или попытка самоубийства) чаще всего связывается с представлением о психологическом кризисе личности...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия