Тема 11. Криптографические шифры
Теоретические сведения Понятие вычета. Вычетом числа a по модулю m называется остаток от деления a на m Из определения видно, что вычеты связаны с делением с остатком. Разделить натуральное число a на натуральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г < b такие, что выполняется равенство а = q·b + г Так для чисел 187 и 12 соответствуют два числа 15 и 7, такие, что 187= 15·12+7. Это равенство часто записывается в виде 187:12 = 15(ост. 7). Напишем названия компонентов деления с остатком: а – делимое, b- делитель, q- частное, r – остаток. Рассмотрим еще примеры: а = - 12, b = 8 ® -12 = (- 2) · 8 + 4, q= -2, r=4 а = - 324, b = - 15 ® — 324 = 22 · (- 15) + 6 q=22, r=6 a = 4, b=10 ® 4=0·10+4 q=0, r=4 a = 12, b = 4 ® 12=4·3+0 q=4, r=0 Число a делится нацело на b, если остаток r = 0 или, а = qb. .Причем отношение «делиться на цело» обозначается . Теорема. Если а и b делятся на с, то при любых целых k и j сумма ka + jb делится на с. Задание 9-1.Найти такое число d ¹ 1, на которое делятся числа 6п + 5 и 9л + 2. При каком значении п. это деление возможно? Решение. Если числа 6п + 5 и 9п + 2 делятся на d, то на d делится и разность 3(6n + 5) - 2(9п + 2) = 15 - 4 = 11 Число 11 — простое число, значит d= 11. Не трудно установить, что п = …- 21, — 10, 1, 12, 23… Сравнение по модулю. Числа в основном сравнивают по величине, но их можно сравнивать по другим признакам и свойствам. Например, по количеству цифр, по остаткам деления, по делимости на некоторое число и др. Рассмотрим сравнение чисел на основе равенства их остатков при делении на некоторое число, что приводи к понятию вычетов. Такое сравнение называется сравнением по модулю. Не следует путать с абсолютной величиной числа, которая так же называется модулем. Введем форму записи остатка: R = A mod B, где A-делимое, B- делитель, R-остаток. Получаемое в процессе деления частное в данном случае не рассматривается. Например, 5=15 mod 10, 3= 45 mod 7 и т.д. При делении n («nÎZ) на g все целые числа разбиваются на g подмножеств, которые соответствуют числу, полученному в остатке. Остатки при этом будут равны: n mod g ={0,1,2,…g-1} Причем, каждому остатку можно поставить в соответствие множество чисел вида: 0 ® n mod g =0 n=k g 1 ® n mod g =1 n=kg+1 2 ® n mod g =2 n=kg+2 3 ® n mod g =3 n=kg+3 g-1 ® n mod g =g-1 n=k(g-1) Очевидно, что любое целое число а принадлежит одному из этих g подмножеств. Причем разность любых двух чисел одного подмножества делится на g, а разность чисел из разных множеств не должна делиться на g. Два целых числа называются сравнимыми по модулю g (g ³ 2), если их разность кратна натуральному числу, т.е. (а — b) g,. Запишем это определение символами: а º b (mod g), если $ kÎ Z (а — b= kg)., Это значит, что числа а и b сравнимы по модулю g тогда и только тогда, когда они принадлежат одному подмножеству, т.е. дают одинаковые остатки при делении на g.. Например: 36 º I6 (mod l0) – числа 36 и 16 сравнимы по модулю 10 24 º 4 (mod 6) - число 24 сравнимо по модулю 6 с число 4 -26º 6 (mod 30) Отметим разницу в записях: записей: 1. аº b (mod g ) или (а= b) (mod g ) означает сравнимость чисел по модулю (сравнение) 2. а= b (mod g ) - означает равенство числа a остатку от деления b на g Отношение сравнимости рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности. Вычетами по модулю р называют отдельные классы эквивалентности для отношения сравнимости (по модулю p)) и обозначают Zp, Раздел математики, изучающий вычеты по модулю, называется алгеброй вычетов (теорией вычетов, модулярной арифметикой). Свойства сравнимости 1. Два числа, сравнимые с третьим по одному модулю, сравнимы между собой: 2. Сравнения можно складывать и вычитать: (а º b(mod p); cºd(mod p)) => (а ± с) º (b ± d)(mod p). Слагаемые можно переносить из одной части сравнения в другую с противоположным знаком. 3. Сравнения можно перемножать: (a º b(mod p), с º d(mod p)) => (ас º bd(mod p)). 4. Обе части сравнения можно умножить на одно и то же целое число k: (а º 6(mod p}) => (ak º bk(mod p)). 5. Обе части сравнения и модуль можно умножить на одно и то же число: (а º b (mod p)) => (akºbk(mod pk)). 6. Обе части сравнения можно возвести в степень (следствие свойства 3): (а º b (mod p)) => (аn = bn (mod p)). Понятие сравнения ввел К.Ф.Гаусс в работе «Арифметические исследования» (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторяющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через период 2к, и т.д. Алгебра вычетов — один из тех разделов математики, которые рождались как некоторые формальные рассуждения и только спустя годы нашли свое практическое применение. Задание 9-2. Для степени y=2n (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя. Решение и комментарии. Как известно, натуральные степени числа 2 оканчиваются цифрами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2. Определим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2я:
f: N®{2, 4, 8, 6}, Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),. Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k) Последнее равенство означают, что для любого п нужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n). Но это задача на делении с остатком числа n на 4: n=4k+m, k-частное, т — остаток. Очевидно, последняя цифра числа 2″ зависит от остатка, полученного при делении показателя n степени 2 n на 4. Отразим этот факт в записи функции: f(n)= f(n mod 4) Из этой формулы можно установить, если f(n mod 4)=0, то При делении чисел на 4 «nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 n для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3. Задание 9-3.Установить последнюю цифру степени y=2 2007 Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=23=8. Ответ 8. Тема 11. Криптографические шифры План. 1. Защита информации, понятие шифра и шифрования 2. Простейшие криптографические шифры Цель. Знакомство с понятием шифр и некоторыми криптографическими шифрами.
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (923)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |