Учебно-методический комплекс по дисциплине " криптография 1 " Научная сфера: 300 000 Сфера технического производства

2.2 МАТЕРИАЛЫ ПРАКТИЧЕСКИХ ЗАНЯТИИ
Практическая работа №1
Тема. Математические основы криптографии
Деление c остатком (деление по модулю) — арифметическая операция, играющая большую роль в арифметике, теории чисел и алгебре. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом. Пусть a и b — целые числа, причём b0 Деление с остатком a («делимого») на a («делитель») означает нахождение таких целых чисел q и r, что выполняется равенство:
a = b*q + r
8=3*2+2
Таким образом, результатами деления с остатком являются два целых числа: q называется неполным частным от деления, а r — остатком от деления. На остаток налагается дополнительное условие: 0  r < |b|, то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел. Если остаток равен нулю, говорят, что a нацело делится на b.
Z={0, 1, 2, 3, … } - целые числа.
Примеры.
При делении с остатком положительного числа a = 78 на b = 33 получаем неполное частное q = 2 и остаток r = 12.
Проверка: 78 = 33 * 2 + 12.
12=78mod33
r = a modb
Теория mod:
(a+b)mod n=((a mod n)+(b mod n))mod n,
(a-b)mod n=((a mod n)-(b mod n))mod n,
(a·b)mod n=((a mod n) · (b mod n))mod n,
(a· (b+c)mod n=(((a·b) mod n)+(a·c) mod n))mod n.
Основные характеристики вычисления по mod:

1. 
   b=a mod n если a>n>0 тогда, делится а на n и вычисляется остатку b. Например: 12mod5=2; 15mod6=3;
   
2. 
   b=a mod n если n>0 ва a<0 тогда, добавляется b раз n до а больше нуля. Например, -5mod6=1; -12mod5=3;
   
3. 
   В равенстве (e*d)modn=1 у нас известно значение e и n, нам необходимо найти значения d. Для того определим два значения a=n и b=e. Создаём 3 множества: