Введение в криптографию. Теоретико-числовые основы защиты информации [Елена Ивановна Деза] (pdf) читать постранично, страница - 4

Таблицы Виженера ........................................................................... 333
10.3. Таблицы частотности.........................................................................334
10.4. Таблицы простых чисел...................................................................... 338
10.5. Таблицы неприводимых и примитивных многочленов...................346
10.6. Таблицы индексов.................................................................'.............348
Ответы и реш ения........................................................................................... 355
Словарь терминов.............................................................................................. 359
Литература.........................................................................................................363

Tlgm: @it_boooks

Обозначения

► N = {1, 2, 3, ...} — множество натуральных чисел;
Z = { . . . , —3, —2, —1, 0, 1, 2, 3, ...} — множество целых чисел.
► rest (а, Ъ) — остаток отделения целого числа а на натуральное число Ь:
a = bq + rest(a, Ь), где q, rest(a, Ь) G Z, и 0 < rest(a, b) < Ь.
► 6|a — целое число b, отличное от нуля, делит целое число а, то есть
а = Ьс, где с G Z.
► (а ь . . . an) — наибольший общий делитель целых чисел а ь . . . , а п,
хотя бы одно из которых не равно нулю, то есть наибольшее целое
число, делящее каждое из чисел а ь • • ., ап.
► [а\, . . . ап\ — наименьшее общее кратное целых чисел а \, . .. , а п , каж­
дое из которых не равно нулю, то есть наименьшее натуральное число,
делящееся на каждое из чисел а\ , . . . , а п .
► Р — {2, 3, 5, 7, 11, 13, 17, 19, ...} — множество простых чисел, то есть
натуральных чисел, имеющих ровно два натуральных делителя; р , q,
Р\, • •
Яь • • •, Qt — простые числа; п = р "1 • р "2 • • • • * > гДе
Р\9Р2 , • • • >Ps — различные простые числа, и а\,
..., a s G N каноническое представление натурального числа п > 1, то есть пред­
ставление п в виде произведения натуральных степеней различных
простых чисел.
► Р п — п - ъ простое число: р \ = 2, р 2 = 3, рз — 5 и т.д.
► р = a • q + 1 (где р, q G Р , и q велико) — сильное простое число, то есть
достаточно большое простое число р, такое что р — 1 имеет большие
простые делители, например q (причем q — 1 также имеет большие
простые делители), и р + 1 имеет большие простые делители.

► п —рі • р 2 • . . . • ps (где Р\,Р 2 , • • ., ps — различные простые числа) —
бесквадратное число.
► S = {4, 6 , 8 , 9, 10, 12, 14,15, 16, 18, ...} — множество составных чисел,
то есть натуральных чисел, имеющих не менее трех натуральных де­
лителей; N — P U 5 U {1}.
► п = 2аі • Заз ♦ ... • psPs (где 2 , 3, . . . , ps — последовательные простые
числа, а 2 > «з > . . . > а!рз, и
= 1 кроме п — 4; 36) — сильно
составное число, то есть натуральное число, которое имеет больше
делителей, чем любое предшествующее ему натуральное число.

Tlgm: @it_boooks

9

Обозначения

► В = {р\9рг, • • • , p s} — база разложения, то есть множество, состоя­
щее из нескольких различных простых чисел; п — р“] • . . . • p f 3 (где
^ 0) — В-гладкое число, то есть натуральное число, все простые
делители которого принадлежат базе В.
► п = (afc_iafc_2 . . . a i a 0)5 (где к ^ 0 , 0 ^ а* <
и afc_i Ф 0 ) —
запись натурального числа п в системе счисления с основанием д, то
есть представление п — а^-\дк~х + а>к-гдк
~2 + •.. + «і * д + Ооі ао,
аі, . . . , a,k- 1 — д-ичные цифры числа п.
► [ж] — целая часть действительного числа х , то есть наибольшее целое
число, не превосходящее ж; [ж] — наименьшее целое число, большее
или равное х.
► (р(п) — функция Эйлера, дающая число натуральных чисел, не превосхо­
дящих п и взаимно простых с ним:
^ (п ) — \{х £ N : х ^ п, (х, п) = 1}| = п • Ц
tр\п
t

(\ - -

V

Р

► /х(п) — функция Мебиуса: /х(1) = 1, /х(п) = (—l)s для бесквадратного
числа п = рі • . . . • ps , и /х(п) = 0 в остальных случаях.
► sign(a;) — знак действительного числа х: sign(a;) — 1 при х > 0 ,
sign(a;) = —1 при х < 0 , и sign(a;) = 0 при х = 0 .
► іг(х) = X) 1 — число простых чисел, не превосходящих действитель­
на;

ное число х.
сумма (произведение) значений комплекснозначной функции f ( x ), определенной для всех х £ N, по всем нату­
ральным делителям d натурального числа п.
► f (n) = 0(д(п)) (где f 9g — комплекснозначные функции натурального
аргумента) — функция f (n ) есть О-большое от функции д(п), то есть
существует такая положительная действительная константа С и такое
натуральное число щ , что для любого п ^ щ имеет место неравенство
► а = b(m odn) — целые числа а и Ь сравнимы по модулю n , n £ N,
то есть а и b имеют одинаковые остатки при делении на п, или, что
то же, п\(а — Ь).
► а ^ Ъ(m odn) — целые числа а и Ъ несравнимы по модулю n , п £ N,
то есть а и Ъ имеют различные остатки при делении на п, или, что
то же, п \ (а — Ь).

Tlgm: @it_boooks

Обозначения

10

► а„ — { x € Z : x = a (mod n)} = { . .. , a - 2n, a - n, a, a + n, a + 2n, ...} —
класс вычетов (числа а) по модулю п, то есть множество всех целых
чисел, сравнимых с числом а по модулю п.
► a m odn — один из вычетов, принадлежащих классу вычетов ап;
как правило, наименьший неотрицательный (наименьший по моду­
лю, наименьший натуральный) вычет класса ап, то есть наименьшее
неотрицательное (наименьшее по модулю, наименьшее натуральное)
число, сравнимое с а по модулю п.
►

— символ Лежандра:

= 1, если целое число а, взаим­

но простое с нечетным простым числом р, является