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

= 2, = 3, = 5, = 7, = 11.

Этот алгоритм может быть несколько видоизменен за счет следующего свойства:

.

Фактически величина

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

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

= для числа ( , , …, , 0). Тогда для числа можно найти из соотношения:

= 0.

Рассмотрим на том же примере эту модификацию алгоритма.

Модифицированный метод расширения оснований модулярного кода

Действия	Модули					Цифры СОК
	2	3	5	7	11
_ ха1	11	11	21	31	01	А1=1
х-а1´	0	02	13	24	106
_ х1а2	00	30	10	50	А2=0
х1-а2´	0	32	15	54
_ х2а3	11	51	91	А3=1
х2-а3´	0	43	89
_ х3а4	55	65	А4=5
х3-а4´	0	18
x4	8

Тогда

,

. Заметим также, что последние умножение на можно не проводить.

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

, или умножая на , получим , где - цифра, полученная по основанию после вычитания цифры . В нашем примере = 1. Таким образом, искомую цифру можно определить из соотношения: , откуда

.

Так как результат образования цифры в СОК по новому основанию

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

Пример. Пусть задана система оснований

,

объем диапазона

. И пусть задано число в этой системе оснований.

Найдем расширенное представление этого числа, добавляя модули

и .

Для этого запишем нули в качестве неизвестных цифр и примем вышерассмотренный алгоритм расширения системы оснований.

Константы

вычислены заранее и записаны в виде матрицы

Тогда получаем

Расширение модулярного кода по нескольким основаниям

Действия	Модули						Цифры СОК
_ ха1	00	20	20	00	00	00	а1=0
х-а1´	0	22	23	04	06	07
_ х1а2	11	11	01	01	01	а2=1
х1-а2´	0	02	65	104	129
_ х2а3	00	20	70	40	а3=0
х2-а3´	0	23	79	48
_ х3а4	66	86	66	а4=6
х3-а4´	0	28	02
x4	5	0

Цифры по основаниям

и находим из соотношений:

и ,

откуда получаем

= 6 и = 0.

Таким образом, число

в этой системе оснований

.

Преимущества метода расширения системы основания с помощью перевода в ОПС состоит в том, что:

во-первых, все вычисления идут в параллельных каналах по определенным модулям;

во-вторых, не требуется вычисление большого количества дополнительных величин (необходимо наличие в памяти только констант

);

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

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

Программа №1

{SN+,E+}{Создание программного кода одинаково пригодного при работе на ПЭВМ с математическим сопроцессором или без него}

program Eyler;

uses crt;

type mas=array[1..20] of longint;