Файл: Отчет по лабораторной работе 1 по дисциплине Защита информации в автоматизированных системах управления.docx

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ Российской Федерации

Федеральное государственное бюджетное

образовательное учреждение высшего образования

«ТЮМЕНСКИЙ ИНДУСТРИАЛЬНЫЙ университет»

Институт дополнительного и дистанционного образования

Управление в технических системах

Отчет по лабораторной работе №1

по дисциплине

«Защита информации в автоматизированных системах управления»

Выполнил:

магистрант группы ИБм(до)з-22-1

Соловьёва Н.Л.

Проверил:

Доцент кафедры КС к.т.н,

Музипов Х.Н.


Содержание

Постановка задачи и решение лабораторной работы №1

Цель работы: написать программу, реализующую набор функций для работы с числами.

Задачи:

Написать функцию для нахождения наибольшего общего делителя двух чисел на основе алгоритма Евклида.

Реализовать функцию для нахождения последовательности простых чисел, не превосходящих заданного числа N, на основе алгоритма Эратосфена.

Создать функцию для вычисления функции Эйлера для положительного целого числа.

Написать функцию для решения линейных сравнений.

В рамках работы необходимо оформить программу в виде отдельного модуля (библиотеки), а также предоставить отчет, содержащий схемы алгоритмов, описание основных функций программы, словесное описание модулей, тестовые примеры и выводы по работе.

Решение задач:

Дано:

1. Найдите НОД (396,1452)?

2. Найти каноническое разложение числа а)2156; б)1934; в)1132.

3. Являются ли числа попарно простыми

а) (678, 941); б) (243, 1485); в) (535, 321)?

4. Решить линейное сравнение:

а) ; б) ; в)

Для решения упражнений вам потребуется использовать функции из модуля "number_theory.py". Давайте по очереди решим каждое упражнение.

---

Чтобы найти НОД (396, 1452), используем функцию euclidean_gcd из модуля "number_theory.py":

from number_theory import euclidean_gcd

a = 396

b = 1452

gcd = euclidean_gcd(a, b)

print(f"НОД({a}, {b}) = {gcd}")

Чтобы найти каноническое разложение числа, вам потребуется определить простые множители числа. Для этого можно воспользоваться функцией sieve_of_eratosthenes из модуля "number_theory.py" и последовательно делять число на найденные простые числа до тех пор, пока результат деления не станет равным 1.

from number_theory import sieve_of_eratosthenes

def prime_factorization(n):

primes = sieve_of_eratosthenes(n)

factors = []

for prime in primes:

while n % prime == 0:

factors.append(prime)

n //= prime

if n > 1:

factors.append(n)

return factors

# a) Каноническое разложение числа 2156:

n = 2156

factors = prime_factorization(n)

print(f"Каноническое разложение числа {n}: {factors}")

# б) Каноническое разложение числа 1934:

n = 1934

factors = prime_factorization(n)

print(f"Каноническое разложение числа {n}: {factors}")

# в) Каноническое разложение числа 1132:

n = 1132

factors = prime_factorization(n)

print(f"Каноническое разложение числа {n}: {factors}")

Чтобы определить, являются ли числа попарно простыми, нужно проверить их попарные НОДы. Используем функцию euclidean_gcd из модуля "number_theory.py":

from number_theory import euclidean_gcd

# а) Числа (678, 941):

numbers = [678, 941]

pairwise_coprime = True

for i in range(len(numbers)):

for j in range(i+1, len(numbers)):

gcd = euclidean_gcd(numbers[i], numbers[j])

if gcd != 1:

pairwise_coprime = False

break

print(f"Числа (678, 941) являются попарно простыми: {pairwise_coprime}")

# б) Числа (243, 1485):

numbers = [243, 1485]

pairwise_coprime = True

for i in range(len(numbers)):

for j in range(i+1, len(numbers)):

gcd = euclidean_gcd(numbers[i], numbers[j])

if gcd != 1:

pairwise_coprime = False

break

print(f"Числа (243, 1485) являются попарно простыми: {pairwise_coprime}")

# в) Числа (535, 321):

numbers = [535, 321]

pairwise_coprime = True

for i in range(len(numbers)):

for j in range(i+1, len(numbers)):

gcd = euclidean_gcd(numbers[i], numbers[j])

if gcd != 1:

pairwise_coprime = False

break

print(f"Числа (535, 321) являются попарно простыми: {pairwise_coprime}")

Для решения линейного сравнения вида ax ≡ b (mod m) используем функцию linear_congruence из модуля "number_theory.py":

