МОЗИ 4 семестр / Лабораторная 10 / ЗАДАНИЕ_МОЗИ_Лаб_10_(Китайская_теорема_об_остатках)
.docЛабораторная/Практика.
Китайская теорема об остатках
Согласно китайской теореме об остатках система уравнений:
x= 1 mod 2 x= 2 mod 3 x= 6 mod 7
Имеет единственное решение на промежутке [0... 2*3*7], если числа 2,3,7 — взаимно простые.
Найдем решение на промежутке от 0 до 42 (перебором):
Решения первого уравнения: 1,3,5,7,9,11,...37,39,41, ... Решения второго уравнения: 2,5,8,11,...38,41,... Решения третьего уравнения: 6,13,20,27,34,41,...
Итоговое решение x=41.
Найдём аналитически решение системы уравнений:
x=1 mod 13 x=4 mod 15 x=8 mod 19
Выразим x из первого уравнения:
Выражение x=1 mod 13, можно записать в виде:
x=1+13*t, где t - некоторое произвольное целое.
Подставляем выражение для x из первого уравнения во второе уравнение:
x = 4 mod 15 1+13t = 4 mod 15 13t = 3 mod 15 t = 3/13 mod15
В модульной арифметике "нет такого понятия как деление", вместо деления необходимо производить умножение на обратный элемент.
t = 3*(13)(-1) mod15
Обратный элемент находят с помощью расширенного алгоритма Эвклида, для небольших чисел в демонстрационных целях можно использовать метод перебора на основе определения обратного элемента:
1*13=13 mod 15 2*13=11 mod 15 3*13= 9 mod 15 4*13= 7 mod 15 5*13= 5 mod 15 6*13= 3 mod 15 7*13= 1 mod 15 ... т.е. t = 3*(13)(-1) =3*7 mod 15
t = 6 mod 15
раскроем модуль:
t = 6 + 15*u, где u - целое число.
теперь подставим это в выражение для х:
x = 1+13t = 1 + 13(6 + 15u) = 79 + 195u
(таким образом, мы получили выражение для «х» с учетом двух уравнений).
Подставим найденное выражение для х в третье уравнение:
79+195u=8 mod19
5u=5mod19
u=5/5mod19 (тут можно было бы тоже не делить на 5, а умножать на обратное к 5 число, но выражение запись 5*5(-1)mod 19 всегда равно 1 по определению обратного элемента, т.е. получаем:
u = 1 mod 19 раскрываем модуль:
u = 1 + 19v, где v - целое число.
Подставляем в выражение для х
Итого с учетом всех трёх уравнений:
x = 79 + 195u = 79 + 195*(1 + 19v) = 274+3705v
Решение на промежутке [0 ... 13*15*19]=274, но есть и другие решения системы, вне промежутка, которые можно получить, принимая в качестве v значения 0, 1, 2, 3, …, …, …, … (В качестве v можно брать и отрицательные числа, что необходимо для решения некоторых задач).
Типичные задачи, которые можно решить на основе подобных подходов:
Задача 1: Как часто стрелки часов (секундная, минутная, часовая) сходятся вместе.
Задача 2: В какие моменты времени несколько спутников с разным периодом обращения вокруг Земли будут одновременно пересекать заданную долготу.
Китайская теорема об остатках может использоваться и в криптографии, как для выполнения процедур шифрования, так и для криптоанализа.
Решение на основе Китайской теореме об остатках:
Задание.
Задача 1 (Методом перебора)
Имеется не более 105 кубиков. Их поочерёдно располагают по 3, по 5 или по 7 в ряд. Последний ряд в некоторых случаях оказывается заполненным не полностью (несколько кубиков оказываются «лишними»). По количеству «лишних» кубиков определить их общее количество.
|
Остаток кубиков при раскладывании: |
||
Варианты |
в ряд по 3 |
в ряд по 5 |
в ряд по 7 |
1 |
0 |
0 |
6 |
2 |
0 |
1 |
5 |
3 |
0 |
2 |
4 |
4 |
1 |
3 |
3 |
5 |
1 |
4 |
2 |
6 |
1 |
0 |
1 |
7 |
2 |
1 |
6 |
8 |
2 |
2 |
5 |
9 |
2 |
3 |
4 |
10 |
0 |
4 |
3 |
11 |
0 |
0 |
2 |
12 |
0 |
1 |
1 |
13 |
1 |
2 |
6 |
14 |
1 |
3 |
5 |
15 |
1 |
4 |
6 |
16 |
2 |
0 |
5 |
17 |
2 |
1 |
4 |
18 |
2 |
2 |
3 |
19 |
0 |
3 |
2 |
20 |
0 |
4 |
1 |
Задача 2
Спутник1 пролетает над городом в x1 час и имеет период обращения y1 часов.
Спутник2 пролетает над городом в x2 час и имеет период обращения y2 часов.
Спутник3 пролетает над городом в x3 час и имеет период обращения y3 часов.
-
Варианты
x1
x2
x3
y1
y2
y3
1
1
2
3
3
5
7
2
1
3
5
2
3
5
3
2
3
4
3
5
8
4
1
2
4
3
2
5
5
4
4
5
7
2
3
6
5
2
1
7
3
2
7
3
3
1
5
6
7
8
2
4
6
2
5
9
9
2
3
5
3
7
5
10
1
4
2
5
7
3
11
2
3
4
3
5
11
12
2
2
6
2
3
13
13
1
1
7
3
5
11
14
0
2
1
2
7
11
15
1
2
3
7
5
9
16
1
2
3
7
5
9
17
4
3
1
5
7
3
18
5
4
3
6
5
7
19
3
4
5
8
5
9
20
4
5
6
7
8
9
Определить, когда все три спутника пролетят одновременно и как часто это бывает:
Использовать аналитический метод;
Использовать метод, основанный на Китайской теореме об остатках (приведённый на «слайдах» ).
Отчет.
Содержание отчёта:
Стандартный титульный лист.
Теория по исследуемому вопросу, если есть в задании (достаточно использовать материалы задания самой лабораторной работы).
Формулировка задания на вычисления.
Шаги выполнения вычисления или доказательства.
Проверка правильности найденных решений, если применимо.
Отчет должен содержать текст программы для вычислений (формулы из ячеек EXCEL) – не скриншотом.
Отчёт должен содержать вывод промежуточных шагов выполнения алгоритма – можно скриншотом.
Файл с отчётом должен иметь название по следующему шаблону: Лаб_(номер лабы(две цифры))_(номер группы)_Фамилия1ИО_Фамилия2ИО_Фамилия3ИО. Пример: Лаб_01_ИКБ-72_ИвановДИ_ПетровЕН_СидоровЯЭ.