Математические основы системы остаточных классов (стр. 6 из 19)

Формулы (5.5) можно переписать следующим

,

,

,

Если это сделать, то вместо

констант как в (5.5), потребуется только k – 1 констант

Оценим с точки зрения вычислений на компьютере достоинства и недостатки последнего варианта формул (5.5) по сравнению с исходным вариантом этих формул.

Пусть

. Тогда для некоторого постоянного числа

с

.

Поэтому

. Таким образом,

. (5.6)

Формула (5.6) – это представление числа А по так называемому смешанному основанию, которое можно перевести в двоичный, либо десятичный формат. Если интервал [0; P) не является необходимым (напомним, что

), то после завершения процесса к нему можно добавить (или вычесть из него) соответствующее число, кратное Р. Преимущество метода, представленного формулами (5.5), состоит в том, что для вычисления используется только арифметика по модулю , которая уже встроена в алгоритмы этого класса. Более того, соотношения (5.5) позволяют выполнять вычислении параллельно. Можно начать с присваивания , затем, в момент j при сразу же получить для .

Важно отметить, что представление (5.6) по смешанному основанию пригодно для сравнения величин двух чисел, заданных в СОК. Так, если известно, что

, то можно сказать, будет ли , если сначала выполнить переход к и к , затем в соответствии с лексикографическим правилом проверить выполнение неравенств или и и т. д. Более того, нет необходимости переходить к двоичной системе счисления, если нужно всего лишь выяснить, будет ли меньше, чем .

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

.

Теорема. Примитивные корни по модулю р существуют тогда и только тогда, когда:

1)

,

2)

,

3)

,

где р – любое нечётное простое число,

.

Таким образом, при всех других р примитивных корней нет. Доказательство теоремы можно найти, например, в книге [ ]. Эта теорема позволяет фактически дать полное описание группы U(Zp) для произвольного модуля р.

Теорема. Пусть

- каноническое представление числа Р. Тогда . Группа - циклическая группа порядка , а - циклическая группа порядка 1 или 2 при l = 1 или l = 2 соответственно. Если , то она будет прямым произведением двух циклических групп, одной порядка 2, другой порядка 2^{l– 2}. Кроме того, число р обладает примитивными корнями тогда и только тогда, когда р = 2, р = 4, р = р^l или р = 2р^l , где р – нечётное простое число.

Как следствие отметим, что для

кольцо - поле тогда и только тогда, когда р – простое число, причём - область целостности. По изложенному материалу рассмотрим ряд примеров.

Пример. Пусть b обратно к а по модулю р. Проверить. Что b(2 – ab) обратно к а по модулю р² и что b²(3 – 2ab) обратно к а² по модулю р².

Решение. По условию

, следовательно , откуда , то есть . Вторую часть задачи можно решить непосредственным вычислением, учитывая, что (так как в кольце из х² = 0 следует, что , и можно применить это к х = 1 – abв .

Пример. Определим последовательность

, следующим образом: и .

Проверить, что

обратно к а по модулю . Какое число обратно к 11335 по модулю 2¹⁶?

Решение. Первая часть задачи фактически повторяет рассуждения примера 1.5. Для второй части задачи полагаем p = 2, а = 11335, b₀ = 1, k = 4. Тогда числом, обратным к а = 11335 по модулю 2¹⁶ будет число b₄, которое вычисляем последовательно:

Пример. Сколько элементов порядка 10 в следующей группе и каковы они? Z₂₅;

Решение. В группе Z₂₅ элементов порядка 10 нет, так как |Z₂₅| = 25, а 25 не делится на 10.

Глава 2. Математические модели модулярного представления и параллельной обработки информации

§ 1. Представление числа в СОК. Модульные операции

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

где , т. е. отображение F элементу элементов ставит в соответствие кодовое слово , где - i-я цифра, n – длина кода. С помощью обратного отображения F^-1, которое называют декодированием, так же можно определить систему счисления.