from number_theory import linear_congruence

# а) Решение линейного сравнения 3x ≡ 1 (mod 7):

a = 3

b = 1

m = 7

solutions = linear_congruence(a, b, m)

if solutions:

print(f"Решение линейного сравнения {a}x ≡ {b} (mod {m}): {solutions}")

else:

print("Линейное сравнение не имеет решений.")

# б) Решение линейного сравнения 4x ≡ 2 (mod 10):

a = 4

b = 2

m = 10

solutions = linear_congruence(a, b, m)

if solutions:

print(f"Решение линейного сравнения {a}x ≡ {b} (mod {m}): {solutions}")

else:

print("Линейное сравнение не имеет решений.")

# в) Решение линейного сравнения 5x ≡ 1 (mod 6):

a = 5

b = 1

m = 6

solutions = linear_congruence(a, b, m)

---

if solutions:

print(f"Решение линейного сравнения {a}x ≡ {b} (mod {m}): {solutions}")

else:

print("Линейное сравнение не имеет решений.")

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

Что внутри алгоритма:
1. Найдем НОД(396, 1452) с помощью алгоритма Евклида:

1452 = 3 * 396 + 264

396 = 1 * 264 + 132

264 = 2 * 132 + 0

Последний ненулевой остаток равен 132. Таким образом, НОД(396, 1452) = 132.

2. Каноническое разложение чисел:

а) 2156 = 2^2 * 539 = 2^2 * 7 * 77 = 2^2 * 7 * 7 * 11

б) 1934 = 2 * 967

в) 1132 = 2^2 * 283

3. Проверим, являются ли числа попарно простыми:

а) (678, 941): НОД(678, 941) = 67, так как 67 является единственным делителем для обоих чисел, они являются попарно простыми.

б) (243, 1485): НОД(243, 1485) = 27, так как 27 является общим делителем для обоих чисел, они не являются попарно простыми.

в) (535, 321): НОД(535, 321) = 107, так как 107 является единственным делителем для обоих чисел, они являются попарно простыми.

4. Решим линейные сравнения:

а) 5x ≡ 3 (mod 7):

Найдем обратный элемент 5 по модулю 7. В данном случае, 5^(-1) ≡ 3 (mod 7).

Умножим обе части на 5^(-1):

3 * 5x ≡ 3 * 3 (mod 7),

25x ≡ 9 (mod 7).

Найдем остаток от деления 9 на 7, что равно 2.

Решением линейного сравнения 5x ≡ 3 (mod 7) является x ≡ 2 (mod 7).

б) 6x ≡ 9 (mod 15):

Найдем обратный элемент 6 по модулю 15. В данном случае, 6^(-1) ≡ 11 (mod 15).

Умножим обе части на 6^(-1):

9 * 6x ≡ 9 * 11 (mod 15),

54x ≡ 99 (mod 15).

Найдем остаток от деления 99 на 15, что равно 9.

Решением линейного сравнения 6x ≡ 9 (mod 15) является x ≡ 9 (mod 15).

в) 4x ≡ 6

(mod 8):

Данное линейное сравнение не имеет решений, так как 4 и 8 не являются взаимно простыми числами.

Вопросы к лабораторной работе № 1

1. Докажите теорему о делении с остатком.

2. Дайте понятие НОД двух чисел? Какой алгоритм используется для его нахождения?

3. Какие числа называются простыми, составными?

4. Расскажите алгоритм нахождения последовательности простых чисел.

5. Какое разложение целого числа называется каноническим?

6. Что показывает функция Эйлера, как она рассчитывается?

7. Расскажите алгоритм решения линейных сравнений.

1. Докажите теорему о делении с остатком.

Теорема о делении с остатком утверждает, что для любых целых чисел a и b, где b ≠ 0, существуют единственные целые числа q и r, такие что a = bq + r, где q - частное, r - остаток, причем 0 ≤ r < |b|.

Доказательство:

---

Шаг 1: Существование остатка и частного:

Рассмотрим два целых числа a и b, где b ≠ 0. Рассмотрим множество всех чисел, которые могут быть представлены в виде a - bx, где x - целое число. Пусть это множество обозначается как S. Мы должны доказать, что существует такое число r ∈ S, что 0 ≤ r < |b|.

Рассмотрим множество S = {a - bx | x ∈ Z}. Если S содержит положительное число, то существует наименьший элемент r в S (по аксиоме вполнеупорядоченности натуральных чисел). В этом случае, a - br ∈ S и a - br < r не может быть положительным, так как r является наименьшим положительным числом в S. Таким образом, r не может быть положительным и, следовательно, r ≤ 0.

