Xreferat.com » Рефераты по математике » Математические основы системы остаточных классов

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

всякого целого числа х вида где q1 – произвольное целое число. Для нахождения q1 подставим значение х во второе сравнение системы, после чего получим откуда где - обратный мультипликативный элемент к по модулю . Такой элемент существует, так как Найденное таким образом q1 можно записать в виде



для некоторого целого числа . Подставив значение в выражение


Теперь первые два сравнения могут быть заменены на одно


(3.2)


Применим теперь описанную процедуру к сравнению (3.2) и к одному из оставшихся сравнений системы (3.1). Повторяя этот процесс k – 1 раз, мы в конечном итоге найдём число х, удовлетворяющее всем сравнениям системы (3.1).

Докажем единственность решения системы (3.1). Воспользуемся методом от противного. Предположим, что существует другое решение системы (3.1). Тогда



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

Пример. Решим систему сравнений



Решение. Так как модули 13, 15, 19 попарно взаимно простые числа, то данная система имеет единственное решение по модулю . Сравнение соответствует диофантовому уравнению , где . Заменяя х во втором сравнении системы на , получаем , т. е. . К числу 13 обратным мультипликативным элементом по модулю 15 является число 7. Умножая последнее сравнение на 7 и, переходя в нём к вычетам по модулю 15, получим . Таким образом, . Следовательно, , при этом все числа вида являются решениями первых двух сравнений данной системы. Подставим в третье сравнение вместо х полученное выше значение или . Так как (5, 19) = 1, то или . Итак,


, то есть х = 274.


Исходя из конструктивного доказательства китайской теоремы об остатках, можно записать алгоритм решения системы линейных сравнений рассматриваемого вида следующим образом (греко-китайский алгоритм).

Вход: Пары , такие, что , , где каждое > 1 и (,) = 1 для и - короткие целые числа.

Выход: х – единственное наименьшее неотрицательное решение системы по модулю .

  1. Инициализация. Р:=1; х:=МОД(,) – подпрограмма нахождения остатка деления на .

  2. Цикл для i от 1 до n – 1: MOДINV(p, );


