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

Переходим к следующему непомеченному числу, которым является 5. Помечаем его как простое и помечаем все его кратные числа (10, 15, 20, 25, 30) как составные.

Продолжаем этот процесс для оставшихся чисел.

В итоге получаем следующую последовательность простых чисел: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].

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

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

Каноническое разложение целого числа - это представление числа в виде произведения простых чисел, возможно с повторениями, в котором порядок сомножителей не имеет значения.

Формально, для целого числа n, его каноническое разложение выглядит следующим образом:

n = p₁^α₁ * p₂^α₂ * p₃^α₃ * ... * pₖ^αₖ,

где p₁, p₂, p₃, ..., pₖ - простые числа, α₁, α₂, α₃, ..., αₖ - их соответствующие степени.

Например, каноническое разложение числа 2156:

2156 = 2^2 * 7 * 7 * 11.

В данном случае, число 2156 представлено в виде произведения простых чисел, где 2 встречается в квадрате (2^2), а числа 7 и 11 присутствуют в первой степени.

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

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

Функция Эйлера, также известная как функция φ (phi) или функция Эйлера-Фи, является арифметической функцией, которая показывает количество положительных целых чисел, меньших и взаимно простых с заданным числом n.

Функция Эйлера обозначается как φ(n), где n - положительное целое число.

Для рассчета функции Эйлера φ(n), необходимо выполнить следующие шаги:

Разложить число n на простые множители, получив его каноническое разложение.

Для каждого простого множителя p в каноническом разложении числа n вычислить φ(p) = p - 1, так как каждое простое число p взаимно просто со всеми числами меньше него.

Умножить все значения φ(p) для каждого простого множителя p в разложении n: φ(n) = φ(p₁) * φ(p₂) * ... * φ(pₖ).

Например, для числа n = 10:

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

Значения φ(2) = 2 - 1 = 1 и φ(5) = 5 - 1 = 4.

Вычисляем φ(10) = φ(2) * φ(5) = 1 * 4 = 4.

Таким образом, функция Эйлера для числа 10 равна 4.

Функция Эйлера имеет много применений в теории чисел и криптографии, особенно в контексте алгоритмов шифрования и нахождения обратного элемента в кольцах по модулю.

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

---

Алгоритм решения линейных сравнений основан на нахождении обратного элемента в кольце вычетов. Линейное сравнение имеет вид:

ax ≡ b (mod m),

где a, b и m - целые числа, a и m не равны нулю, и x - неизвестное целое число, которое мы хотим найти.

Для решения линейного сравнения необходимо выполнить следующие шаги:

Найдите наибольший общий делитель (НОД) чисел a и m с помощью алгоритма Евклида. Если НОД(a, m) не равен 1, то линейное сравнение не имеет решений. Если НОД(a, m) равен 1, переходим к следующему шагу.

Найдите обратный элемент a по модулю m. Обратный элемент a обозначается как a^(-1) и удовлетворяет условию: a * a^(-1) ≡ 1 (mod m). Для нахождения обратного элемента можно использовать расширенный алгоритм Евклида.

Умножьте обе части исходного линейного сравнения на обратный элемент a^(-1):

(a^(-1) * a * x) ≡ (a^(-1) * b) (mod m).

Так как a * a^(-1) ≡ 1 (mod m), то остается:

x ≡ (a^(-1) * b) (mod m).

Найдите остаток от деления (a^(-1) * b) на m. Это будет решение линейного сравнения.

Например, рассмотрим линейное сравнение 3x ≡ 2 (mod 7):

Найдем НОД(3, 7) с помощью алгоритма Евклида. Получим НОД(3, 7) = 1, что означает, что уравнение имеет решение.

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

Умножим обе части исходного сравнения на 3^(-1):

(5 * 3 * x) ≡ (5 * 2) (mod 7).

Получаем: 15x ≡ 10 (mod 7).

Найдем остаток от деления 10 на 7, что равно 3. Таким образом, решением линейного сравнения 3x ≡ 2 (mod 7) является x ≡ 3 (mod 7).

Алгоритм решения линейных сравнений может быть обобщен и применен для любых линейных сравнений с различными значениями a, b и m.

Схемы алгоритмов и описание функций.

Ниже приведены схемы алгоритмов и описание основных функций программы для каждой из задач лабораторной работы №1.

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

Схема алгоритма:

Алгоритм EuclideanGCD(a, b):

Пока b не равно 0:

Вычислить остаток от деления a на b и сохранить его в переменной r.

Присвоить a значение b.

Присвоить b значение r.

Вернуть a.

Описание функции:

def EuclideanGCD(a, b):

while b != 0:

r = a % b

a = b

b = r

return a

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

Схема алгоритма:

Алгоритм SieveOfEratosthenes(N):

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

Пока i^2 <= N:

Если i помечено как простое:

Для каждого числа j в интервале от i^2 до N с шагом i:

---

Пометить j как составное.

Увеличить i на 1.

Вернуть список всех простых чисел.

Описание функции:

def SieveOfEratosthenes(N):

primes = [True] * (N + 1)

primes[0] = primes[1] = False

i = 2

while i * i <= N:

if primes[i]:

for j in range(i * i, N + 1, i):

primes[j] = False

i += 1

prime_numbers = [num for num, is_prime in enumerate(primes) if is_prime]

return prime_numbers

Вычисление функции Эйлера для положительного целого числа:

Схема алгоритма:

Алгоритм EulerTotientFunction(n):

Инициализировать переменную count со значением 0.

Для каждого числа i в интервале от 1 до n:

Если i и n взаимно просты:

Увеличить count на 1.

Вернуть count.

Описание функции:

def EulerTotientFunction(n):

count = 0

for i in range(1, n + 1):

if EuclideanGCD(i, n) == 1:

count += 1

return count

Решение линейных сравнений:

Схема алгоритма:

Алгоритм LinearCongruenceSolver(a, b, m):

Найти НОД(a, m) и сохранить его в переменной d.

Если b не делится нацело на d:

Решений нет.

Иначе:

Найти одно частное решение x0, используя расширенный алгоритм Евклида.

Выписать общее решение в виде x = x0 + (k * m) / d, где k - целое число.

Вернуть общее решение.

Описание функции:

def LinearCongruenceSolver(a, b, m):

d = EuclideanGCD(a, m)

if b % d != 0:

return "No solution"

else:

x0, y0 = ExtendedEuclideanAlgorithm(a, m)

x = (x0 * (b // d)) % m

return x

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

Выводы по работе

В ходе выполнения лабораторной работы №1 были решены следующие задачи:

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

Нахождение последовательности простых чисел с использованием алгоритма Эратосфена.

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

Решение линейных сравнений.

Для решения каждой задачи были представлены соответствующие схемы алгоритмов и описания основных функций программы.

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

Алгоритм Эратосфена позволяет эффективно находить последовательность простых чисел до заданного числа N. Он работает на основе пошагового вычеркивания составных чисел из списка, начиная с 2. Полученный список содержит только простые числа.

Функция Эйлера представляет собой функцию

---

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

Решение линейных сравнений с помощью алгоритма нахождения обратного элемента и расширенного алгоритма Евклида позволяет найти все решения такого сравнения. Результатом является общее решение, выраженное через одно частное решение и параметры, определяющие множество всех решений.

Лабораторная работа позволила познакомиться с основными математическими концепциями и алгоритмами, используемыми в вычислительной математике. Реализация данных алгоритмов в виде программы позволяет эффективно и точно решать соответствующие задачи.

---