Шаг 2: Ограничение остатка:

Предположим, что r < 0. Рассмотрим число r + |b|. Тогда a - b(q + 1) = a - bq - b = r + |b| > r, где q + 1 - новое предполагаемое частное. Значит, r не может быть меньше 0.

Таким образом, мы доказали, что существует такое число r, что 0 ≤ r < |b|.

Шаг 3: Единственность остатка и частного:

Предположим, что есть два различных представления для a в виде a = bq + r и a = bq' + r', где 0 ≤ r, r' < |b|. Тогда bq + r = bq' + r'. Отсюда следует, что b(q - q') = r' - r.

Поскольку левая часть равенства делится на b, а правая часть меньше |b|, то получаем, что обе части равенства равны нулю. Таким образом, r' - r = 0 и q - q' = 0, что приводит к тому, что r = r' и q = q'.

Таким образом, мы доказали, что остаток r и частное q в разложении a = bq + r являются единственными.

Теорема о делении с остатком доказана.

2. Дайте понятие НОД двух чисел? Какой алгоритм используется для его нахождения?

НОД (Наибольший Общий Делитель) двух чисел - это наибольшее целое число, которое одновременно делит оба числа без остатка. Другими словами, НОД двух чисел - это наибольший общий делитель для этих чисел.

Для нахождения НОД двух чисел существует несколько алгоритмов, одним из самых известных и эффективных является алгоритм Евклида.

Алгоритм Евклида работает по следующему принципу:

Пусть a и b - два числа, для которых мы хотим найти НОД.

Если b равно 0, то НОД(a, b) равен a.

В противном случае, мы заменяем a на b, и b на остаток от деления a на b (a mod b).

Повторяем шаги 2 и 3 до тех пор, пока b не станет равным 0.

Когда b равно 0, НОД(a, b) равен a.

Алгоритм Евклида основан на простом наблюдении, что НОД(a, b) равен НОД(b, a mod b). Поэтому мы последовательно заменяем большее число на остаток от деления и продолжаем этот процесс до достижения нулевого остатка.

Алгоритм Евклида эффективен и позволяет быстро находить НОД двух чисел даже при больших значениях. Он широко используется в математике и алгоритмах для решения различных задач,

---

таких как нахождение простых чисел, решение линейных сравнений и других.

3. Какие числа называются простыми, составными?

Простые числа - это натуральные числа больше единицы, которые имеют ровно два делителя: 1 и само число. Иными словами, простое число делится только на 1 и на себя.

Например, числа 2, 3, 5, 7, 11 и 13 являются простыми, так как они имеют только два делителя: 1 и само число.

Составные числа - это натуральные числа больше единицы, которые имеют более двух делителей. Иначе говоря, составное число делится не только на 1 и на себя, но также имеет другие делители.

Например, число 4 является составным, так как оно делится не только на 1 и на себя, но также на 2. Аналогично, числа 6, 8, 9 и 10 также являются составными, так как у них есть делители, отличные от 1 и самих чисел.

Простые числа являются основными строительными блоками для всех других чисел. Составные числа можно представить как произведение простых чисел.

4. Расскажите алгоритм нахождения последовательности простых чисел.

Алгоритм нахождения последовательности простых чисел, не превосходящих заданное число N, основан на алгоритме Эратосфена. Этот алгоритм позволяет эффективно определить все простые числа в заданном диапазоне.

Шаги алгоритма Эратосфена для нахождения простых чисел до N:

Создайте список чисел от 2 до N и обозначьте их как простые.

Начиная с числа 2, пометьте его как простое, а все его кратные числа (кроме самого числа) пометьте как составные.

Перейдите к следующему непомеченному числу, которое будет простым, и пометьте все его кратные числа как составные.

Повторяйте шаг 3 до тех пор, пока не пройдете все числа от 2 до N.

Все непомеченные числа в итоге останутся простыми числами.

Пример работы алгоритма:

Допустим, нам нужно найти все простые числа, не превосходящие 30.

Создаем список чисел от 2 до 30: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30].

Начинаем с числа 2. Помечаем его как простое и помечаем все его кратные числа (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30) как составные.

Переходим к следующему непомеченному числу, которым является 3. Помечаем его как простое и помечаем все его кратные числа (6, 9, 12, 15, 18, 21, 24, 27, 30) как составные.

Переходим к следующему непомеченному числу, которым является 4, но так как оно уже помечено как составное, пропускаем его.

---