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

Глава 1. Теоретико-числовая база построения СОК

Вз 1. Сравнения и их основные свойства

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

Вз 3. Китайская теорема об остатках и её роль в представлении чисел в СОК

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

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

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

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

Вз 2. Основные методы и алгоритмы перехода от позиционного представления к остаткам

Вз 3. Восстановление позиционного представления числа по его остаткам

Вз 4. Расширение диапазона представления чисел

Глава 3. Программная эммуляция алгоритмов перевода чисел из СОК в ПСС и обратно и алгоритма RSA

Цитированная литература

Инженеры и программисты, а также математики знакомы с таким понятием как цифровая обработка сигналов. Напомним некоторые факты.

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

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

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

- в вычислении свёртки;

- в вычислении дискретного преобразования Фурье.

Цельже дипломной работы:

- установить взаимосвязь СОК и теории чисел;

- изучить СОК и методы перевода чисел из ПСС в СОК и обратно;

- разработать и выполнить программы на языке Paskal, содержащие различные методы перевода чисел из ПСС в СОК и обратно.

Дипломная работа состоит из введения, трёх глав и списка литературы.

Во введении даётся краткое обоснование поставленных задач.

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

Вторая глава посвящена представлению чисел в СОК и различным методам перевода чисел из СОК в ПСС и от ПСС в СОК.

Третья глава содержит программные разработки методов перевода чисел из ПСС в СОК и обратно.

Глава 1. Теоретико-числовая база построения СОК

Вз 1. Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на р различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение. Целые числа а и называются сравнимыми по модулю р, если разность чисел а тАУ делится на р, то есть, если . Соотношение между а, и р запишем в виде:

(1.1)

запись mod будет означать, что , числа а и тАУ вычеты.

Если разность а тАУ не делится на р, то запишем:

.

Согласно определению означает, что а делится на р.

Примеры:

, т. к. 101 тАУ 17 = 84, а или , т. к. числа 135 и 11 при делении на 4 дают остаток 3.

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

Определение: Целые числа а и называются сравнимыми по модулюр, если остатки от деления этих чисел на р равны.

Дадим основные свойства сравнений:

1. Рефлексивность отношения сравнимости:

2. Симметричность отношения сравнимости:

если, , то .

3. Транзитивность отношения сравнимости:

если , , то .

4. Если и k тАУ произвольное целое число, то .

5. Если и (k, p) = 1, то .

6. Если и k тАУ произвольное натуральное число, то .

7. Если , где k и р тАУ произвольные натуральные числа, то .

8. Если , , то и .

9. Если , , то .

10. Если , то при любом целом > 0, .

11. Если и - произвольный многочлен с целыми коэффициентами, то .

12. Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.

13. Если и , то .

14. Если , то множество общих делителей а и р совпадает с множеством общих делителей и р. В частности,

15. Если , , тАж, , то , где .

При делении целого числа на модуль р в остатке получается 0, 1, 2, 3,тАж, р тАУ 1 чисел.

Отнесём все целые числа, дающие при делении на р один и тот же остаток в один класс, поэтому получится р тАУ различных классов по модулю р.

В один класс попадут равноостаточные числа, они называются вычетами друг друга.

Обозначим через А₀ тАУ класс вычетов, которые при делении на р дают остаток 0.

Например, числа вида .

Через А₁ тАУ числа, дающие при делении остаток 1.

Например, числа вида .

Через А₂ тАУ числа, дающие при делении остаток 2.

Например, числа вида .

Через А_р-1 тАУ числа, дающие при делении остаток р тАУ 1.

Например, числа вида .

Полной системой вычетов по модулю р называется совокупность р-целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р: 0, 1, тАж, р тАУ 1. Множество {0, 1, тАж, р тАУ 1} называется полной системой наименьших неотрицательных вычетов по модулю р. Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р, есть полная система вычетов по модулю р. Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, тАж, р; полную систему наименьших по абсолютной величине вычетов:

при чётном р и

при р нечётном.

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

Число классов, взаимно простых с модулем р, равно значению функции Эйлера φ(р).

Вз 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 соответственно.

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

.

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

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

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

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

,

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

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

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

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

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

:

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

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

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

Вз 3. Китайская теорема об остатках и её роль в представлении чисел в СОК

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

Теорема. Пусть - попарно взаимно-простые числа, больше 1, и пусть . Тогда существует единственное неотрицательное решение по модулю Р следующей системы сравнений:

тАж, (3.1)

Другими словами, отображение, которое каждому целому числу х, , ставит в соответствие кортеж , где , , является биекцией кольца на декартово произведение

колец .

Существует много различных доказательств этой теоремы. Приведём конструктивное доказательство китайской теоремы об остатках.

Доказательство. Найдём число х, , удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа х вида где q₁ тАУ произвольное целое число. Для нахождения q₁ подставим значение х во второе сравнение системы, после чего получим откуда где - обратный мультипликативный элемент к по модулю . Такой элемент существует, так как Найденное таким образом q₁ можно записать в виде

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

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

(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 до тАУ 1: MOДINV(, );

q:=МОД(

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

4. q:=МОД(

5. Вернуть х.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

.

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

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

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

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

Например, при р = 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 означает операцию нахождения остатка от деления. Поэтому на компьютере с длиной слова 2³² можно выбрать

, ,, , ,

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

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

.

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

,

где и при .

Тогда ,

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

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

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

, где

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

Тогда

Вернёмся к общему случаю. Так как , удовлетворяют условиям (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) позволяют выполнять вычислении параллельно. Можно начать с присваивания

Вместе с этим смотрят:

10 способов решения квадратных уравнений

РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора

РЖнтегральнi характеристики векторних полiв

РЖнтерполювання функцiй

Автокорреляционная функция. Примеры расчётов