Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
48 Я E о я E Я T А о ? с ? я Л г с я
49 О P H III г ь Г 3 И H E
50 E о О с г E Я
458
/ Іример
Таблица 6
f 1 2 3 4 5 6 T 8 9 10 11 I \ н| \14 15 16 Г 13 1 20 ^l 72 24 1 25
I P 1 III В г E E ь Г и LU Ї т I и B в I1 о в Б ф о Ы Ц.
*> В O л H O Я Я 3 О T д А 1 ? H я ы Y я А ш И \ F У
3 А H ж В C ь В Б о г ILl L T г 3 ч E F H В г H F P Б
4 Б F P H И я // /4 \ о J Я Л о с ь Я V/ F Я я ? я B 4
5 В Б д H и ж г P F \ г А H ж H 3 и Г P Б P Б г T г
6 H А п E г P о B Я ч А S ? P F с г о в Л в M о Л О
7 Ні Г 3 И ь 3 P Г H и 3 T I я I T г в P ы P Б ж UI С
8 п O г T я C в о L я С 7 У ;а Я л о я я г я Л P д я
9 е P H ф H T P г И 3 И Б P с Л P в ь У Б I H ы і III
IO И в А/ Ul E ./7 в о T с Л я А У в я А */ А Л ? F о д
Il Б л H O Б T P 3 P г J Lil H Ж H P в э F 3 и H О д г
12. Л У E А Л Л в с в о /О Д F P F в F т 7/ С / 7 Y я о
13 Ж г B F И И л ш Б в H P H H К я Б T Г в А Ц 1 я H
14 P о Я O T T У л А я E В Ы ? 3 ж А 7 Cf я ь А/ Л ж I ?
15 в Б И В Б А H ш В г E ш P Г ж ю B С H с г И Г ж I Б
16 А T H А /? F Il И о И д В о P я Я К E /г о T о P А
17 ю Ji ь H ж T Б P ж г ш Б о P и г P ж H ь ю с Б с Г
18 я У Vf E P л А в P о л А Y в г о я P F л/ я /г А А* о
19 в в Б O г ш Ь T 3 ю P Г И U H к я H Б д г T H О г
20 я Я ,4 Y O д И л с я в о г ъ F 3 д F M я о У7 E л о
21 K ю E 3 и P H В в ц H л д Ж Б я в H В E ю 3 С г ж
22 3 я Я C г я E я я ы E У я P А ж я E я Я я с К о P
23 г H Ь1 г л и H ф E 1 E г в P Ц 3 Pl Ж г E T ш I ь д
24 O E / O У T E ш Я л Я о я в ы с T P о Я л д о M я
2^ г 3 г А 3 и P H в в Г ь Л д T Б в 4 к Б P H T Л 3
26 O C O Б C г В E я я о л/ У я л /1 я У 3 Л в F Л У с
27 H А ю 3 л с Г в в л э M Б А ж ь с Л Л И ж Г E T IU
28 E Б я C У к о я я * IO ф А Б P я А* У У Г P о Я 7 д
29 г O г ш ц E 3 и Б T Д г У E и Б И ч 3 H А ю Л ь в
30 O Y O д Ы Я с T // я о tZ И г /1 T ь с E Б я У л/ я
31 H E ф E Б У H T Г P H с г Б P г P 3 H ь Г с г T г
32 E Я ш Я M V F л о в ? к о M в о в с E M О А о Л о
33 И C H P У H ь F в H д ж H С г 3 г г P E T E H ь JI
34 T K E в ч ? M я я E я P E л о с л о в Я л Я F M У
3S 3 г 3 H UI E д ж E H к я Б P ф E H с в H Б Л ы г 3
36 C O C E д Я п P Я E ж А в ш И E к я F л/ У F о с
37 и E и ч 3 3 P г E Б E 3 H Б H E 3 и P Б Б E E 3 г
38 T Я T ь C с в о Я M Я с E M E И с 7 в А И Я Я с 0
39 А Б C Б Б E P А П ш в F Г в О г ш F T P д T E 3 г
40 Я А K А M Я в ? У Д я я о я X о д И л Д я л Я г о
41 P Г E C л ж и С H Д г д ж Б к UI в E с Б Б в Б Ui H
42 Я O H K У P T к ? Я о я P А 3 д я Я к А л/ я /4 д E
43 P Б T 3 H ж и ч С E к 3 Л С в Б UI Г Б Б ф в H E ж
44 в А я C E P T У А Я 3 с У л* я А д о M А ш я ? я P
45 Б А г и ц 3 Б Б К Б JX ь 3 ІД P Б T ж Б 3 о г Ш F в
46 А Б O F Ы с Л V/ 3 4 я я с ы в А л P А С X о д Я я
47 E У H ЬІ г В H У E И Б г с ж г Б H 3 H в Б и 3 с E
48 Я ч E г 0 Я E fZ Я T А л к P о M E г E // 4 г с к //
49 50 O X P в H E ш д г O ь д/ Г о 3 с И T H ь E Я
459
Приложение З
Элементы алгебры и теории чисел
Модулярная арифметика
Пусть а и п — натуральные числа. “Разделить число а на число п с остатком” — это значит найти целые числа а и г, удовлетворяющие условию
a = q n +г, где 0 <г <п.
При этом число q называют неполным частным, а г - остатком от деления числа а на число п.
Если остаток г равен нулю, то говорят, что число п делит число а, или, по-другому, п является делителем числа а,
Целые числа а и Ъ называют сравнимыми по модулю п, если их остатки при делении на п совпадают. Обычно для обозначения этого факта используется запись
а = Ъ (mod п) .
Отсюда, в частности, следует, что число п делит разность чисел а и Ь. Для обозначения остатка часто используют бесскобочную запись
b = a mod п .
Операцию нахождения числа b = a mod п называют приведением числа а по модулю п.
Множество целых чисел a0v..,aw_j, таких, что для любого целого числа b найдется к є со свойством
ак = b(mod п), называется полной системой вычетов по мо-
460
Цементы алгебры и теории чисел
дулю п. Обычно используется полная система вычетов {О,
Разложение чисел на простые множители
Натуральное число a, большее 1, называется простым, если оно не имеет натуральных делителей, отличных от 1 и самого числа а.
Любое натуральное число, отличное от 1, либо является простым, либо может быть представлено в виде произведения простых чисел. Это представление определено однозначно с точностью до порядка сомножителей в произведении.
Следует отметить, что в настоящее время нет достаточно эффективных алгоритмов разложения произвольного целого числа на простые множители даже в случае, когда известно, что оно разлагается в произведение двух простых чисел. Отсутствие эффективных алгоритмов с доказуемыми оценками сложности позволяет использовать задачу разложения натуральных чисел на простые множители при обосновании стойкости некоторых криптографических алгоритмов.
Алгоритм Евклида нахождения наибольшего общего делителя
Наибольшее целое число, делящее одновременно целые числа а и Ь, называется их наибольшим делителем и обозначается НОД(а, b) или просто (<а, Ь). Если (a, ZO==I, то а и Ъ называются взаимно простыми числами.
