МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет Инфокоммуникационных сетей и систем

Кафедра Защищенных систем связи

Дисциплина Математические основы защиты информации

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №10

Китайская теорема об остатках

10.03.01 Информационная безопасность

ФИО:

Группа

Преподаватель: Кушнир Д.В.

Санкт-Петербург

Содержание

Китайская теорема об остатках 3

Теоретическая часть по исследуемому вопросу

Китайская теорема об остатках

Согласно китайской теореме об остатках система уравнений:

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. Имеется не более 105 кубиков. Их поочерёдно располагают по 3, по 5 или по 7 в ряд. Последний ряд в некоторых случаях оказывается заполненным не полностью (несколько кубиков оказываются «лишними»). По количеству «лишних» кубиков определить их общее количество. 20 вариант, в ряд по 3 – 0; в ряд по 5 – 4; в ряд по 7 – 1;

2. 1. Спутник1 пролетает над городом в x1 час и имеет период обращения y1 часов. 2. Спутник2 пролетает над городом в x2 час и имеет период обращения y2 часов. 3.Спутник3 пролетает над городом в x3 час и имеет период обращения y3 часов. Определить, когда все три спутника пролетят одновременно и как часто это бывает. Использовать аналитический метод; использовать метод, основанный на Киатйской теореме об остатках.

Вариант 20 x1-4 x2-5 x3-6 y1-7 y2-8 y3-9

Ход работы

Задача 1. имеет единственное решение на промежутке [0...3*5*7-1] = [0...104] т.к. 0mod105 = 105;

Найдем решения перебором, для этого воспользуемся excel

Решение первого уравнения от 0 до 99: 0,3,6,7…96,99 Решение второго уравнения от 0 до 99: 4,9,14,19…94,99 Решение третьего уравнения от 0 до 99: 1,8,15,22…92,99

Задача 2.

Аналитический метод.

Составим уравнения, используя исходные данные:

x=4mod7 x=5mod8 x=6mod9

x = 4 + 7t 4+7t = 5mod8 7t = 1mod8 t = 1*7^-1mod8 t = 7 mod 8 t = 7+8u x = 4 + 7t = 4 + 7(7+8u) = 4+49+56u=53+56u 53+56u = 6 mod 9 56u=7mod9 7u=7mod9 u=1mod9 u=1+9v x = 53+56u = 53 + 56(1 + 9v)=53+56+504v=109+504v

Метод основанный на Китайской теореме об остатках:

M = 7*8*9 = 504

M1 = 504/7 = 72 m2 = 504/8 = 63 m3 = 504/9 = 56

N1 : 71y1=1mod7 = 1 n2 : 63y2=1mod8 = 7 n3 : 56y3=1mod9 = 5

X = 4*72*1+7*63*5+56*5*6=288+1205+1136 = 2629mod504 = 109mod504

Ответ: Спутники пролетят над городом примерно на 109 часу, далее это будет происходить с периодичностью 504 часа.