q:=МОД(

  1. х:= х + pq, где MOДINV – подпрограмма вычисления мультипликативного обратного элемента.

  2. q:=МОД(

  3. Вернуть х.

Несложный анализ времени работы данного алгоритма показывает, что



где - количество цифр числа Р, т. е. длина числа Р, при этом функция L ведёт себя как логарифм.


§ 4. Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по данному модулю


Вернёмся теперь к вопросу о мультипликативных обратных элементах в фактор-кольце Zp.

Теорема. Пусть , тогда класс имеет мультипликативный обратный элемент по модулю р тогда и только тогда, когда (, р) = 1.

Теорема. Характеристика λ конечного поля – простое число.

Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.

Первый способ. Из условия (а, р) = 1 получаем ах + ру = 1 или и, следовательно, х – мультипликативный обратный к а по модулю р.

Второй способ. Предварительно напомним теорему Эйлера:

(а, р) = 1, доказательство которой достаточно простое и мы его не приводим, так как его можно найти в любой книге по теории чисел. Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма. Если р – простое число и а – произвольное целое число, не делящееся на р, то .

Следствие. В кольце Zp классов вычетов по модулю р из следует, что

Таким образом, для вычисления мультипликативного обратного к классу по модулю р в случае, когда , достаточно возвести в степень k, где k = р – 2, если р – простое число, и в противном случае.

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

Из китайской теореме об остатках следует следующее

Утверждение. Пусть - каноническое представление числа р. Тогда функция, которая каждому классу ставит в соответствие кортеж , где для , является кольцевым изоморфизмом кольца класса вычетов по модулю р и кольца кортежей вида , где для . Более того, если обозначить через * любую из кольцевых операций + или · , то



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

,


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


.


Можно сделать вывод о том, что произвольное целое положительное число А, 0 < A < P, где и для , однозначно представимо своими наименьшими неотрицательными остатками по модулю , причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

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


§ 5. Числа Мерсенна, Ферма и операции над ними


При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах вида , где m – нечётное, именуемые числами Мерсенна. При простых значениях m = p число может оказаться простым, но может быть составным.

Например, при р = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при р = 11, 23, 29 числа - составные.

Числа вида , где k – положительное, обычно называют числами Ферма. При k = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537. Все остальные числа Ферма – составные. Все числа Мерсенна и Ферма – взаимно простые.

Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.

При работе же на двоичных компьютерах, иногда желательно выбирать модули в виде чисел Мерсенна


. (5.1)


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


, . (5.2)

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


,

.


Здесь и указывают на действия, которые с учётом условия (5.2) должны быть выполнены с отдельными компонентами кортежей и при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:


.


Эти операции могут быть эффективно выполнены, даже если больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разложить число по степеням 2. Для работы с модулями вида необходимо знать, при каких условиях число является взаимно простым с числом . Для этого существует простое правило:


. (5.3)

Формула (5.3) утверждает, в частности, что


.


Уравнение (5.3) следует из алгоритма Евклида и тождества


,


где mod означает операцию нахождения остатка от деления. Поэтому на компьютере с длиной слова 232 можно выбрать


, ,, , ,


что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до .

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

.


Если основание b = 2 и модули имеют вид , оба подхода сводятся к совсем простому способу. Рассмотрим двоичные представления числа А с блоками по бит:

,


где и при .

Тогда ,

Поскольку . Поэтому вычисляются путём сложения битовых чисел .

Обратный переход от СОК к позиционной системе счисления выполняется немного сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т. е. разложения чисел на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от к А, необходимо иметь другое доказательство китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании констант , где . (5.4)

Константы можно вычислить с помощью расширенного алгоритма Евклида, который по заданным i и j позволяет определить числа a и b такие, что , и можно положить . В частности, для величины, обратной к по модулю , легко получить сравнительно простую формулу

, где


и . Действительно, если , то . Поэтому при имеем ; а так как эти последние величины расположены между нулём и , должно быть .

Тогда



Вернёмся к общему случаю. Так как , удовлетворяют условиям (5.4), то можно выполнить присваивания


,

,

, (5.5)

.


Тогда число

(5.6)


будет удовлетворять условиям ,


для . (5.5)


Формулы (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, другой порядка 2l – 2. Кроме того, число р обладает примитивными корнями тогда и только тогда, когда р = 2, р = 4, р = рl или р = 2рl , где р – нечётное простое число.

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

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

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

Пример. Определим последовательность , следующим образом: и .

Проверить, что обратно к а по модулю . Какое число обратно к 11335 по модулю 216?

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



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

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

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


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


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

К любой кодовой системе применимы следующие требования:

- возможность представления в данной системе любой величины в рассматриваемом, заранее назначенном диапазоне;

- единственность представления – любая кодовая комбинация соответствует одному и только одному числу в заданном диапазоне;

- простота оперирования с числами в данной системе счисления.

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

Всякое представление чисел рабочего диапазона является лишь составным элементом соответствующей машинной арифметики и не может рассматриваться отдельно от неё. Арифметические свойства той или иной системы счисления прежде всего определяются характером межразрядных связей, появляющихся в ходе выполнения операций над кодовыми словами. Исследования показали, что в рамках обычной позиционной системы счисления (ПСС) значительного ускорения выполнения операций добиться невозможно. Это объясняется тем, что в ПСС значение разряда любого числа, кроме младшего, являющегося результатом двухместной арифметической операции, зависит не только от значения одноимённых операндов, но и от всех младших разрядов, т. е. ПСС обладает строго последовательной структурой. Сегодня, предпочтение отдаётся вычислительным структурам, обладающими способностями к параллельной обработке информации. Этими особенностями обладают непозиционные коды с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий. Эта мысль зародилась в середине 50-х годов прошлого века, когда чешские учёные М. Валах и Л. Свобода в своих исследованиях в области непозиционных систем счисления рассматривают представление чисел в виде набора остатков от деления на выбранные натуральные модули – основания системы. Подобную систему счисления стали называть системой остаточных классов (СОК) или модулярной системой счисления (МСС). Вслед за чешскими учёными возможность применения этой системы в ЭВМ рассмотрена в исследованиях американских учёных Айкена, Семона и Гарнера.

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

, . (1.1ґ)


Возможность такого представления числа определяется теоремой о делении с остатком в кольце целых чисел.

Теорема. Если , то существуют единственные


, такие, что

(1.2ґ)


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

Установить взаимно-однозначное соответствие между целыми числами из диапазона [0, P) и их остатками позволяет китайская теорема об остатках.

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

Пусть операнды А и В, а также результаты операций сложения и умножения А + В и А·В представлены соответственно остатками , , по основаниям , причём оба числа и результаты находятся в диапазоне [0, P), то есть


,

,

, (1.3ґ)

,

и , , , .


Выражения (1.3) можно переписать в виде


(1.4ґ)

. (1.5ґ)


Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.

Действительно, на основании (1.1ґ) можно переписать в виде



Из представления А и В по теореме о делении с остатком (1. 2ґ) следует, что


, , , .

Тогда .

Откуда, .

В случае умножения .

Тогда


.


Следовательно, .

Примеры.

Даны: р1 = 2, р2 = 3, р3 = 5, р4 = 7. А = (0, 0, 3, 4), В = (1, 1, 2, 0).

Найти: А+В, А – В, АВ.

Решение.


А+В = (0, 0, 3, 4) + (1, 1, 2, 0) = (1, 1, 0, 4).

АВ = (0, 0, 3, 4)· (1, 1, 2, 0) = (0, 0, 1, 0).

А – В = (0, 0, 3, 4) – (1, 1, 2, 0) = (1, 2, 1, 4).


В отличие от позиционной системы счисления (ПСС), в которой число А представляется в виде


, (1.6ґ)

где N – основание ПСС , значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным.

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

Перевод чисел из ПСС в СОК при помощи выражения (1.1ґ) связан с реализацией операции деления, поэтому использование данного метода неэффективно.

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

Исследования СОК выявили целый ряд её преимуществ.

  1. Максимальный параллелизм. Для оценки уровня параллелизма системы счисления вводится специальный показатель


, (1.7ґ)

где k – длина кода системы, n(v) – количество поразрядных показателей параллелизма , не меньших заданного порога , причём , где ni – максимально возможное число пар цифр оказывающих влияние на значение суммы в ходе её формирования на языке данного кода. Для СОК показатель параллелизма принимает максимально возможное значение . Это

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: