Математические основы системы остаточных классов

дипломная работа

§ 2. Теорема о делении с остатком. Алгоритм Евклида

Рассмотрим пример. Пусть р = 6.

Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

r = 0;

r = 1;

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

,

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

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

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

Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством , где L(a) и L(b) - число цифр в а и b соответственно. В правом столбце этого алгоритма каждый остаток выражен через . Надо вычислить и . Очевидно, что и . Сравнивая обе части на i-м шаге, получим

откуда получается следующая индуктивная процедура вычисления и

:

Пример. Применим расширенный алгоритм Евклида к числам а = 342, b = 612. Весь алгоритм представим в виде следующей таблицы.

Расширенный алгоритм Евклида

Номер

итерации

q

A0

a1

x0

x1

Y0

y1

0

-

342

612

1

0

0

1

1

0

612

342

0

1

1

0

2

1

342

270

1

-1

0

1

3

1

270

72

-1

2

1

-1

4

3

72

54

2

-7

-1

4

5

1

54

18

-7

9

4

-5

6

3

18

0

9

-34

-5

19

Заметим, что равенство выполняется на каждом шаге итерации. Алгоритм выдаёт d = 18, x = 9, y = -5 и тогда 18=342•9 + 612•(-5).

Делись добром ;)