МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ФИЗИКО-МАТЕМАТИЧЕСКИЙ
КАФЕДРА АЛГЕБРЫ
Утверждена приказом по университету Допущена к защите
от ____________________№_________ «____» ______________200__г.
Зав.кафедрой алгебры,
к. ф.-м. наук, доц. Копыткова
Людмила Борисовна
М. П.
ДИПЛОМНАЯ РАБОТА
«МАТЕМАТИЧЕСКИЕ ОСНОВЫ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ»
Рецензенты: Выполнила:
___________________________ Пивоварова Елена Николаевна
___________________________ студентка 5 курса, гр. «Б»
специальности математика
очной формы обучения
Дата защиты: Научный руководитель:
«______» __________________ Копыткова Людмила Борисовна
к. ф.-м. н., доцент
Ставрополь, 2004 г.
Оглавление
Введение
Глава 1. Теоретико-числовая база построения СОК
§ 1. Сравнения и их основные свойства
§ 2. Теорема о делении с остатком. Алгоритм Евклида
§ 3. Китайская теорема об остатках и её роль в представлении чисел в СОК
§ 4. Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по данному модулю
§ 5. Числа Мерсенна, Ферма и операции над ними
Глава 2. Математические модели модулярного представления и параллельной обработки информации
§ 1. Представление числа в СОК. Модульные операции
§ 2. Основные методы и алгоритмы перехода от позиционного представления к остаткам
§ 3. Восстановление позиционного представления числа по его остаткам
§ 4. Расширение диапазона представления чисел
Глава 3. Программная эммуляция алгоритмов перевода чисел из СОК в ПСС и обратно и алгоритма RSA
Цитированная литература
Введение
Инженеры и программисты, а также математики знакомы с таким понятием как цифровая обработка сигналов. Напомним некоторые факты.
Сигнал называется цифровым, если область значений последовательности ограничена конечным множеством действительных или комплексных чисел.
Обработка сигналов универсальными цифровыми вычислительными машинами или специализированными цифровыми процессорами осуществляется путём выполнения ряда вычислительных операций над последовательностями чисел. В настоящее время существует несколько алгоритмов, предназначенных для использования в области цифровой обработки сигналов. Здесь же немалую роль играет система остаточных классов, основанная на элементарной теории чисел.
Вообще, идею теории чисел для получения алгоритмов вычислений используют в 2-х наиболее важных направлениях обработки сигналов:
- в вычислении свёртки;
- в вычислении дискретного преобразования Фурье.
Цель
же дипломной работы:
- установить взаимосвязь СОК и теории чисел;
- изучить СОК и методы перевода чисел из ПСС в СОК и обратно;
- разработать и выполнить программы на языке Paskal, содержащие различные методы перевода чисел из ПСС в СОК и обратно.
Дипломная работа состоит из введения, трёх глав и списка литературы.
Во введении даётся краткое обоснование поставленных задач.
Первая глава содержит известные факты теории чисел в той мере, в какой они будут применяться в дальнейшем. Здесь излагаются самые элементарные понятия теории чисел, в частности, сравнения и их свойства, различные теоремы. А также главная теорема в СОК – китайская теорема об остатках.
Вторая глава посвящена представлению чисел в СОК и различным методам перевода чисел из СОК в ПСС и от ПСС в СОК.
Третья глава содержит программные разработки методов перевода чисел из ПСС в СОК и обратно.
Глава 1. Теоретико-числовая база построения СОК
§ 1. Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число p
и будем рассматривать остатки при делении на р
различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение
. Целые числа а
и b
называются сравнимыми по модулю р
, если разность чисел а –
b
делится на р
, то есть, если . Соотношение между а,
b
и р
запишем в виде:
(1.1)
запись modp
будет означать, что , числа а
и b
– вычеты.
Если разность а –
b
не делится на р
, то запишем:
.
Согласно определению означает, что а
делится на р
.
Примеры
:
, т. к. 101 – 17 = 84, а или , т. к. числа 135 и 11 при делении на 4 дают остаток 3.
Теорема
. а
сравнимо с b
тогда и только тогда, когда а
и b
имеют одинаковые остатки при делении на р
, поэтому в качестве определения сравнения можно взять следующее:
Определение
: Целые числа а
и b
называются сравнимыми по модулю
р
, если остатки от деления этих чисел на р
равны.
Дадим основные свойства сравнений:
1. Рефлексивность отношения сравнимости:
2. Симметричность отношения сравнимости:
если, , то .
3. Транзитивность отношения сравнимости:
если , , то .
4. Если и k
– произвольное целое число, то .
5. Если и (k, p
) = 1, то .
6. Если и k
– произвольное натуральное число, то .
7. Если , где k
и р
– произвольные натуральные числа, то .
8. Если , , то и .
9. Если , , то .
10. Если , то при любом целом n
> 0, .
11. Если и - произвольный многочлен с целыми коэффициентами, то .
12. Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.
13. Если и , то .
14. Если , то множество общих делителей а
и р
совпадает с множеством общих делителей b
и р
. В частности,
15. Если , , …, , то , где .
При делении целого числа на модуль р
в остатке получается 0, 1, 2, 3,…, р
– 1 чисел.
Отнесём все целые числа, дающие при делении на р
один и тот же остаток в один класс, поэтому получится р
– различных классов по модулю р
.
В один класс попадут равноостаточные числа, они называются вычетами друг друга
.
Обозначим через А
0
– класс вычетов, которые при делении на р
дают остаток 0.
Например, числа вида .
Через А
1
– числа, дающие при делении остаток 1.
Например, числа вида .
Через А
2
– числа, дающие при делении остаток 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
соответственно.
Рассмотрим гомоморфное отображение:
.
Тогда каждому целому числу А
можно поставить в соответствие кортеж наименьших неотрицательных вычетов по одному из соответствующих классов.
Важно отметить, что при том нет никакой потери информации при условии, что , так как всегда, зная можно восстановить, как мы увидим позже само число А
. Поэтому кортеж можно рассматривать как один из способов представления целого числа А
в компьютере – модулярное представление или представление в системе остаточных классов (СОК).
Для дальнейшего нам требуется расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а
и b
одновременно не равны нулю, то существуют целые числа х
и у
, такие, что .
Действительно, пусть d
– наименьшее целое положительное число вида , например, , где числа х
0
и у
0
не обязательно определены однозначно. Существование числа d
следует только из принципа полной упорядоченности. Очевидно, что d
> 0. Остаётся показать, что . Для этого надо проверить выполнение двух условий: а) и ; б) если и , то . Допустим, что свойство а) не выполняется и для определённости положим, что |. Тогда по теореме о делении с остатком , и, следовательно,
,
что противоречит минимальности d
. Выполнение свойства б) проверяется непосредственно:
Рассмотрим теперь расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя . Значения х
и у
вычисляются в серии шагов, в каждом из которых мы выражаем а
i
(вычисленное в процессе работы алгоритма Евклида) в форме . А именно, рассмотрим последовательность
В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения (а,
b
), не превосходит числа цифр в меньшем из чисел а
и b
, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.
Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством , где L(a
) и L(b
) – число цифр в а
и b
соответственно. В правом столбце этого алгоритма каждый остаток выражен через . Надо вычислить и . Очевидно, что и . Сравнивая обе части на i
-м шаге, получим
откуда получается следующая индуктивная процедура вычисления и
:
Пример
. Применим расширенный алгоритм Евклида к числам а
= 342, b
= 612. Весь алгоритм представим в виде следующей таблицы.
Расширенный алгоритм Евклида
Номер итерации |
q
|
A
0 |
a
1 |
x
0 |
x
1 |
Y
0 |
y
1 |
| 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).
§ 3. Китайская теорема об остатках и её роль в представлении чисел в СОК
Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках. Эта теорема формулируется следующим образом.
Теорема
. Пусть - попарно взаимно-простые числа, больше 1, и пусть . Тогда существует единственное неотрицательное решение по модулю Р
следующей системы сравнений:
…, (3.1)
Другими словами, отображение, которое каждому целому числу х
, , ставит в соответствие кортеж , где , , является биекцией кольца на декартово произведение
колец .
Существует много различных доказательств этой теоремы. Приведём конструктивное доказательство китайской теоремы об остатках.
Доказательство. Найдём число х
, , удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа х
вида где q
1
– произвольное целое число. Для нахождения q
1
подставим значение х
во второе сравнение системы, после чего получим откуда где - обратный мультипликативный элемент к по модулю . Такой элемент существует, так как Найденное таким образом q
1
можно записать в виде
для некоторого целого числа . Подставив значение в выражение
Теперь первые два сравнения могут быть заменены на одно
(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
:=МОД(
3. х
:= х
+ pq
, где MOДINV – подпрограмма вычисления мультипликативного обратного элемента.
4. q
:=МОД(
5. Вернуть х
.
Несложный анализ времени работы данного алгоритма показывает, что
где - количество цифр числа Р
, т. е. длина числа Р
, при этом функция 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
и что b
2
(3 – 2ab
) обратно к а
2
по модулю р
2
.
Решение
. По условию , следовательно , откуда , то есть . Вторую часть задачи можно решить непосредственным вычислением, учитывая, что (так как в кольце из х
2
= 0 следует, что , и можно применить это к х
= 1 – ab
в .
Пример
. Определим последовательность , следующим образом: и .
Проверить, что обратно к а
по модулю . Какое число обратно к 11335 по модулю 216
?
Решение
. Первая часть задачи фактически повторяет рассуждения примера 1.5. Для второй части задачи полагаем p
=
2, а =
11335, b
0
= 1, k
= 4. Тогда числом, обратным к а =
11335 по модулю 216
будет число b
4
, которое вычисляем последовательно:
Пример
. Сколько элементов порядка 10 в следующей группе и каковы они? Z
25
;
Решение
. В группе Z
25
элементов порядка 10 нет, так как |Z
25
| = 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
) – количество поразрядных показателей параллелизма , не меньших заданного порога , причём , где n
i
– максимально возможное число пар цифр оказывающих влияние на значение суммы в ходе её формирования на языке данного кода. Для СОК показатель параллелизма принимает максимально возможное значение . Это говорит об отсутствии межразрядных связей в числе, записанном в СОК.
2) Малоразрядность остатков. Поэтому, ввиду малого количества возможных кодовых комбинаций появляется возможность построения табличной арифметики. При этом большинство операций превращаются в однотактовые, осуществляемые простой выборкой из таблиц. По мере совершенствования технологии производства запоминающих устройств с высокой плотностью записи информации, составляющих техническую систему табличного метода вычислений, интерес к СОК неуклонно возрастает.
3) Реализация принципа конвейерной обработки информации. Это означает, что при выполнении вычислений модульные и следующие за ним операции удаётся совместить по времени только тогда, когда очередные операции зависят от результатов текущих, ещё не закончившихся операций. Таким образом, алгоритмы модулярной арифметики обладают конвейерной структурой.
4) Высокая точность, надёжность, способность к самокоррекции. Причём в СОК можно построить непозиционные коды, обнаруживающие и исправляющие ошибки, которые являются полностью арифметическими, то есть в этих кодах информативная и контрольная части равноправны относительно любой операции. Эта особенность предоставляет возможность варьировать корректирующей способностью кода за счёт изменения точности вычислений.
Конечно, и эта система не лишена недостатков. К ним относится невозможность визуального сравнения чисел, отсутствие признаков выхода результатов за пределы диапазона, ограниченность действия системы сферой целых положительных чисел, получение во всех случаях точного результата операции, что исключает возможность непосредственного округления результата, а также трудность выполнения немодульных операций. Но они не являются непреодолимыми.
§ 2. Основные методы и алгоритмы перехода от позиционного представления к остаткам
Обработка информации в цифровых устройствах, функционирующих в СОК, осуществляется с помощью модульных и немодульных операций.
К модульным операциям относятся операции сложения, вычитания и умножения. Анализ применения арифметики СОК показывает, что их звенья имеют одинаковую структуру, типовым элементом которой является последовательность вида
, (2.1´)
где - целочисленная функция вычета по некоторому модулю, р
i
– основание СОК, - операция определения наименьшего вычета по модулю р
i
.
К немодульным операциям относятся операции, при которых значение того или иного результата разряда зависит от всех или нескольких разрядов исходного числа.
Устройства, реализующие немодульные операции, довольно чётко разделяются на 2 типа.
Примером устройства первого типа является устройство свёртки, обеспечивающее вычисление
, (2.2´)
где А
i
– значение i
-го разряда исходного числа, представленного в позиционной системе счисления (ПСС); Qi
– весовой коэффициент.
Устройства свёртки широко используются в цифровых системах, функционирующих в СОК, представляющих существенную, а порой и основную часть оборудования, предназначенную для реализации ряда способов выполнения операций – перевода чисел из ПСС в СОК, деления произвольных чисел и некоторых других. Кроме того, такие устройства находят применение и в цифровых системах, функционирующих в ПСС.
Примером устройств второго типа является устройство позиционного преобразования, обеспечивающие получение характеристик, указывающих на принадлежность числа, представленного в СОК, тому или иному интервалу диапазона представимых чисел.
Математической основой устройств первого типа является определение наименьших неотрицательных вычетов, которые определяются свёртками исходного числа по каждому модулю. Для определения свёрток по каждому модулю необходимо перевести число из позиционной системы счисления в систему остаточных классов.
Перевод числа в систему остаточных классов можно осуществить методом деления. Однако из-за операции деления техническая реализация такого метода не эффективна для машинного использования, кроме того, данный метод требует применения арифметического устройства в позиционной системе счисления.
Рассмотрим метод перевода числа из позиционной системы счисления в СОК, не содержащий операции деления, называемый методом непосредственного суммирования модульных значений разрядов позиционного числа.
Пусть число X
записано в позиционной системе счисления с основанием N
, т. е.
или , (2.3´)
где .
Представим степени основания Ni
и коэффициенты Ai
в системе остаточных классов с основаниями , тогда
, (2.4´)
Подставим (2.4´) в (2.3´), получим
(2.5´)
Таким образом, для образования числа Х в СОК требуется k констант, являющихся степенями и констант, соответствующих значениям .
Имея в памяти процессора массив из констант, весь перевод может быть осуществлён процессором, работающим в СОК.
Рассмотренный метод является основой широкого выбора возможных аппаратурных реализаций цифровых преобразователей ПСС – СОК, которые различаются между собой как по составу и количеству используемых элементов, так и по скорости преобразования информации.Известные в литературе цифровые преобразователи ПСС – СОК, основанные на данном методе, анализ которых позволил сделать важные выводы о том, что одним из существенных недостатков подобных преобразователей являются большие аппаратурные затраты при переводе чисел большой разрядности и низкое быстродействие.Повышенные требования, связанные с уменьшением аппаратурных средств и увеличением скорости обработки информации, привели к необходимости глубокого изучения вопросов разработки эффективных алгоритмов. Для решения этой задачи предлагаются два метода. Рассмотрим первый метод. Для этого докажем следующую теорему, которая является основой нового метода преобразования чисел из ПСС в СОК как аппаратурными, так и программными способами.
Теорема
. Пусть число Х
записано в позиционной системе счисления с основанием N
и если
, где . (2.6´)
а - простое число, r
– число разрядов (при j
= 1, 2,…, r
), то
и . (2.7´)
Доказательство. , . Далее, подставляя значения выражений (2.6´) в выражение (2.7´), и учитывая свойства сравнений, получим
, (2.8´)
Рассмотрим второй метод, который нашёл широкое применение в литературе. Назовём его методом последовательного умножения и суммирования. Суть метода состоит в следующем. Пусть число записано в виде (2.3´). Иначе это выражение можно записать
,
, (2.9´)
,
.
Т. е. значение числа Х
в СОК по модулю образуется путём умножения старшего разряда на основание системы счисления N
, затем суммирования полученного результата со значением следующего разряда по модулю , затем умножения полученного результата на основание N
по модулю , а так последовательные умножения и суммирования по модулю производятся до тех пор, пока при суммировании не будет добавлено значение младшего разряда.
Следует отметить, что рассмотренный метод позволяет реализовать весьма экономичные, в смысле аппаратурных затрат, цифровые устройства преобразования информации.
§ 3. Восстановление позиционного представления числа по его остаткам
Система остаточных классов обладает одной особенностью, которую можно отнести к недостаткам этой системы: нельзя визуально определить величину числа, представленного в СОК, а следовательно затруднительно и выполнение таких операций, как сравнение чисел, определение знака числа. Один из путей решения этой проблемы состоит в преобразовании чисел из СОК в позиционную систему счисления. Оценим существующие способы перевода, как традиционные: метод ортогональных базисов; перевод числа в обобщенную позиционную систему (ОПС), так и недавно появившиеся интервальные методы перевода.
1). Метод восстановления числа по его остаткам был найден еще в Китае две тыс. лет назад. Основой этого метода является теорема, названная, поэтому Китайской теоремой об остатках (КТО).
Теорема.
Пусть – попарно взаимно простые числа, = , , , …, подобраны так, что 1, = , . Тогда решение системы , , будет иметь вид: .
Эта теорема лежит в основе метода ортогональных базисов при переводе из системы остаточных классов в позиционную систему счисления.
Пусть основания системы остаточных классов ; = = – объем диапазона системы. С выбором системы определяются ее основные константы – базисы , . Задача перевода числа = =() в ПСС заключается в определении таких чисел , , чтобы =. Для однозначного определения на базисы системы накладывается ряд ограничений и показывается, что таким свойством обладают базисы
= (1, 0, 0, …, 0, 0), =(0, 1, 0, …, 0, 0), = (0, 0, 0, …, 0, 1),
которые называются ортогональными.
Тогда в случае ортогональных базисов =, . Ортогональные базисы определяются по формуле
= , , (3.1´)
где
= (3.2´)
– целые положительные числа, которые называются весами базиса, их определяют из сравнений
º 1 (3.3´)
Тогда, по Китайской теореме, число
= ().
Таким образом, если найдены ортогональные базисы для системы оснований, то для перевода числа = () достаточно вычислить и ввести эту сумму в диапазон [0; ) вычитанием величины, кратной , т.е.
==–, (3.4´)
где – ранг числа , показывающий сколько раз надо вычесть величину диапазона из полученного числа, чтобы вернуть его в диапазон.
Пример.
Пусть дана система оснований = 2, = 3, = 5, =7, =11, объем диапазона =2·3·5·7·11=2310. перевести число = (1, 2, 1, 4, 7) в позиционную систему.
Вычислим ортогональные базисы.
Для этого найдем величины :
=1155, =770, =462, =330,
=210.
Ищем веса базисов:
1155º 1(2), º 1( 2).
770º 1(3), º 2(3).
462º 1(5), º 3( 5).
330º 1(7), º 1( 7).
210º 1(11), º 1( 11).
Тогда получаем сами базисы:
= ·= 1·1155 =1155,
= ·= 2·770 =1540,
= ·= 3·462 =1386,
=·= 1·330 =330,
=·= 1·210 =210.
Вычислим величину числа :
===1481.
Так как ортогональные базисы полностью определяются выбором оснований системы, то они могут быть заранее вычислены, причем единственный раз.
Недостаток рассмотренного метода заключается в том, что приходится иметь дело с большими числами и, кроме того, действия сложения и умножения надо выполнять в позиционной системе счисления, а полученный результат необходимо вводить в диапазон вычитанием величины кратной .
2). Другой метод определения величины числа связан с переводом числа из системы остаточных классов в ОПС. Для того чтобы рассмотреть этот метод, выявим связь между представлением некоторого числа в этих двух системах.Пусть по-прежнему СОК задается основаниями и = () – число в этой системе. И пусть – также основания ОПС, тогда число можно представить в виде
= + +…+
+ + + , (3.5´)
где 0 £ < – коэффициенты (цифры) ОПС.
Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимооднозначного соответствия между множеством представлений чисел в СОК и ОПС.
Равенство (3.5´) можно переписать в виде
=+(+(+…+(+)…)),
откуда следует, что цифры ОПС могут быть получены из соотношений:
=–=–, где =,
=–=–, где =, (3.6´)
…
=– = –, где =.
Причем при определении цифр по формулам (3.6´) все вычисления можно вести в СОК.
Действительно, из (3.6
= и, вообще, для > 1 =.
Перевод, осуществляемый согласно алгоритму (3.6´),содержит всего 2(–1) остаточные арифметические операции вычитания и деления без остатка, где – число модулей системы. Можно предложить некоторую модификацию, т. е. операция деления заменить операцией умножения. Для этого предварительно вычисляется констант , которые удовлетворяют условию
1(), 1 ≤ < ≤ . (3.7´)
Эти константы можно, например получить из расширенного алгоритма Евклида
= 1 (3.8´)
Здесь следует заметить тот факт, что константы полностью определяются выбранной системой оснований, поэтому могут быть вычислены заранее и храниться в некоторой таблице. В приложении к [90] для модулей и не превосходящих 31 представлена таблица величин .
Если константы вычислены, то вычисление цифр ОПС по алгоритму (3.6´) может быть переписано в виде:
,
, (3.9´)
,
.
Константы принято также записывать в виде = и называть обратными элементами по умножению для чисел по модулю (multiplicativeinverse).
Рассмотрим алгоритм (3.9´) на примере.
Пример.
Пусть дана система оснований = 2, = 3, = 5, = 7, = 11. Объем диапазона = 2310. переведем число =(1, 1, 3, 5, 4) в ОПС.
Найдем сначала константы :
= =2, = =3, = =4, = =6,
= =2, = =5, = =4,
= =3, = =9,
= =8.
Для удобства константы запишем в виде матрицы :
Выполнение алгоритма (3.9´) представлено в таблице
Перевод числа из СОК в ОПС
Действия |
Модули | Цифры ОПС |
||||
| = 2 | = 3 | = 5 | = 7 | = 11 | ||
|
– |
1 |
2 1 |
1 1 |
4 1 |
7 1 |
==1 |
– |
0 |
1 2 |
0 3 |
3 4 |
6 6 |
|
|
– |
– |
2 2 |
0 2 |
5 2 |
3 2 |
= 2 = |
– |
0 |
3 2 |
3 5 |
1 4 |
||
|
– |
– |
1 |
1 1 |
4 1 |
= 1 = | |
– |
0 |
0 3 |
3 9 |
|||
|
– |
0 |
5 0 |
= 0 = | |||
– |
0 | 5 8 |
||||
|
|
7 – |
= 7 = | ||||
Таким образом,
+ +++=
= 7 · 2 · 3 ·5 · 7 + 0 · 2 · 3 · 5 + 1 · 2 · 3 + 2 · 2 + 1 = 1481.
Преимущество рассмотренного метода перед методом ортогональных базисов состоит в том, что все вычисления выполняются в модулярной арифметике, причем в отдельных каналах, соответствующих модулям , правда, к сожалению, не параллельно. Рассмотрим некоторые модификации изложенного метода.
Один из вариантов уменьшения числа операций в рассмотренном алгоритме может быть достигнут путём особого выбора системы оснований. Выберем систему оснований СОК следующим образом:
Очевидно, что основания такой системы взаимно простые числа. Эта система обладает той особенностью, что , т.е. из сравнений получаем, что все константы = 1. При таком выборе системы оснований алгоритм можно видоизменить следующим образом: вычисления начинают со старших модулей, тогда, т.к. константы = 1, то в алгоритме отпадает необходимость умножать на , т.е.
(3.10´)
где
Пример.
Выберем систему оснований по указанному принципу:
Объём диапазона
Введем новые обозначения
Пусть в системе оснований задано число (27, 0, 1, 1). Переведём его в ОПС с той же системой оснований.
Метод перевода чисел из СОК в ОПС на основе выбора системы оснований
| Действия | Модули | Цифры ОПС | ||||||||
| – | 27 27 |
0 6 |
1 0 |
1 1 |
||||||
| – | – | 1 1 |
0 1 |
|||||||
| – | – |
1 0 |
||||||||
| – | 1 | |||||||||
Таким образом,
Как видно, при указанном выборе системы оснований число операций уменьшается вдвое, т.к. необходимо для осуществления перевода совершить операцию вычитания, против операций в общем случае. Кроме того отпадает необходимость вычислять и хранить константы . Похожим свойством обладают системы оснований
,
для которых все константы . Однако, главный недостаток указанных систем состоит в быстром росте оснований системы, так как . Один из способов достижения компромисса в создавшемся положении это выбор такой системы оснований, для которой лишь часть констант .
Другая модификация алгоритма (3.9´) основывается на факте, что если в процессе перевода появляется определенная комбинация цифр, то оставшиеся цифры числа в ОПС можно сразу определить и процесс перевода может быть завершен. К условиям, которые могут завершить процесс перевода до выполнения последнего шага алгоритма (3.9´) можно отнести следующие:
1. Если при определении цифры оказалось, что все другие остаточные цифры равны , где – другие основания СОК (< ), тогда остальные цифры ОПС будут нули.
2. Если при определении цифры оказалось, что все другие остаточные цифры равны , где – другие основания СОК (>), тогда =–1.
Рассмотрим примеры, иллюстрирующие эти случаи.
Пример.
Пусть основания системы = 2, = 3, = 5, = 7, = 11 объем диапазона = 2310.
Переведем числа =(1, 2, 3, 2, 1) и =(1, 0, 2, 4, 8) в ОПС с той же системой оснований. Учтем, что константы для этой системы вычислены ранее, выпишем их в виде матрицы :
Для числа получаем
Метод перевода числа в ОПС по условию получения комбинации цифр
Действия |
Модули | Цифры ОПС |
||||
| = 2 | = 3 | = 5 | = 7 | = 11 | ||
|
– |
1 |
2 1 |
3 1 |
2 1 |
1 1 |
=1 |
– |
0 |
1 2 |
2 3 |
1 4 |
0 6 |
|
|
– |
2 |
1 2 |
4 2 |
0 2 |
= 2 | |
– |
0 |
4 2 |
2 5 |
9 4 |
||
|
|
3
|
3 |
3 |
= 3 | ||
Тогда согласно пункту 1, == 0. Таким образом,
=(1, 2, 3, 2, 1)= = 0 · 2 · 3 ·5 · 7 + 0 · 2 · 3 · 5 + 3 · 2 · 3 + 2 · 2 + 1 = 23.
Для числа получаем
Метод перевода числа в ОПС по условию получения комбинации цифр
Действия |
Модули | Цифры ОПС |
||||
| = 2 | = 3 | = 5 | = 7 | = 11 | ||
|
– |
1 |
0 1 |
2 1 |
4 1 |
8 1 |
=1 |
– |
0 |
2 2 |
1 3 |
3 4 |
7 6 |
|
|
– |
1 |
3 1 |
5 1 |
9 1 |
= 1 | |
– |
0 |
2 2 |
4 5 |
8 4 |
||
|
|
4
|
6 |
10 |
= 4 | ||
Тогда согласно пункту 2, = 4, = 6, = 10.
Таким образом
, = (1, 0, 2, 4, 8) = 10 · 2 · 3 ·5 · 7 + 6 · 2 · 3 · 5 + 4 · 2 · 3 + 1 · 2 + 1 = 2307.
При использовании предложенного метода число операций в процессе перевода чисел в ОПС уменьшается. Причем наибольшая выгода наблюдается при небольших по абсолютной величине основаниях системы. Было подсчитано, что при использовании рассмотренных приемов число операций в процессе перевода числа из СОК в ОПС, например, для системы модулей = 13, = 11, = 7, = 5, = 3, = 2, будет в среднем 6,4, против 10 остаточных операций при применении стандартного метода. Однако, для проверки условий, позволяющих завершить процесс перевода. Потребуется наличие дополнительных логических устройств.
Еще можно отметить, что специальный выбор оснований СОК может позволить вычисление констант . Так, при кодировании остатков в двоичной системе бывает удобно выбирать модули СОК в виде
=. (3.11´)
Тогда для определения констант существует достаточно простая формула
= 1++…+, (3.12´)
где целые числа и подбираются из условий
, . (3.13´)
3). Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.
Рассмотрим СОК, заданную системой оснований , с объёмом диапазона . Выберем дробящий модуль и проведём дробление заданного диапазона на интервалы путём деления на модуль . Тогда количество интервалов , а длина интервала определяется величиной модуля. В результате величину любого числа , заданного в СОК по выбранным основаниям можно определить по номеру интервала:
, (3.14´)
в котором находится число и по цифре числа в СОК по модулю , т.е.
. (3.15´)
Так как (,) = 1, то по теореме Эйлера:
, (3.16´)
где – функция Эйлера. Причём если – простое число, то =–1. Подставляя (3.15´) в (3.4´), учитывая (3.1´) и (3.4´) число можно записать в виде
. (3.17´)
Для определения номера интервала подставим (3.17´) в (3.14´):
. (3.18´)
Учитывая, что перепишем (3.18´) в виде
. (3.19´)
Так как является делителем чисел то
где
и –
постоянные коэффициенты, определённые системой оснований.
Таким образом,
. (3.20´)
Подставляя (3.20´) в (3.15´), получим позиционное представление числа
. (3.21´)
В качестве дробирующего модуля целесообразнее выбирать наибольший из модулей системы. В этом случае модульные операции выполняются при меньшей величине модуля, что ведёт к меньшим временным и аппаратурным затратам. Целесообразно также для упрощения вычислений и минимизации времени выполнения операций выбирать в качестве дробирующего модуля наибольшие модули системы, представляющие числа Мерсенна или Ферма . При этом предпочтение отдаётся числам Мерсенна, так как арифметика по этим модулям проще.
Проиллюстрируем рассмотренный метод на примере.
Пример.
Пусть дана система оснований тогда = 210. Пусть надо перевести число =(0,1,4,3). В качестве дробирующего модуля выберем тогда , номер интервала
, а само число . Определим Так как
то
Тогда
Таким образом, 13·7 + 3 = 94.
На основе этой же характеристики числа – номера интервала, с применением теоремы Эйлера предлагается алгоритм перевода числа в ПСС. Разность между модулями можно представить в виде = – и тогда
, (3.22´)
но с другой стороны
(). (3.23´)
Из (3.22´) и (3.23´) следует, что
Так как . (3.24´)
Решение сравнения (3.24´) можно записать в виде
(3.25´)
где – функция Эйлера. Если – простое число, то Поэтому в случае простого выражение (2.3.13) примет вид:
Перепишем (3.15´) с учётом (3.25´)
(3.26´)
где – константа, определяемая выбором оснований СОК. Нетрудно заметить, что – наименьший неотрицательный вычет по составному модулю ·. Исходя из этого можно записать:
(3.27´)
где показывает, сколько раз произведение · укладывается в числе . Для нахождения можно считать, что число представлено в системе оснований в виде и после этого можно воспользоваться формулой (3.27´). Проводя аналогичные рассуждения, после преобразований получим:
(3.28´)
Где
(3.29´)
Тогда искомая величина числа ( – наименьший неотрицательный вычет числа по составному модулю ) определяется за – 1 шагов, где – число оснований СОК.
Пример.
Пусть основания СОК = 3, = 5, = 7, = 11, объём диапазона = 1155. Найдём величину числа =
(1,2,0,8).
§ 4. Расширение диапазона представления чисел
Расширение системы оснований является одной из основных немодульных операций в СОК. Выполнение этой операции бывает необходимо при выполнении операции деления чисел, при вычислении позиционных характеристик, при обнаружении переполнения при выполнении сложения или умножения чисел.
Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа.
Один из путей расширения системы оснований состоит в переводе числа в позиционную систему счисления и вычисления остатка от деления на новый модуль. Этот путь не является рациональным с точки зрения числа операций.
Другой метод расширения системы оснований позволяет определить цифру числа по новому основанию, базируясь на таких позиционных характеристиках числа, как ранг числа, след числа. Пусть вновь задана система оснований с диапазоном Р
, ортогональными базисами , веса которых . По определению, . Пусть в этой системе задано число . Расширим систему оснований, добавляя основание , тогда диапазон системы станет , ортогональные базисы системы , их веса , причём . Задача состоит в определении цифры числа по основанию называют цифру , при которой число находится в интервале , и что число , то определение цифры по основанию сводится к определению минимального следа числа А
в расширенной системе оснований.
Чтобы получить формулы для цифры запишем выражение для числа А
в основной и расширенной системах:
и ,
где и - ранги числа А
в основной и расширенной системах.
Приравнивая правые части этих выражений, определяем :
, или обозначая через целое число , а через величину , получаем . Наконец, представляя в виде , где k
,
q
– целые неотрицательные числа и , получаем
, или
. (4.1´)
Формула (4.1´) и есть формула расширения диапазона чисел.
Для практической реализации этой формулы поступают следующим образом:
1. Вычисляют параметры основной и расширенной систем (ортогональные базисы, их веса, минимальные псевдоортогональные числа с их рангами и кратности).
2. Конструируют число из минимальных псевдоортогональных чисел , , с рангами , которые однозначно определяются выбранной системой оснований . В результате, получают число , где - след числа, а его ранг находят по теореме о ранге суммы:
, (4.2´)
где - число переходов по основанию
3. Расширяют число по формуле расширения (4.1´). Пользуясь величиной ранга , вычисленной по формуле (4.2´), получают число , которое отличается от искомого числа А
цифрами по двум последним основаниям.
4. Если , то , т. е. - искомое расширение числа А
.
5. Если , то прибавляют к числу такое из минимальных псевдоортогональных чисел кратности , где , которое превратит цифру по основанию в . В результате, получают число .
6. Если кратность , то число является искомым расширением числа А
, так как к числу , не превышающему прибавили число , не превышающее , т. е. не превышает Р
, т. е. величины 1-го интервала.
7. Если , то число может располагаться либо в последних частях 1-го интервала [0; P
), либо в младших частях второго интервала [P
; 2P
), а тогда искомым является число .
Еще один путь решения поставленной задачи представляет собой перевод числа из СОК в ОПС с дополнительным финальным шагом. Рассмотрим этот метод.
Пусть СОК состоит из оснований , , …, . Объем диапазона этой системы будет . Добавим к числу оснований СОК новое основание . Объем диапазона этой системы . Тогда любое число из диапазона [0; ) в обобщенной позиционной системе счисления представимо в виде =++…+ ++. Если число будет лежать в первоначальном диапазоне [0; ), то в ОПС цифра = 0. Этот факт и используется для получения остатка от деления числа на новое основание СОК .
Пусть число имело представление (, , …, ) по основаниям , , …, . Добавляем новое основание , тогда число =(, , …, , ) в системе оснований , , …, , , где – остаток от деления числа на , т.е. искомая цифра по новому основанию.
Для определения этой цифры рассматриваем алгоритм перевода числа из СОК в ОПС, включая неизвестную цифру в проводимые операции. При этом мы последовательно будем получать цифры ОПС , , …, и выражение для цифры . Но так как по предположению число [ 0; ), то цифра = 0. Из полученного соотношения и определяем искомую цифру .
Пример.
Пусть задана система модулей = 2, = 3, = 5, = 7, тогда = 2·3·5·7=210. И пусть задано число = 157= (1, 1, 2, 3). Расширим систему оснований, добавляя = 11. Пусть = (1, 1, 2, 3, ) в системе оснований = 2, = 3, = 5, = 7, = 11. Набор констант = задается матрицей
Процесс решения задачи покажем
Расширение оснований модулярного кода
| Действия | Модули | Цифры СОК | ||||
| 2 | 3 | 5 | 7 | 11 | ||
_ х
а
|
1 1 |
1 1 |
2 1 |
3 1 |
1 |
а
1 =0 |
х
´ |
0 | 0 2 |
1 3 |
2 4 |
-1 6 |
|
_ х
а
|
0 0 |
3 0 |
1 0 |
6-6 0 |
а
2 =0 |
|
х
´ |
0 | 3 2 |
1 5 |
6-6 4 |
||
_ х
а
|
1 1 |
5 1 |
2-2 1 |
а
3 =1 |
||
х
´ |
0 | 4 3 |
2-3 9 |
|||
_ х
а
|
5 5 |
7-5 5 |
А4
=5 |
|||
х
´ |
0 | 7-10 8 |
||||
| x
4 |
-3 | а
5 =-3 |
||||
Таким образом, а
5
= – 3, но по условию а
5
= 0, т.е. – 3 = 0, откуда = 3. Получим расширенное представление числа = 157 = (1, 1, 2, 3, 3) по основаниям
= 2, = 3, = 5, = 7, = 11.
Этот алгоритм может быть несколько видоизменен за счет следующего свойства:
.
Фактически величина используется только на последнем шаге определения цифры . Поэтому в столбце по новому основанию с самого начала можно записать ноль и применить алгоритм перевода числа из СОК в ОПС.
Пусть по этому алгоритму будет получено что = для числа (, , …, , 0). Тогда для числа можно найти из соотношения:
= 0.
Рассмотрим на том же примере эту модификацию алгоритма.
Модифицированный метод расширения оснований модулярного кода
| Действия | Модули | Цифры СОК | ||||
| 2 | 3 | 5 | 7 | 11 | ||
_ х
а
|
1 1 |
1 1 |
2 1 |
3 1 |
0 1 |
А1
=1 |
х
´ |
0 | 0 2 |
1 3 |
2 4 |
10 6 |
|
_ х
а
|
0 0 |
3 0 |
1 0 |
5 0 |
А2
=0 |
|
х
´ |
0 | 3 2 |
1 5 |
5 4 |
||
_ х
а
|
1 1 |
5 1 |
9 1 |
А3
=1 |
||
х
´ |
0 | 4 3 |
8 9 |
|||
_ х
а
|
5 5 |
6 5 |
А4
=5 |
|||
х
´ |
0 | 1 8 |
||||
| x
4 |
8 | |||||
Тогда ,
. Заметим также, что последние умножение на можно не проводить.
Тогда финальный шаг для определения цифры по новому основанию может быть записан как , или умножая на , получим , где - цифра, полученная по основанию после вычитания цифры . В нашем примере = 1. Таким образом, искомую цифру можно определить из соотношения: , откуда
.
Так как результат образования цифры в СОК по новому основанию зависит только от первых цифр, то операцию расширения можно проводить сразу по нескольким основаниям.
Пример. Пусть задана система оснований
,
объем диапазона . И пусть задано число в этой системе оснований.
Найдем расширенное представление этого числа, добавляя модули и .
Для этого запишем нули в качестве неизвестных цифр и примем вышерассмотренный алгоритм расширения системы оснований.
Константы вычислены заранее и записаны в виде матрицы
Тогда получаем
Расширение модулярного кода по нескольким основаниям
| Действия | Модули | Цифры СОК | |||||
_ х
а
|
0 0 |
2 0 |
2 0 |
0 0 |
0 0 |
0 0 |
а
1 =0 |
х
´ |
0 | 2 2 |
2 3 |
0 4 |
0 6 |
0 7 |
|
_ х
а
|
1 1 |
1 1 |
0 1 |
0 1 |
0 1 |
а
2 =1 |
|
х
´ |
0 | 0 2 |
6 5 |
10 4 |
12 9 |
||
_ х
а
|
0 0 |
2 0 |
7 0 |
4 0 |
а
3 =0 |
||
х
´ |
0 | 2 3 |
7 9 |
4 8 |
|||
_ х
а
|
6 6 |
8 6 |
6 6 |
а
4 =6 |
|||
х
´ |
0 | 2 8 |
0 2 |
||||
| x
4 |
5 | 0 | |||||
Цифры по основаниям и находим из соотношений:
и ,
откуда получаем = 6 и = 0.
Таким образом, число в этой системе оснований
.
Преимущества метода расширения системы основания с помощью перевода в ОПС состоит в том, что:
во-первых, все вычисления идут в параллельных каналах по определенным модулям;
во-вторых, не требуется вычисление большого количества дополнительных величин (необходимо наличие в памяти только констант );
в-третьих, возможно получение расширенного представления числа сразу по нескольким дополнительным основаниям, что не влияет на быстродействие всей операции.
Глава 3. Программная эмуляция алгоритмов перевода чисел из СОК в ПСС и обратно и алгоритма
RSA
Программа №1
{SN+,E+}{Создание программного кода одинаково пригодного при работе на ПЭВМ с математическим сопроцессором или без него}
program Eyler;
uses crt;
type mas=array[1..20] of longint;
var i,n,b,c,d,v,x,f,f1:longint;
w:real;
a,p:mas;
r:string;
{Оформлениеэкрана}
procedure visitka;
begin
writeln(‘ Министерство образования Российской Федерации ‘);
writeln(‘ Ставропольский государственный университет ‘);
writeln(‘ Кафедра алгебры ‘);
writeln(‘ ‘);
writeln(‘Дипломнаяработа‘);
writeln(‘ ‘);
writeln(‘ Методы перевода чисел из системы остаточных классов‘);
writeln(‘ в позиционную систему счисления ‘);
writeln(‘ ‘);
writeln(‘ Выполнила: Пивоварова Елена Николаевна, ‘);
writeln(‘ФМФ, 5 курс, гр. Б ‘);
writeln(‘Научный руководитель:‘);
writeln(‘заведующая кафедрой алгебры‘);
writeln(‘Копыткова Людмила Борисовна ‘);
writeln(‘‘);
writeln(‘ Нажмитеклавишу <Enter> ‘);
writeln(‘ ‘);
writeln(‘Теоретические сведения‘);
writeln(‘ Программа позволяет производить перевод числа‘);
writeln(‘ А=(а1
, а2
, …,аn
), представленного в СОК с основаниями ‘);
writeln(‘ р1
, p2
,…,pn
такими, что р1
< p2
<…<pn
и p(i) – простые ‘);
writeln(‘числа, в позиционную систему счисления методом, ‘);
writeln(‘основанным на применении функции Эйлера. Данный метод‘);
writeln(‘заключается в следующем: для нахождения числа A в‘);
writeln(‘позиционной системе счисления берутся 2 модуля:p(i) и p(i+1),‘);
writeln(‘причем p(i) > p(i+1), и соответствующие им остатки а(i) и а(i+1). ‘);
writeln(‘Находится наименьший неотрицательный вычет по модулю ‘);
writeln(‘p(i) * p(i+1). Применяя эту операцию многократно и переходя ‘);
writeln(‘к составным модулям, осуществляют перевод чисел. ‘)
writeln;writeln;writeln;
writeln ('Нажмитеклавишу <Enter>...');
readln;
clrscr;
end; {visitka}
{Вычислениенаименьшегонеотрицательноговычета}
procedure vich (var v:longint; a,m:longint);
begin if a<0 then v:=a+m else v:=a mod m
end;{vich}
{Тест простого числа}
function test (ch:longint):boolean;
var i:longint;
begin i:=2;
while (i<=ch) and ((ch mod i)<>0) do
i:=i+1+(i mod 2);
if i=ch then test:=true else test:=false;
end;{test}
{Вводданных}
procedure DataEnter;
var i:longint;
begin
write('Введитечисломодулей:');
readln(n);
writeln('Вводзначениямодулей (p(i)<=30, p(i)-простые,');
writeln('p(i)<p(i+1)):');
for i:=1 to n do
begin
while true do begin
write('Модуль p',i ,'= ');
readln(p[i]);
if (p[i]<=30) and Test(p[i]) then
begin if i<>1 then begin
if p[i]>p[i-1] then break;
end
else break;
end;
end;{while}
end;{for}
writeln('ВводчиславСОК (a(i)>=0 и a(i)<p(i)):');
for i:=1 to n do
begin
while true do begin
write('a[',i,']=');
readln(a[i]);
if (a[i]>=0) and (a[i]<p[i]) then break;
end;{while}
end;{for}
end;{DataEnter}
{ПереводчиславПСС}
procedure Calcx(var x:longint;p,a:mas);
var i,b,c,f1:longint;
begin
f1:=p[2];
for i:=2 to n do
begin
{ВычислениефункцииЭйлера}
if p[1]<p[i] then f:=p[i]-1;{f-значениефункцииЭйлера, если}
{p[i]-простое число}
f1:=f1*(p[i]-1);
if p[1]>p[i] then
begin b:=p[1];p[1]:=p[i];p[i]:=b;
c:=a[1];a[1]:=a[i];a[i]:=c;
f:=f1 {f - значениефункцииЭйлера, если}
{f - составное число}
end;
{Перевод числа }
w:=exp((f-1)*ln(p[i]-p[1]));
vich(d,round(w),p[i]);
vich(v,a[1]-a[i],p[i]);
vich(v,d*v,p[i]);
x:=v*p[1]+a[1];
p[1]:=p[1]*p[i];
a[1]:=x;
end
end;{Calcx}
begin
repeat
clrscr;
visitka;
dataenter;
calcx(x,p,a);
writeln('A= ',x);
writeln('Повторить? (y/n): ');
readln(r);
until (r= 'n')
end.
Министерство образования Российской Федерации
Ставропольский государственный университет
Кафедра алгебры
Дипломная работа
Методы перевода чисел из системы остаточных классов
в позиционную систему счисления
Выполнила:Пивоварова Елена Николаевна,
ФМФ, 5 курс, гр. Б
Научный руководитель:
заведующая кафедрой алгебры
Копыткова Людмила Борисовна
Нажмите клавишу <Enter>
Теоретические сведения
Программа позволяет производить перевод числа
А=(а1
, а2
, …,аn
), представленного в СОК с основаниями
р1
, p2
,…,pn
такими, что р1
< p2
<…<pn
и p(i) – простые
числа, в позиционную систему счисления методом,
основанным на применении функции Эйлера.
Данный метод заключается в следующем:
для нахождения числа A в
позиционной системе счисления берутся 2 модуля:
p(i) и p(i+1), причем p(i) > p(i+1), и
соответствующие им остатки а(i) и а(i+1).
Находится наименьший неотрицательный
вычет по модулю p(i) * p(i+1).
Применяя эту операцию многократно и переходя
к составным модулям, осуществляют перевод чисел.
Результаты работы программы
Нажмите клавишу <Enter>…
Введите число модулей:2
Ввод значения модулей (p(i)< =30, p(i)-простые,
p(i)< p(i+1)):
Модуль р1=17
Модуль р2=19
Ввод числа в СОК (а(i)>=0 и (а(i)<p(i)):
a[1]=2
a[2]=3
A=155
Повторить? (у/n):
y
Введите число модулей:3
Ввод значения модулей (p(i)< =30, p(i)-простые,
p(i)< p(i+1)):
Модуль р1=2
Модуль р2=3
Модуль р3=5
Ввод числа в СОК (а(i)>=0 и (а(i)<p(i)):
a[1]=1
a[2]=2
a[3]=4
A=29
Повторить? (у/n):
n
Программа
№2
program
COK_Poliandr;
type
mas1=array [1..10] of integer;
mas2= array [1..10,1..10] of integer;
var
p, a, o: mas1;
t: mas2;
Aonc, PP, i, j, y, k, n, f : integer;
begin
writeln
('Перевод чисел из СОК в обобщенную систему счисления ');
write
('Введите размер системы оснований = ');
readln
(n);
writeln
('Введите каждое основание ');
PP:=1;{Присвоение начального значения объему диапазона}
for
i:=1 to
n do begin
{Ввод системы оснований и вычисление объёма
диапазона}
writ
e ('p[',i,']= ');
readln
(p[i]);
PP:=PP*p[i];
end;
writeln
('ОбъемдиапазонаР =',PP);
writeln
('Введите число в СОК по цифрам: ');
for
i:=1 to
n do begin
{Ввод исходного числа в СОК}
write
(i,' цифра= ');
readln
(a[i]);
end
;
write
('Переведём число А = ( '); {Вывод на экран исходного числа}
for
i:=1 to
n do write
(a[i],',');
writeln
(') в ОПС.');
writeln
('На первом этапе получим матрицу констант ');
for
k:=1 to
n do
for
J:=k to
n do
{Вычисление матрицы обратных элементов по
умножению для чисел pk
по модулю pj
}
begin
i:=0; f:=0;
repeat
if (1+i*p[j]) mod p[k] =0 then begin
t[k,j]:=(1+i*p[j]) div p[k];f:=1;{Флаг поднят, если произошло вычисление константы}
end;
i:=i+1;
until
(i>n) or
(f=1);{Выход из цикла, если поднят флаг или превышено значение параметра}
end;
for k:=1 to n do begin
{Вывод полученной матрицы}
for J:=1 to n do write(
t[k,j],' ');
writeln;
end;
write
('ЗатемполучимцифрыОПС: ');
for j:=1 to n do begin
o[j]:=a[j];{Получение очередной цифры}
for i:=j to n do begin
if
a[i]>=o[j] then
a[i]:=a[i]-o[j] {Первое действие}
else
a[i]:=a[i]+p[i]-o[j];
a[i]:=a[i]*t[j,i]; {Второе действие}
if
a[i]>p[i] then
a[i]:=a[i] mod p[i];
end;
write
(o[j],' ');{Вывод очередной цифры ОПС}
end;
writeln;
write
('В итоге, получим число: ');
Aonc:=0; y:=1;{Обнуление результата}
for
i:=1 to
n do begin
{Получение числа в позиционной системе счисления по его цифрам }
Aonc:= Aonc+y*o[i];
y:=y*p[i];
end;
writeln
(Aonc);{Вывод полученного результата}
readln;
{Задержка результата на экране
до нажатия клавиши ENTER}
end.
Результаты работы программы
Перевод чисел из СОК в обобщенную систему счисленияВведите размер системы оснований = 5
Введите каждое основание
p[1]=2
p[2]=3
p[3]=5
p[4]=7
p[5]=11
Объем диапазона Р =2310
Введите число в СОК по цифрам: 1 цифра = 1
2 цифра = 2
3 цифра = 1
4 цифра = 4
5 цифра = 7Переведём число А = ( 1, 2, 1, 4, 7,) в ОПС.
На первом этапе получим матрицу констант 0 0 2 3 4 5
0 0 0 2 5 4
0 0 0 0 3 9
0 0 0 0 0 8
0 0 0 0 0 0
Затем получим цифры ОПС: 1 2 1 0 7
В итоге, получим число: 1481
Применение СОК не ограничивается только переводом чисел из СОК в ПСС и обратно. Например, ещё СОК можно использовать для шифровки сообщений.
Программа №3
В данной программе реализуется шифрование и расшифрование сообщения методом RSA.
Блок-схема алгоритма нахождения А-1
mod
N
Блок-схема алгоритма вычисления ad
(modN)
Блок-схема алгоритма нахождения простых чисел не превышающих
N
Блок-схема реализации алгоритма RSA
Листинг программы
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include <math.h>
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Log->Lines->Clear();
srand( GetTickCount() );
// Ввод P и Q
int p = StrToInt( Edit1->Text );
int q = StrToInt( Edit2->Text );
Log->Lines->Add( "p = " + IntToStr( p ) );
Log->Lines->Add( "q = " + IntToStr( q ) );
// Вычисление N
intN = p * q;
Log->Lines->Add( "N = p*q = " + IntToStr( N ) );
// Вычисление f(N)
int f = (p-1)*(q-1);
Log->Lines->Add( "f(n)=(p-1)(q-1) = " + IntToStr( f ) );
// Вводоткрытогоключа K1
int k1 = StrToInt( edtOK->Text );
Log->Lines->Add( "k1 = " + IntToStr( k1 ) );
// Проверка условий существования открытого ключа
if( NOD( k1, f ) != 1 )
{
Log->Lines->Add( "открытый ключ и f(n) не взаимно простые. введите новые параметры" );
return;
}
// Нахождение секретного ключа
intk = ObrElem( k1, f );
Log->Lines->Add( "k = k1^(-1) mod f(n) = " + IntToStr( k ) );
AnsiString clear = Edit3->Text;
AnsiString coded;
// Шифрование и расшифрование сообщения
coded = "";
int *clear_c = new int[clear.Length()];
int *coded_c = new int[clear.Length()];
int *clr_c = new int[clear.Length()];
for( int i = 1; i <= clear.Length(); i++ )
{
clear_c[i-1] = (int)clear[i];
coded_c[i-1] = ModStep( clear_c[i-1], k1, N );
clr_c[i-1] = ModStep( coded_c[i-1], k, N );
char temp[256];
wsprintf( temp, "%c = %c = %c", clear[i], (char)coded_c[i-1], (char)clr_c[i-1] );
Log->Lines->Add( temp );
wsprintf( temp, "%c", (char)coded_c[i-1] );
coded += temp;
}
delete[] clr_c;
delete[] coded_c;
delete[] clear_c;
// Вывод полученных результатов
Log->Lines->Add( "cleartext = " + clear );
Log->Lines->Add( "coded text = " + coded );
Log->Lines->Add( "" );
}
// МодульнохожденияНОД (a, b)
int __fastcall TForm1::NOD(int a, int b)
{
if( ( a == 0 )||( b == 0 ) )
{
return abs( a + b );
}
while( a != b )
{
if( a > b )
{
a -= b;
}
else
{
b -= a;
}
}
return b;
}
//Модуль нахождения обратного элемента по модулю N
int __fastcall TForm1::ObrElem(int a, int N)
{
int u1 = 0, u2 = 1, u3 = N;
int v1 = 1, v2 = 0, v3 = a;
int t1, t2, t3, q;
while(u3 != 1)
{
q = u3 / v3;
t1 = u1 - v1*q;
t2 = u2 - v2*q;
t3 = u3 - v3*q;
u1 = v1;
u2 = v2;
u3 = v3;
v1 = t1;
v2 = t2;
v3 = t3;
}
return u1 < 0 ? u1 + N : u1;
}
// Модуль возведения числа в степень по модулю N
int __fastcall TForm1::ModStep(int a, int d, int n)
{
int aBmodN = a;
int dtemp = d;
AnsiString binary = "";
while( dtemp > 1 )
{
binary += IntToStr( dtemp % 2 );
dtemp = floor( dtemp / 2 );
}
binary += dtemp;
for( int i = 1; i < binary.Length(); i++ )
{
aBmodN = aBmodN*aBmodN * ( binary[binary.Length() - i] == '0' ? 1 : a ) % n;
}
return aBmodN;
}
void __fastcall TForm1::Button3Click(TObject *Sender)
{
int q = 0;
int p = 0;
int *a = new int[256];
prost( a, 64 );
srand( GetTickCount() );
while( ( p == 0 )||( p > 64 ) )
{
p = a[ rand() % 64-1 ];
}
while( ( q == 0 )||( q > 64 ) )
{
q = a[ rand() % 64-1 ];
}
Edit1->Text = FloatToStr( p );
Edit2->Text = FloatToStr( q );
delete[] a;
}
// Модуль нахождения простых чисел на превышающих N методом решета Эратосфера
void __fastcall TForm1::prost( int *a, int n )
{
int b, c;
for( b = 1; b <= n; b++ )
{
a[b] = b;
}
for( b = 2; b <= floor( sqrt( n ) ); b++ )
{
c = 0;
c += ( b << 1 );
while( c <= n )
{
a[c] = 0;
c+= b;
}
}
}
Цитированная литература
1. Бухштаб А. А. Теория чисел – М: Наука, 1975 г.
2. Айерленд К. Классическое введение в современную теорию чисел. М: Мир, 1987.
3. Акушинский И. Л., Юдицкий Д. И. Машинная арифметика в остаточных классах. – М. Советское радио, 1968.
4. Амербаев В. М. Теоретические основы мащинной арифметики, - Алма –Ата: Наука, 1976.
5. Червяков Н. И. Применение нейронных сетей для прямого и обратного преобразования кодов в СОК. Вестник СГУ, Физ.-мат. науки, 1999.
6. Червяков Н. И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. – Ставрополь: СВВиУС, 1984.
7. Червяков Н. И. Преобразование цифровых позиционных и непозиционных кодов в системах управления и связи. – Ставрополь: СВВиУС, 1985.
8. Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации, - Минск: Университетское, 1992.
9. Онищенко С. М. Применение гиперкомплексных чисел в теории инерциальной навигации. Автономные системы, - Киев: Наукова думка, 1983.