Лаб_04
.odtМИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ,
СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
(СПбГУТ)
ФАКУЛЬТЕТ ИНФОКОММУНИКАЦИОННЫХ СЕТЕЙ И СИСТЕМ (ИКСС)
КАФЕДРА ЗАЩИЩЕННЫХ СИСТЕМ СВЯЗИ (ЗСС)
_______________________________________________________________________________
Отчет
по практической работе №4
Вариант №23
«Теория чисел в криптографии»
Выполнил студент группы ИКБ-14:
Травкина Е.
Проверил:
Кушнир Дмитрий Викторович
Санкт-Петербург
2023
Задание 1.
Пояснения. Мультипликативная инверсия (нахождение обратного элемента по модулю) в Zn (на множестве целых чисел). Два числа a и b мультипликативно инверсны друг другу, если a·b = 1 (mod n). Мультипликативную инверсию числа (обратный элемент по модулю) для числа “a” часто записывают в виде: a-1
Например, если модуль равен 10, то мультипликативная инверсия 3 есть 7. Другими словами, мы имеем 3·7 (mod 10) = 1 или 3·7 = 1(mod 10).
В модульной арифметике целое число может иметь, а может не иметь мультипликативную инверсию. Целое число и его мультипликативная инверсия сравнимы с 1 по модулю n. Может быть доказано, что “a” имеет мультипликативную инверсию в Zn, если только НОД (n, a) = 1, т.е. если числа “n” и “a” не имеют общих множителей (взаимнопростые).
Нахождение мультипликативной инверсии для числа a по модулю b:
Способ 1.
Если НОД(a,b)=1, то существуют целые числа α и β, для которых верно равенство α·a+β·b = 1 (соотношение Безу). Данные числа (α и β) могут быть найдены по расширенному алгоритму Эвклида (см. предыдущую лабораторную работу).
Рассматривая соотношение α·a+β·b = 1, приведем его по модулю b: (α·a) mod b +(β·b) mod b= 1 => α·a= 1 mod b, т.е. коэффициент α и есть мультипликативная инверсия (обратный элемент).
Найдём обратный элемент a-1 для a=41 по модулю 167.
Проверяем, что НОД(41,167)=1, значит обратный элемент существует.
Находим соотношение Безу для чисел a=41 и b=167. => 41·(-57)+167· 14=1
Получаем: 41⋅ (-57)=1 mod 167. Ответ: a-1= 14 = 110 mod 167.
Способ 2.
Теорема Эйлера. Для любого модуля «m» и целого числа «a», взаимно простого с «m», справедливо сравнение aφ(m) ≡ 1mod m. Следствие: a-1 ≡ aφ(m)-1 mod m для взаимно простых «a» и «m».
Найдём обратный элемент a-1 для a=41 по модулю 167.
Проверяем, что НОД(41,167)=1, значит обратный элемент существует.
Находим φ(167)=166 (так как 167 простое число, а для простого p: φ(p)=p-1
Вычисляем aφ(m)-1 = 41φ(167)-1=41165=110 mod 167. Ответ: a-1=110 mod 167.
Проверка с помощью онлайн ресурса:
Задания 2.
Число n = 19 при делении на 16 дает в остатке 3. Какой остаток при делении на 12 даст число 3n?
Пусть n = 19, тогда 3n = 57. 57 mod 12 = 9
Ответ: 9
Какие остатки при делении на 24 могут иметь простое число и его квадрат?
2: 2^2 даёт остаток 4.
3: 3^2 даёт остаток 9.
5: 5^2 даёт остаток 1.
7: 7^2 даёт остаток 1.
11: 11^2 даёт остаток 1.
13: 13^2 даёт остаток 1.
17:17^2 даёт остаток 1.
19: 19^2 даёт остаток 1.
23: 23^2 даёт остаток 1.
Ответ: Остатки простого числа и квадрата при делении на 24 могут быть 1, 4 или 9.
Какие остатки при делении на p имеют квадраты и кубы целых чисел, если p = 5, p = 7?
Остатки квадратов при делении на 5: 0,1,4
Остатки квадратов при делении на 7: 0,1,2,4
Остатки кубов при делении на 5: любые цифры
Остатки квадратов при делении на 7: 0,1,6
Доказать, что остаток при делении квадрата нечётного натурального числа на 8 равен 1. (Примечание. Нечетное число можно представить в виде “2a+1”)
Нечетное натуральное число можно представить в виде: 2 * а + 1, где а некоторое натуральное число.
(2*а + 1)^2 = 4а^2 + 4а + 1 = 4а(а + 1) + 1.
4а(а + 1) делится на 8 без остатка, тк одно из этих выражений а или (а + 1) точно делится на 2
Ответ: остаток при делении квадрата нечетного натурального числа на 8 всегда равен 1.
Доказать, что сумма квадратов двух последовательных натуральных чисел при делении на 4 даёт остаток 1. (Примечание. Представьте первое число как «a», второе как «a+1» и проверьте на чётность сумму квадратов без 1.)
Представим последовательность натуральных чисел как 2а и 2а+1, тогда сумма их квадратов будет равна 4а²+4а²+4а+1=8а²+4а+1=4(2а²+1)+1 Выражение 4(2а²+1) делится на 4, т. к. состоит из произведения множителей, один из которых равен 4. Значит 4(2х²+1)+1 делится на 4 с остатком 1
Докажите, что сумма: 83+84+85+86+87 делится на 5 и на 85
83+84+85+86+87 = (83+87) + (84+86) + 85 = 170 + 170 + 85 = 425
425/5 = 85
Сумма делится на 5 и на 85, так как делится на 5 без остатка
Докажите для целых чисел «a» и «b», что если: 5a + 9b делится на 11, то и a + 4b также делится на 11.
Предположим, что 5a + 9b делится на 11, но a + 4b не делится на 11. Это означает, что существуют целые числа q и r такие, что:
5a + 9b = 11q + 4b = 11r + k, где k не равно нулю и меньше 11.
Мы можем выразить "a" из первого уравнения:
a = (11q - 9b)/5.
Подставим это выражение для "a" во второе уравнение:
(11q - 9b)/5 + 4b = 11r + k.
Упрощая выражение, получим:
11q + 16b = 55r + 5k.
Делим обе стороны на 11:
q + (16b)/11 = 5r + (k/11).
Поскольку левая часть является целым числом, то правая часть также должна быть целым числом. Но это возможно только тогда, когда k = 0. Таким образом, получаем, что a + 4b делится на 11, что противоречит нашему предположению.
Следовательно, мы доказали, что если 5a + 9b делится на 11, то и a + 4b также делится на 11.
Докажите, что любое простое число, большее 3, можно записать в одном из двух видов: (6n + 1) либо (6n – 1), где n ‑ натуральное число.
Остаток p при делении на 6 равен 1 или 5. Тогда существует натуральное число n, такое что p = 6n + 1 или p = 6n + 5.
Действительно, если p = 6n + 1, то p = 6n + 6 - 5, что можно записать как p = 6(n+1) - 5. Если p = 6n + 5, то p = 6n + 6 - 1, что можно записать как p = 6(n+1) - 1.
В обоих случаях p может быть записано в одном из двух видов: (6n + 1) либо (6n – 1).
Найти все такие натуральные числа p, что p и (5p + 1) ‑ простые.
Ответ: р = 2
Найти все такие натуральные числа p, что p и 3p² + 1 ‑ простые.
Если p нечётно, то 3p² + 1 чётно.
Ответ: p = 2.
p > 3 и p ‑ простое число, будет ли хотя бы одно из чисел p + 1 и p ‑ 1
а) делиться на 4? Рассмотрим числа p – 1, p, p + 1, p + 2. Из четырёх последовательных чисел одно обязательно делится на 4, но это не p и не p + 2 (оба эти числа нечётны). Значит, одно из чисел p + 1 или p – 1 будет делиться на 4. б) делится на 5? при p = 13 оба эти числа на 5 не делятся
Ответ: а)Будет б)Не обязательно
Может ли число 3821^(14567) - 1 быть простым?
Для того чтобы ответить на этот вопрос, нам нужно воспользоваться малой теоремой Ферма, которая утверждает, что если p - простое число, а a - целое число, не делящееся на p, то:
a^(p-1) ≡ 1 (mod p)
Здесь ≡ означает "сравнимо по модулю".
Таким образом, если число 3821^(14567) - 1 простое, то оно должно удовлетворять этому уравнению:
3821^(14567 - 1) ≡ 1 (mod 3821^(14567) - 1)
Найдите все простые числа, которые отличаются на 17.
Ответ: 2 и 19
Докажите, что для любых натуральных чисел a и b верно равенство НОД(a, b)*НОК(a, b) = ab.
Из определения НОД следует, что a = a' НОД(a, b), b = b' НОД(a, b), где НОД(a', b') = 1. Из определения НОК следует, что НОК(a, b) = a'b' НОД(a, b).
Поэтому НОД(a, b)НОК(a, b) = a'b' НОД(a, b)НОД(a, b) = ab.
Доказать, что числа «27x + 4» и «18x + 3» взаимно просты при любом натуральном x.
Допустим, что у этих чисел есть общий делитель d, где d больше единицы. Тогда:
d | (27x + 4) и d | (18x + 3)
Мы можем выразить эти числа в виде:
27x + 4 = 3(9x + 1) + 1
18x + 3 = 3(6x + 1)
Заметим, что у обоих чисел есть общий делитель 3. Поэтому, если d не равно 3, то он не может быть общим делителем обоих чисел.
Допустим, что d равно 3. Тогда:
3 | (27x + 4) и 3 | (18x + 3)
Это означает, что их можно выразить в виде:
27x + 4 = 3(9x + 1) + 1
18x + 3 = 3(6x + 1)
Таким образом, мы видим, что они имеют разные остатки при делении на 3, и поэтому не могут иметь общий делитель, больший единицы
a и b ‑ натуральные числа. Известно, что a^2 + b^2 делится на ab. Докажите, что a = b.
Пусть d = НОД(a, b) – наибольший общий делитель чисел a и b, a = du, b = dv. Сокращая на d², получим, что u² + v² делится на uv. Но НОД(u² + v², uv) = 1, так как u и v взаимно просты. Следовательно, uv = 1. Значит, u = v = 1, a = b = d.
Изменятся ли частное и остаток, если делимое и делитель увеличить в 3 раза?
Частное изменилось в части остатка, т. е остаток увеличился в три раза; Вывод: если делимый и делитель увеличить на одинаковое количество раз, то и в частном остаток увеличится во столько же раз.
Найдите остаток от деления 2^100 на 3.
Ответ: 1
Может ли сумма трёх последовательных натуральных чисел быть простым числом?
Сумма трех последовательных натуральных чисел кратна 3 и больше 3. Действительно, n + (n + 1) + (n + 2) = 3(n + 1). Поэтому ответ- нет
Докажите, что (n^3 – n) делится на 24 при любом нечётном n. (Замечание: представьте в виде разности квадратов)
Разложим данное выражение на множители:
n^3 - n = n * (n^2 - 1) = n * (n - 1) * (n + 1) =
= (n - 1) * n * (n + 1).
Мы получили, что данное выражение при любом n есть произведение трёх последовательных натуральных чисел. Одно из них будет обязательно делиться на 3, а значит и все выражение будет делиться на 3.
Если n - нечетное число, то его можно представить в виде:
n = 2 * k + 1, k - натуральное число.
Подставим это представление в разложение исходного выражения:
(n - 1) * n * (n + 1) = 2 * k * (2 * k + 1) * (2 * k + 2) =
= (2 * k + 1) * 4 * k * (k + 1).
Так как k и (k + 1) два последовательных натуральных числа, то одно из них обязательно делится на 2. Следовательно, все выражение будет делится на 4 * 2 = 8.
Мы доказали делимость выражения на 3 и на 8, а значит и делимость на 3 * 8 = 24.