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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:06, 23 апреля 2016.

Теорема о существовании решения

TemplateTheoremIcon.svg Теорема Теорема

Пусть - попарно взаимопростые положительные, а - целые. Система сравнений

имеет решение, причем все решения системы сравнимы по модулю [1].

Доказательство

Без ограничения общности будем считать, что в системе каждое принимает значение от 0 до . Тогда существует ровно различных систем такого вида. Столько же существует и целых чисел, принадлежащих множеству . Так как каждое число из является решением некоторой системы, то общее число решений систем на множестве равно числу этих систем. Поэтому для доказательства теоремы достаточно показать, что в нет двух чисел, являющихся решениями одной и той же системы вида. Сделаем это методом от противного. Допустим, что некоторая система имеет такие решения и , что . В этом случае разность удовлетворяет неравенствам , и является решением системы сравнений

Из последнего следует, что каждое делит , и, следовательно, входит в каноническое разложение на простые множители. Поэтому, , что противоречит . Таким образом, каждая система имеет не более одного решения среди целых неотрицательных чисел из . Теорема доказана.


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

TemplateTheoremIcon.svg Теорема Китайская теорема об остатках
Пусть - взаимно простые положительные, - целые, . Единственным решением системы сравнений
на множестве является , где и для
Доказательство

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


Применение

Разложение в прямую сумму примарных колец

- кольцо вычетов

изоморфно примарной сумме колец.

Для доказательства изоморфизма:

  1. Гомоморфизм с нулевым ядром ("на все множество"; если не "на все" некоторые элементы не будут иметь прообраза)
CRT-1.PNG

Рассмотрим (элемент декартова преобразования)

Обязательно должен иметь прообраз отображения

Возьмем элемент и найдем (все элементы попарно взаимопросты выполняется CRT)

Возьмем решение системы уравнений

По определению

Т.о. свели операцию в большом кольце к операциям в примарных кольцах.

TemplateExampleIcon.svg Пример Пример

или

восстановление прообраза:


Применение в схеме RSA

- большие простые числа

(элемент прямой суммы)

- не зависят от (их можно посчитать заранее в дальнейшем просто подставлять )

уменьшаются размеры регистров расшифрования/зашифрования (выше скорость, меньше памяти).

CRT применяется как с криптографией с ОК, так и с криптографией с ЗК.

Список литературы

  1. ЛЕКЦИИ ПО АЛГЕБРЕ конечные: группы, кольца, поля и линейные пространства