Дипломная работа: Математические основы системы остаточных классов

r = 2;

r = 3;

r = 4;

r = 5;

где через r обозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема : Разделить число на число , , с остатком, значит, найти пару целых чисел q и r , таких, что выполняются следующие условия: .

Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5, 6}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как ; фактор-множество

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули . Чаще всего числа выбирают из множества простых чисел.

Пусть …, .

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. где , то кольцо Z , по определению, является евклидовым. Таким образом, в качестве чисел можно выбрать остатки от деления числа А на р _i соответственно.

Рассмотрим гомоморфное отображение:

.

Тогда каждому целому числу А можно поставить в соответствие кортеж наименьших неотрицательных вычетов по одному из соответствующих классов.

Важно отметить, что при том нет никакой потери информации при условии, что , так как всегда, зная можно восстановить, как мы увидим позже само число А . Поэтому кортеж можно рассматривать как один из способов представления целого числа А в компьютере – модулярное представление или представление в системе остаточных классов (СОК).

Для дальнейшего нам требуется расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа х и у , такие, что .

Действительно, пусть d – наименьшее целое положительное число вида , например, , где числа х ₀ и у ₀ не обязательно определены однозначно. Существование числа d следует только из принципа полной упорядоченности. Очевидно, что d > 0. Остаётся показать, что . Для этого надо проверить выполнение двух условий: а) и ; б) если и , то . Допустим, что свойство а) не выполняется и для определённости положим, что |. Тогда по теореме о делении с остатком , и, следовательно,

,

что противоречит минимальности d . Выполнение свойства б) проверяется непосредственно:

Рассмотрим теперь расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя . Значения х и у вычисляются в серии шагов, в каждом из которых мы выражаем а _i (вычисленное в процессе работы алгоритма Евклида) в форме . А именно, рассмотрим последовательность

В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения (а, b ), не превосходит числа цифр в меньшем из чисел а и b , умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.