Математика. Часть 1. Алгебра и аналитическая геометрия. Красильщик И.С - 93 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

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

Рубрика: 

92 §19. Кольцо целых чисел
Пара чисел (n, e) объявля ется открытым ключом и помещается в открытый
каталог, а число d является секретным.
Если абонент A хочет послать сообще ние t (натуральное число) або нен-
ту B, то он выбирает из открытого каталога абонента B пару (n, e) и вычис-
ляет шифрованное сообщение
s = остаток от де ления t
e
на n,
а аб о не нт B, получив это сообщ ение, вычисляет t по формуле
t = остаток от деле ния s
d
на n.
Чем больше числа p и q, тем сложнее расшифровать код (т.е. найти число d).
Определение 14. П усть m и n — целые числа.
1. Наибольшим общим делителем (НОД) чисел m и n называется та-
кой общий положительный делитель
5
этих чисел, на который делится
любой другой их общий делитель.
2. Числа m и n называются взаимно простыми, если их НОД равен еди-
нице.
3. Наименьшим общим кратным (НОК) чисел m и n называется такое
общее положительное кратное этих чисел, кот о рое делит любое другое
общее кратное этих чисел.
Предложение 3. У любых двух ненулевых целых чисел существуют и
единственны НОД и НОК.
Нахождение НОД и НОК. Чтобы найти Н ОД и НОК чисел m и n, нуж-
но:
1) найти разложение (3) для чисел m и n.
2) записать числа m и n в виде m = p
i
1
1
p
i
2
2
. . . p
i
k
k
, n = p
j
1
1
p
j
2
2
. . . p
j
k
k
. Если
какое- нибудь из чисел p
α
не является делителем m или n, то соответ-
ствующий показатель степени равен нулю;
3) взять числа l
α
= min(i
α
, j
α
). Тогда НОД = p
l
1
1
p
l
2
2
. . . p
l
k
k
;
4) взять числа s
α
= max(i
α
, j
α
). Тогда НОК = p
s
1
1
p
s
2
2
. . . p
s
k
k
.
Пример 29. Пусть m = 72, n = 7 5. Тогда 72 = 2
3
· 3
2
, 75 = 3 · 5
2
. Значит,
72 = 2
3
·3
2
·5
0
, 75 = 2
0
·3
1
·5
2
. Поэтому l
1
= min(3, 0) = 0, l
2
= min(2, 1) = 1,
l
3
= min(0, 2) = 0, а s
1
= max(3, 0) = 3, s
2
= max(2, 1) = 2, l
3
= max(0, 2) = 2.
Значит,
НОД(72, 75) = 2
0
· 3
1
· 5
0
= 3, НОК(72, 75) = 2
3
· 3
2
· 5
2
= 1800.
5
То есть число, которое является делителем и m, и n.
92                                                           §19. Кольцо целых чисел

Пара чисел (n, e) объявляется открытым ключом и помещается в открытый
каталог, а число d является секретным.
   Если абонент A хочет послать сообщение t (натуральное число) абонен-
ту B, то он выбирает из открытого каталога абонента B пару (n, e) и вычис-
ляет шифрованное сообщение
                            s = остаток от деления te на n,
а абонент B, получив это сообщение, вычисляет t по формуле
                            t = остаток от деления sd на n.
Чем больше числа p и q, тем сложнее расшифровать код (т.е. найти число d).
     Определение 14. Пусть m и n — целые числа.
      1. Наибольшим общим делителем (НОД) чисел m и n называется та-
         кой общий положительный делитель5 этих чисел, на который делится
         любой другой их общий делитель.
      2. Числа m и n называются взаимно простыми, если их НОД равен еди-
         нице.
      3. Наименьшим общим кратным (НОК) чисел m и n называется такое
         общее положительное кратное этих чисел, которое делит любое другое
         общее кратное этих чисел.
   Предложение 3. У любых двух ненулевых целых чисел существуют и
единственны НОД и НОК.

Нахождение НОД и НОК. Чтобы найти НОД и НОК чисел m и n, нуж-
но:
    1) найти разложение (3) для чисел m и n.
    2) записать числа m и n в виде m = pi11 pi22 . . . pikk , n = pj11 pj22 . . . pjkk . Если
       какое-нибудь из чисел pα не является делителем m или n, то соответ-
       ствующий показатель степени равен нулю;
    3) взять числа lα = min(iα , jα ). Тогда НОД = pl11 pl22 . . . plkk ;
    4) взять числа sα = max(iα , jα ). Тогда НОК = ps11 ps22 . . . pskk .
   Пример 29. Пусть m = 72, n = 75. Тогда 72 = 23 · 32, 75 = 3 · 52. Значит,
72 = 23 · 32 · 50, 75 = 20 · 31 · 52. Поэтому l1 = min(3, 0) = 0, l2 = min(2, 1) = 1,
l3 = min(0, 2) = 0, а s1 = max(3, 0) = 3, s2 = max(2, 1) = 2, l3 = max(0, 2) = 2.
Значит,
       НОД(72, 75) = 20 · 31 · 50 = 3,           НОК(72, 75) = 23 · 32 · 52 = 1800.

     5То есть число, которое является делителем и m, и n.

Страницы