5.1.4 Китайская теорема об остатках
Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, если известны его вычеты по этим модулям. Этот результат был известен еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложена китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным криптографическим инструментом.
Она формулируется следующим образом.
Пусть m1, m2, … , m t – модули (целые числа, большие 1), которые являются попарно взаимно простыми, т.е. НОД (mi, mj,) = 1 при i j.
Пусть а1, а2, … , а t – тоже целые числа, такие, что 0 ≤ а i ≤ m i.
Пусть М = m1 • m2 • … • m t – произведение всех m i . Обозначим М i = M / m i.
И пусть N i будет обратным к М i (mod m i), i = 1, 2, … , t, т.е.
М i • N i 1 (mod m i).
Так как НОД (М i , m i) = 1, то обратный элемент N i существует и легко находится по алгоритму Евклида из соотношения
М i • N i + m i • n i = 1, i = 1, 2, … , t.
Сравнения х а i (mod m i), i = 1, 2, … , t, имеют в интервале
[0, M – 1] единственное общее решение
х = a i • N i • М i (mod M).
Рассмотрим частный случай. Пусть М = m1 • m2 , где m1 и m2 – взаимно простые числа. Тогда для произвольных целых а1 < m 1 и а 2 < m 2 существует единственное число х, х < М, такое, что
х а 1 (mod m 1) и х а 2 (mod m 2).
Чтобы найти значение решения х, сначала используют алгоритм Евклида для вычисления значений N 1 и N 2 , таких, что
М 1 • N 1 1 (mod m 1) и М 2 • N 2 1 (mod m 2).
Здесь M m 1 • m 2 M
M 1 = = = m 2 ; M 2 = = m 1.
m 1 m 1 m 2
Затем вычисляют значение
х = (a 1 • N 1 • М 1 + a 2 • N 2 • М 2 ) (mod M).
Пример. Решить систему из двух сравнений
х 1 (mod 5),
х 10 (mod 11)
и найти общее решение х по модулю 55.
Здесь: m 1 = 5; m 2 = 11; M = m 1 • m 2 = 5 • 11 = 55;
а 1 = 1; а 2 = 10; M 1 = М / m 1 = m 2 = 11; M 2 = М / m 2 = m 2 = 5.
Найдем значения N 1 и N 2, обратные к M 1 и M 2 сответственно по mod m 1 и mod m 2 :
М 1 • N 1 1 (mod m 1), 11 • N 1 1 (mod 5) N 1 = 1,
М 2 • N 2 1 (mod m 2), 5 • N 2 1 (mod 11) N 2 = 9.
Вычислим общее значение
х = (a 1 • N 1 • М 1 + a 2 • N 2 • М 2 ) (mod M) =
= (1 • 11 • 1 + 10 • 5 • 9 ) (mod 55) = (11 + 450) (mod 55) =
= 461 (mod 55) = 21 (mod 55).
Итак, х = 21 (mod 55).
- Дискретная математика
- 6.050102 “Компьютерная инженерия” содержание
- 1 Теория множеств 7
- 2 Математическая логика 15
- 3 Формальные теории 35
- 4 Теория графов 47
- 5 Элементы теории чисел 80
- 6 Теория алгоритмов 121
- Введение
- 1 Теория множеств
- 1.1 Множества и подмножества
- 1.1.1 Элементы множества
- 1.2 Аксиомы теории множеств
- 1.3 Способы задания множеств
- 1.4 Операции над множествами
- 1.5 Элементы алгебры множеств
- 1.5.1 Определение алгебры множеств
- 1.5.2 Основные законы алгебры множеств
- 1.5.3 Принцип двойственности
- 2 Математическая логика
- 2.1 Функции алгебры логики (булевые функции)
- 2.1.1 Способы задания булевых функций
- 2.1.2 Логические функции одной переменной
- 2.1.3 Логические функции двух переменных
- 2.2.6 Функционально полные системы булевых функций
- 2.3 Алгебра буля
- 2.3.1 Определение алгебры. Теорема Стоуна
- 2.3.2 Законы алгебры логики
- 2.3.3 Разложения функций по переменным
- 2.3.4 Приведение логических функций
- 2.3.5 Импликанты и имплициенты булевых функций
- 2.3.6 Методы минимизации логических функций
- 2.4 Алгебра жегалкина
- 2.4.1 Преобразование функций в алгебре Жегалкина
- 2.4.2 Переход от булевой алгебры к алгебре Жегалкина
- 3 Формальные теории
- 3.1 Основные принципы построения формальных теорий исчисления
- 3.2 Определение исчисления высказываний
- 3.2.1 Метатеоремы исчисления высказываний
- 3.2.2 Схемы исчисления высказываний
- 3.3 Исчисление предикатов
- 3.3.1 Определение формальной теории pl
- 3.3.2 Принцип резолюции в исчислении предикатов
- 3.3.3 Схемы доказательств в исчислении предикатов
- 4 Теория графов
- 4.1 История теории графов
- 4.2 Основные определения
- 4.3 Способы представления графов
- 4.3.1 Матрицей смежности
- 4.3.2 Матрицей инцидентности
- 4.4 Пути в графах
- 4.4.1 Задача о кратчайшем пути
- 4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе
- 4.5 Транспортные сети
- 4.5.1 Потоки в транспортных сетях
- 4.5.2 Задача нахождения наибольшего потока в транспортной сети
- 4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети
- 4.5.4 Транспортная задача
- 4.6 Обходы в графах
- 4.6.1 Эйлеровы графы
- 4.6.2 Алгоритм Флёри нахождения эйлерова цикла
- 4. Если получился цикл, но не ейлеров, то отбрасываем данную последнюю вершину и повторяем пункт 2.
- 4.6.3 Гамильтоновы циклы
- 4.6.4 Метод ветвей и границ.
- 4.6.5 Метод ветвей и границ в задаче о коммивояжёре
- 4.7 Деревья
- 4.7.1 Построение экономического дерева
- 4.7.2 Алгоритм Краскала
- 5 Элементы теории чисел
- 5.1 Модулярная арифметика
- 5.1.1 Алгоритм Евклида для нахождения наибольшего общего делителя
- 5.1.2 Вычисление обратных величин
- 5.1.3 Основные способы нахождения обратных величин
- 5.1.4 Китайская теорема об остатках
- 5.2 Кодирование
- 5.2.1 Оптимальное кодирование
- 5.3 Обнаружение и исправление ошибок
- 5.3.1 Общие понятия
- 5.3.2 Линейные групповые коды
- 5.3.2 Код Хэмминга
- 5.3.3 Циклические коды
- 5.3.4 Построение и декодирование конкретных циклических кодов
- 5.4 Сжатие информации
- 5.4.1 Исключение повторения строк в последующих строках
- 5.4.2 Алгоритм lzw
- 6 Теория алгоритмов
- 6.1. Основные понятия
- 6.1.1 Основные требования к алгоритмам
- 6.1.2 Блок–схемы алгоритмов
- 6.1.3 Представление данных
- 6.1.4 Виды алгоритмов
- 6.1.5 Правильность программ
- 6.1.6 Эффективность алгоритмов
- 6.1.7 Сходимость, сложность, надежность
- 6.2 Универсальные алгоритмы
- 6.2.1 Основные понятия
- 6.2.2 Машины Тьюринга
- 6.2.3 Рекурсивные функции
- 6.2.5 Тезис Черча-Тьюринга
- 6.2.6 Проблема самоприменимости
- 6.3 Языки и грамматики
- 6.3.1 Общие понятия
- 6.3.2 Формальные грамматики
- 6.3.3 Иерархия языков
- 6.4 Параллельные вычисления
- Рекомендованная литература