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

В основу модулярной арифметики положена операция «деление по модулю», которая дает возможность бесконечное множество целых чисел отобразить в конечное множество классов эквивалентности (классов вычетов по модулю). Модулярная арифметика нашла широкое применение в криптографии.

Определение При заданных целых числах x,и n> 0 операция x (mod n) «деление по модулю» возвращает r – остаток от деления числа x на число n ( и удовлетворяет условию x= k n + r, где k – целое число).

Теорема (свойства операции «деление по модулю»)

Пусть x, y и n > 0 – целые числа, причем НОД (y, n) = 1 (НОД – наибольший общий делитель; если НОД (y, n) = 1, то y и n называют взаимно простыми числами).

1. (x + y) mod n = [(x) mod n + (y) mod n] (mod n).

2. (– x) mod n = (n – x) mod n = n – (x mod n).

3. (x x y) mod n = [(x) mod n x (y) mod n] (mod n).

4. Обозначим через y^-1 mod n величину, обратную к y по модулю n. Она является единственным числом из интервала [1,n –1], удовлетворяющем условию (y^-1 x y)mod n = 1.

Как и при делении рациональных чисел, деление чисел по модулю можно заменить на умножение делимого на число обратное делителю (если оно существует). Для любого y, если НОД (y, n) = 1, выражение (x x y^-1) mod n можно заменить на (x / y) mod n.

Замечание В операции «деление по модулю» x mod n величина k не важна. Следовательно в тождестве x mod n = y mod n числа x и y могут отличаться на величину, кратную n. Тогда это уравнение можно записать так x ≡ y mod n или y ≡ x mod n. Эта операция называется сравнение чисел по модулю, а числа x и y называют сравнимыми по модулю.

Анализ приведенных выше свойств свидетельствует о том, что модулярная арифметика очень похожа на целочисленную. Операции сложение по модулю и умножение по модулю:

а) коммутативны (перестановка операндов не меняет результата);

б) ассоциативны (изменение последовательности выполнения операций результата не меняет).

Поиск по сайту: