Задание с экзамена по защите информации

в 13:26, , рубрики: защита информации, Учебный процесс в IT, экзамен

Сразу озвучу задачку, чтобы не было предвкушения, будто тут будет показан какой-то крутой новый метод шифрования.

Нужно доказать, чтоЗадание с экзамена по защите информации - 1

Статья ориентирована на студентов, заинтересованных граждан и просто зевак. У нас защита информации была на пятом курсе в институте. На лекциях по защите информации было много историй о нелегкой судьбе русских программистов в шальные девяностые: как им платили за работу пельменями, которые делались на цокольном этаже предприятия, где они работали, как делается самогон и т.п. А оставшееся время лекции посвящалось собственно аспектам защиты информации. На лекциях давалось очень много теории по темам, хоть как-то связанным с алгоритмами шифрования. На экзамене в каждом билете было пара вопросов по теории и одна задачка.

За день до нашего экзамена ребята с параллельной группы скинули одну задачку(описана в начале статьи), решить которую не смогли. Сидела я на работе, думала, как ее решить, около часа. Какие идеи и первые мысли по решению были у меня в голове на тот момент, я не скажу, уже несколько лет прошло. Кстати мне на экзамене попалась задачка такого же типа. Ниже покажу доказательство двух типовых задачек. Если вы знаете, как доказать по-другому, отпишитесь в комментариях.

Итак, приступим. Доказательство построено с использованием теоремы Эйлера.
Еще раз повторю задание. Нужно доказать, что Задание с экзамена по защите информации - 2 делится на 12 для всех простых x > 3.

x и 12 — взаимно простые, тогда по т.Эйлера, Задание с экзамена по защите информации - 3 делится на 12, т.е. остаток от деления равен 0 (в теореме единица перенесена в правую часть равенства, сделаем так же):
Задание с экзамена по защите информации - 4

Для числа 12 существует четыре меньших него и взаимно простых с ним чисел (1, 5, 7, 11), поэтому функция Эйлера принимает значение четыре:

Задание с экзамена по защите информации - 5
Задание с экзамена по защите информации - 6

Перенесем единицу из правой части равенства влево и воспользуемся формулой из школы, разложим на множители разность квадратов:

Задание с экзамена по защите информации - 7

Сокращаем на Задание с экзамена по защите информации - 8, поскольку Задание с экзамена по защите информации - 9 не кратно 12 при простых x > 3:

Задание с экзамена по защите информации - 10

Что и требовалось доказать.

А теперь вот вам еще одна типовая задачка, которая попалась мне на экзамене. Когда решение было показано преподу, он почему-то был удивлен, поскольку, как он потом сказал, было бы достаточно просто посчитать в лоб, возвести в степень и показать, что одно число делится на другое. А решение, которое я ему показала, он видит впервые. Вот всегда думаешь, что для доказательства нужно применить теоремы, следствия, аксиомы, а оказывается «можно было просто в лоб посчитать».

Доказать, что число Задание с экзамена по защите информации - 11 делится на 105.

Если число делится нацело, то остаток 0. Числа 73 и 105 – взаимно простые => по т. Эйлера:

Задание с экзамена по защите информации - 12

Вычисляем функцию Эйлера. Поскольку перебирать все числа меньше 105 и искать взаимно простые со 105 долго, разложим 105 на множители и найдем функцию Эйлера для каждого из них, а после просто перемножим:
Задание с экзамена по защите информации - 13

Задание с экзамена по защите информации - 14

Переносим единицу влево и раскладываем на множители:
Задание с экзамена по защите информации - 15

Сокращаем на Задание с экзамена по защите информации - 16, поскольку выражение не кратно 105:

Задание с экзамена по защите информации - 17

Разложим на множители и сократим еще раз:

Задание с экзамена по защите информации - 18
Задание с экзамена по защите информации - 19

Остаток от деления Задание с экзамена по защите информации - 20 на 105 — ноль, деление нацело. Ч.т.д.

Возможно, кому-то пригодится это решение, но, надеюсь, что у вас на ЗИ будет что-то поинтереснее.

Автор: AnROm

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js