В криптографии существуют шифры и по простому модулю и по составному модулю.
Нужно знать когда применять простой модуль, а когда составной и какие ограничения надо вводить, чтобы расшифровка проводилась однозначно Свойства состоят из трех групп:
I) Свойства, определяемые отношением эквивалентности
1) Рефлективность
a ≡ a mod m
2) Симметричность
a ≡ b mod m, a mod b ≡ m
a j( m ) mod m ≡ 1
a j( m ) ≡ 1 mod m
3) Транзитивность
Имеем 3 натуральных числа. Рассмотрим условие: Если a ≡ b mod m и b mod c ≡ m, то a ≡ с mod m
II) Свойства сравнимости по модулю 2 аналогичны свойствам равенства
1) Если
a1 ≡ b1
mod m и
a1 ≡ b2
mod m, то ( a1 + a2 )=(
b1 +b2 ) mod m
2) Если
a1 ≡ b1
mod m и
a2 ≡ b2
mod m, то ( a1 * a2 )=(
b1 * b2
mod m
3) Если a ≡ b mod m, (k,m)=1, тогда
ak = bm
mod m
4) Если a ≡ b mod m, тогда
Справедливо и обратное
a k ≡ bk mod m, где k- натуральное.
III) Свойства, отличающихся от свойств равенства
5) Имеем a, b – числа, m – модуль
(a,b) ≡ d – наибольший общий делитель
(d,m) ≡ 1, a ≡ b mod m, тогда a/d ≡ b/d mod m
Пример
45 ≡ 27 mod 6
45/9 ≡ 27/9 mod 6
5 ≡ 3 mod 6, поэтому числа 9 и 6 не взаимнопросты
6) b*a ≡ b mod m, d –такое что a/d, b/d, m/d a/d ≡ b/d mod (m/d)
7) (a+b) mod m ≡ [a mod m + b mod m] mod m
8) a*b mod m ≡ [(a mod m)*(b mod m)] mod m
На основе этих свойств можно достаточно просто доказать теорему Эйлера в общем виде.