Математические основы криптологии. Галуев Г.А. - 15 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

29
чем
к простых чисел. Далее была доказана теорема (Виноградов
И.М.), утверждающая что всякое достаточно большое нечетное
число представимо в виде суммы трех простых чисел.
Утверждение о представлении четных чисел в виде суммы
двух простых чисел до сегодняшнего дня не доказано.
Продолжим знакомство с основными понятиями и теоре-
мами теории чисел, которые
будут необходимы для дальнейше-
го изложения лекционного курса.
Пусть
m
∈
N - натуральные числа.
Целые числа
а и b (a,b
∈
z) называются сравнимыми по мо-
дулю
m
∈
N (m
≠
0) если разность a и b делится на m т.е. m/a-b.
Сравнимость чисел
a и b по модулю m обозначают симво-
лом
),(mo
d
mba ≡
называемым сравнением по модулю m.
Числа
a и b сравнимы по модулю m тогда и только тогда,
когда существует целое
t(t
∈
z) такое, что
,m
t
ba
+
=
также и
только тогда, когда они имеют одинаковые остатки при делении
на
m т.е.
12
; .amq r bmq r=+ =+
Отсюда следует, что все целые числа Z по модулю m раз-
биваются по
m непересекающихся классов сравнимых между
собой чисел (т.е. имеющих одинаковые остатки при делении на
m)
Каждое число
b, входящее в какой - либо из классов, назы-
вается
вычетом числа a по модулю m, а каждый класс - классом
вычетов по модулю m. Число разных классов вычетов равно m.
Полной системой вычетов (по модулю
m) называют мно-
жество из
m целых чисел {
m
rr ,...,
1
}, если для любого целого
числа
a существует точно одно число
),...,1 ( mir
i
=
из мно-
жества
},...,{
1 m
rr такое, что
)(mod mra
i
=
.
Пример
: множество {0,1,2,…m -1}
Сравнимость по модулю
m для произвольных целых, чисел
является отношением эквивалентности, (т.е. классы вычетов по
модулю
m являются классами эквивалентности) т.к. для них
30
справедливо выполнение соотношений:
(mod )
(mod ) (mod )
(mod ), (mod ) (mod )
a a m ðåô ëåêñèâí î ñò ü
ab m ba m ñèììåòðè÷íîñòü
ab m bc m ac m
òðàíçèòèâíîñòü
≡
−
≡→≡−
≡≡→≡
−
Свойства сравнений по модулю
m напоминают свойства
обычных числовых равенств:
1. Два числа, сравнимые с третьим, сравнимыми между
собой
2. Сравнения по одному и тому - же модулю можно по-
членно складывать:
)(mod)](mod)(mod[)(mod
2121
mmamamaa
⋅
+
=
+
3.
Сравнения по одному и тому - же модулю можно по-
членно перемножать:
)(mod)](mod)(mod[)(mod
2121
mmamamaa
⋅
⋅
⋅
Правила сокращения сравнений несколько отличаются от
правил сокращения неравенств.
4.
Если
)(mo
d
, 1), () (mo
d
mV
U
тоmaиmaVaU
≡
=
≡
(mod ), (mod ).
Å
ñëè aU aV am ò î U V m
=
≡
Для каждого целого числа
m, m>1 ввести числовую функ-
цию
ϕ
(m), представляющую собой количество чисел из сово-
купности чисел
0,1,…,m -1 взаимно простых с m. Функцию
ϕ
(m) называют функцией Эйлера. Например:
ϕ
(2)=1,
ϕ
(3)=2,
ϕ
(4)=2,
ϕ
(5)=4,
ϕ
(6)=2 и т.д.
Очевидно, что если
m=p - простое число, то
ϕ
(p)=p-1. На-
звание функции
ϕ
(m) происходит из следующей теоремы Эй-
лера: Для любых целых чисел а и m, таких, что (a,m)=1 (т.е. a и
m взаимно простые числа) справедливо выражение
).(mod1
)(
ma
m
≡
ϕ
Из теоремы Эйлера следует малая
теорема Ферма: Если р

Страницы