CONVERSION OF NUMERATION IN MODULAR ARITHMETIC IN THE SYSTEMS OF RESIDUAL CLASSES WITH DIFFERENT BASES
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
Volume 2014 № 4
, 2014
Rubrics: MANAGEMENT, MODELING, AUTOMATION
Authors:
1.
Dagestan State Technical University
Type:
Article
Pages:
from 32
to 39
Status:
Published
Received:
05.10.2014
Accepted:
25.10.2014
Published:
25.10.2014
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
modular arithmetic, positional number system, processing of numerical data, conversion process
Abstract (English):
One of the stages of processing numbers in modular arithmetic, which requires the most amount of computer resources and thus significantly reduces the efficiency of the use of methods of modular arithmetic as the processing technology of numeric data in data processing equipment, is a step of converting the number of positional number system (PNS) in the modular (MS), and vice versa. However, in the processing of data it is sufficient to implement the MS-PNS conversion only at the start and at the very last stages of processing, and in the intermediate transformations to use conversion from one to another modular system. This article proposes a process for the conversion of numbers from one system to another residual classes without using Euclidean algorithm, as its multiple implementation is the most time-consuming step of finding representations of numbers in the SRC and the inverse transform notions of SRC in the required number. The procedure relies on the use of tables prepared beforehand. On the basis of this procedure, an algorithm that focuses directly on writing code can be developed. The assessment of the main characteristics of the conversion process is made. Quad-core processor, each core that can handle a 64-bit was considered as an example. The assessments presented in the paper showed that the cost of filling the tables were quite acceptable, which led to the conclusion about the possibility of the practical implementation of the developed procedure.
One of the stages of processing numbers in modular arithmetic, which requires the most amount of computer resources and thus significantly reduces the efficiency of the use of methods of modular arithmetic as the processing technology of numeric data in data processing equipment, is a step of converting the number of positional number system (PNS) in the modular (MS), and vice versa. However, in the processing of data it is sufficient to implement the MS-PNS conversion only at the start and at the very last stages of processing, and in the intermediate transformations to use conversion from one to another modular system. This article proposes a process for the conversion of numbers from one system to another residual classes without using Euclidean algorithm, as its multiple implementation is the most time-consuming step of finding representations of numbers in the SRC and the inverse transform notions of SRC in the required number. The procedure relies on the use of tables prepared beforehand. On the basis of this procedure, an algorithm that focuses directly on writing code can be developed. The assessment of the main characteristics of the conversion process is made. Quad-core processor, each core that can handle a 64-bit was considered as an example. The assessments presented in the paper showed that the cost of filling the tables were quite acceptable, which led to the conclusion about the possibility of the practical implementation of the developed procedure.
Keywords:
modular arithmetic, positional number system, processing of numerical data, conversion process
modular arithmetic, positional number system, processing of numerical data, conversion process
Введение Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную и наоборот. Как отмечено в [1, 2], при обработке числовых данных часто достаточно иметь алгоритмы преобразования не из модулярной в позиционную, а из одной модулярной системы (с одним основанием) в другую модулярную систему. При этом при определенных условиях преобразования чисел из одной модулярной системы в другую могут оказаться более быстрыми, чем из модулярной в ПС, особенно если количество чисел в основании системы остаточных классов (СОК) достаточно велико. Отметим, что если количество чисел в основании мало, вычисления в СОК по трудоемкости сравнимы с вычислениями в ПСС. Кроме того, как отмечено в [1], необходимость преобразования представления числа из одной СОК в другую возникает также при необходимости создания определенных условий по обеспечению информационной безопасности процесса обработки данных, т. к. при длительном использовании одной и той же СОК злоумышленник может путем накопления определенной статистики раскрыть набор чисел, входящих в ее основание. Наконец, при использовании технологий параллельной обработки данных (например, в многопроцессорных системах) на разных процессорах будут сформированы разные основания СОК, и при необходимости использования результатов, полученных на одних процессорах, другими процессорами также возникает необходимость преобразования из одной СОК в другую. Указанной задаче преобразования числовых данных из одной модулярной системы в другую и посвящена данная работа. Публикаций по исследуемой тематике нет. Близкие результаты приведены в [3]. Основные соотношения процесса преобразования Приведем формализованную постановку задачи. Пусть имеются две СОК: A={, , …, } и B = {, , …, }, где и - простые числа, и задано некоторое число x, удовлетворяющее условиям , , которое имеет следующие представления в системах A и B: и . Необходимо построить процедуру, которая позволяла бы, когда известно представление , получить представление непосредственно, без преобразования xA в исходное число x и последующего разложения x в системе B. Положим . Предположим вначале, что K = L. Тогда предлагаемая процедура состоит из отдельных этапов, на каждом из которых в СОК одно из чисел Pi заменяется на одно из чисел Qj, а также «подправляется» представление числа x в новой СОК. Описываемая процедура не зависит от порядка следования чисел в основаниях СОК. Рассмотрим первый этап процедуры. Необходимо, имея представление xA = xA (1) в СОК A = A1, получить представление xA (2) числа x в СОК A2={, , , …, }, где - представление числа x в СОК Ai, которые формируются в процессе реализации процедуры. Для получения искомого представления воспользуемся формулой, выражающей искомое число x через его разложение в СОК A1 [2]: , где , есть решение сравнения (). (1) Пусть в СОК A2 число x представляется в виде , где для i > 1 и , есть решение сравнения () и . Последние соотношения равносильны следующим (i > 1): (2) где использовано обозначение , . Первое соотношение в (2) можно переписать в виде или , где . Сравнивая последнее соотношение со вторым соотношением в (2), заключаем: для всех i > 1. (3) Для нахождения воспользуемся соотношением (1); с учетом (3) получаем , откуда . (4) При этом, поскольку , то т. е. делится на . Вычислив обе части (4) по и воспользовавшись тем, что , получаем соотношение (напомним, ): . (5) Заметим, что , и . (6) Соотношения (5) и (6) позволяют вычислить число без вычисления числа x. Аналогичным образом, на j-м шаге алгоритма (), можно получить следующие соотношения для вычисления числа для случая, когда количество чисел в основании СОК при замене одной СОК на другую остается неизменным, т. е. K = L: , (7) где ; для всех i > j; для i < j; (8) ; . (9) Рассмотрим теперь случай L < K, т. е. в новой СОК в основании больше чисел, чем в исходной. Введем в основание A новое простое число Q; получим новую систему оснований . Найдем представление числа x в системе оснований B на основе его представления в системе оснований A. Рассмотрим вначале случай, когда K = L + 1, т. е. система оснований B получается из системы оснований A путем добавления некоторого простого числа Q, не совпадающего с другими числами основания A: для всех . Тогда справедливы соотношения: , где , , есть решение сравнения (), для и , есть решение сравнения () и . Тогда справедливы соотношения: , откуда после сравнения с соотношением заключаем, что . Отсюда вытекает соотношение , . (10) Далее, , откуда выводим: . (11) Соотношения (10), (11) позволяют получить представление числа x в СОК B на основе его представления в СОК A в случае, когда K = L + 1. В случае K > L + 1 можно выполнить описанную процедуру K - L раз, добавляя на каждом шаге по одному простому числу из тех, которые входят в основание B, но не входят в основание A. Таким образом, процедура получения представления числа x в СОК B на основе его представления в СОК A при K > L построена. Пусть теперь K < L, т. е. основание B получается из основания A путем выбрасывания L - K чисел. Рассмотрим вначале случай L = K + 1 и предположим, что выбрасывается . Тогда, обозначая, как и выше, волной над буквенным обозначением значение соответствующего параметра в СОК с основанием B, имеем: , , , откуда после сравнения последних двух соотношений заключаем: , ; . (12) Соотношение (12) позволяет получить представление числа x в основании B при любых K и L путем выполнения L - K шагов, на каждом из которых выбрасывается одно из чисел из основания A. Таким образом, выше приведены все соотношения, необходимые для получения представления числа x в заданной СОК B на основе наличия его представления в другой СОК A (при условии, что число x меньше числа, равного произведению чисел в основании каждой из СОК). В следующем разделе описана непосредственно алгоритмическая процедура выполнения указанного преобразования. Как уже отмечалось выше, одним из важных достоинств приведенных соотношений является то, что эти соотношения позволяют получить представление в альтернативной СОК на основе представления в исходной СОК непосредственно, без вычисления самого числа, представлениями которого они являются. Предлагаемый алгоритм имеет еще одно важное достоинство. Напомним, что получение исходного числа на его представления в СОК обычно осуществляется на основе китайской теоремы об остатках, одно из основных соотношений которой приведено в (1). Непосредственное использование (1) требует решения сравнений, что обычно осуществляется на основе обобщенного алгоритма Эвклида. Многократная реализация алгоритма Эвклида и является наиболее трудоемким этапом нахождения представлений чисел в СОК и обратного преобразования представлений в СОК в искомые числа. Предлагаемые соотношения позволяют избежать использования алгоритма Эвклида непосредственно в процессе выполнения преобразований, что существенно повысит скорость реализации процедуры. Именно в приведенных соотношениях алгоритм Эвклида необходим только для получения чисел . Но база данных простых чисел, которые будут использованы при формировании основания СОК, выбирается заранее. Поэтому заранее, например еще на этапе проектирования системы (процессора), может быть сформирована база данных (таблица) чисел для всех пар чисел и , и в дальнейшем при использовании соотношений (7)-(9) эти числа просто могут выбираться из построенной таблицы. Более того, использование таблиц позволяет в значительной мере аппаратно реализовать процесс преобразования чисел из одной СОК в другую. Таким образом, анализ показывает, что использование соотношений (7)-(9) потенциально позволит существенно повысить эффективность преобразования чисел из одной СОК в другую и тем самым повысить быстродействие процессов и процедур вычислений в СОК. Этапы алгоритма преобразования числа из одной системы остаточных классов в другую Соотношения (7)-(12) позволяют сформировать следующую алгоритмическую процедуру преобразования представления чисел из одной СОК в другую. Шаг 0. На предварительном этапе, предшествующем процессу вычислений (возможно, даже на стадии проектирования процессора), формируется база простых чисел и таблица чисел для всех пар простых чисел P и Q () из сформированной базы простых чисел. Шаг 1. Вводится число x и выбирается некоторая система оснований СОК A={, , …, } из простых чисел (которые все различны и упорядочены по возрастанию) из базы простых чисел. При этом число L и числа Pi выбираются так, чтобы выполнялось условие . Строится представление числа x в СОК с основанием A следующим образом: , где (). Необходимо перейти к представлению числа x в СОК с другой системой оснований B = {, , …, }, т. е. получить представление , где . Находим числа для всех . Шаг 2. Сравниваются числа K и L. Если L < K, то переходим к шагу 6. В противном случае (т. е. ) последовательно для j от 1 до K выполняются следующие действия. Шаг 3. Число Pj сравнивается с числами Qi , входящими в основание B. Если найдется число m такое, что Pj = Qm, то число j увеличиваем на единицу. Если полученное значение j = K, то переходим к шагу 5. В противном случае переходим к началу шага 3. Если же для всех , то выполняются следующие действия. Шаг 4. Находим на основе равенств (7)-(9) числа и , для всех i от 1 до L. Увеличиваем j на единицу и проверяем условие j = K. Если оно выполняется, то переходим к шагу 5, предварительно присваивая значения , для всех . В противном случае переходим к шагу 3. Шаг 5. При L = K переходим к шагу 6. В противном случае (т. е. L > K) последовательно для j от L до K + 1 выполняются следующие действия. Вначале полагаем j = L. На основе (12) находятся значения коэффициентов , для всех i < j. Значение j уменьшается на единицу; если полученное значение j равно K + 1, то процесс вычислений шага 5 прекращается и переходим к следующему шагу 7. Если j > K + 1, то полагаем , для всех и переходим к началу данного шага (начало данного абзаца). Шаг 6. Если L < K, то последовательно выполняются следующие действия. Вначале, аналогично шагу 4, на основе равенств (7)-(9) находим числа и , для всех i от 1 до L. Затем последовательно для j от L+ 1 до K выполняются следующие действия. Вначале полагаем j = L + 1. На основе соотношения (10) находим коэффициенты , для всех i < j; на основе соотношения (11) находим и . Далее увеличиваем j на единицу. Если выполняется равенство j = K, то переходим к следующему шагу. В противном случае полагаем , для всех и переходим к началу шага 6 (начало данного абзаца). Шаг 7. Выводится вектор в качестве представления числа x в СОК с основанием B, а также запоминаются вспомогательные коэффициенты , для всех i от 1 до K для их использования при последующих вычислениях. Процесс вычислений заканчивается. На основе описанной процедуры может быть разработан алгоритм, ориентированный непосредственно на написание программного кода. Реализация разработанного алгоритма Для практической реализации разработанного алгоритма необходимо оценить возможные значения приведенных выше параметров алгоритма, в частности количество чисел в основании СОК; ограничения на числа, входящие в основание; количество простых чисел в базе данных; размеры таблицы обратных значений простых чисел в модульной арифметике. Перечисленные вопросы ниже рассматриваются с точки зрения возможностей современных типовых процессоров, поскольку разработанный алгоритм может представлять большой интерес применительно к организации работы процессоров. Рассмотрим четырехъядерный процессор, каждое ядро которого может обрабатывать числа длиной 64 бит. Оценим вначале число L простых чисел в основании. Так как , то при L > 4 среди чисел найдутся числа, удовлетворяющие соотношению - достаточно малые числа, которые при наборе определенной подходящей статистики могут быть взломаны злоумышленником, что существенно облегчит ему возможности по нахождению других чисел в основании СОК. При L < 4 количество чисел в основании достаточно мало, что усложняет текущие вычисления в СОК, делая их по трудоемкости сравнимыми с вычислениями в позиционной системе. На основании вышесказанного предлагается каждому ядру сопоставить СОК с четырьмя простыми числами в основании, т. е. L = 4. Для того чтобы простые числа трудно было подобрать (например, путем перебора), предлагается наложить ограничения на минимальную длину простых чисел, а именно предлагается выбрать простые числа Pi (i = 1, 2, 3, 4), удовлетворяющие условию Pi > 214 = 8192. Поскольку при этом произведение P1· P2·P3· P4 является верхней границей для обрабатываемых чисел, то получаем оценку 264 < P1· P2·P3· P4. При этом желательно, чтобы разница между правой и левой частями была бы как можно меньше для неизбыточности вычислений. Отсюда выводим, что каждое из чисел Pi не должно быть очень большим, т. к. в противном случае не удастся обеспечить выполнение условия Pi > 214 для всех i. Поэтому для максимально возможных значений простого числа P в основании СОК получаем соотношение , откуда выводим соотношение . Таким образом, получаем следующие ограничения на величины простых чисел P в основании СОК: 214 < P < 222. Оценим теперь размер таблицы обратных значений P(Q) для всех пар простых чисел. По теореме Чебышева, при достаточно больших n количество простых чисел, не превосходящих n, асимптотически эквивалентно. Отсюда выводим, что количество простых чисел P, удовлетворяющих условию 214 < P <222, приблизительно равно . Следовательно, размер таблицы (т. е. количество заполняемых клеток) приблизительно равен чисел. Оценим величину времени, необходимого для заполнения таблицы. Оценки показывают, что вычисление одного значения таблицы обратных величин на основе обобщенного алгоритма Эвклида требует не более тактовых операций. Тогда при использовании процессора с тактовой частотой 2 ГГц = 2 ∙ 230 Гц потребуется времени порядка Поскольку таблица формируется заранее (не в режиме реального времени), то затраты времени порядка 18 часов на заполнение таблицы вполне приемлемы. Из приведенного анализа заключаем, что предлагаемая процедура преобразования чисел из одной СОК в другую практически реализуема с точки зрения возможностей существующих вычислительных устройств. Заключение Таким образом, в ходе исследований: 1. Получены математические соотношения, позволяющие на основе представлений числа в одной СОК находить его представления в другой без использования алгоритма Эвклида и вычисления искомого числа в процессе преобразований, что существенно повышает скорость выполнения операции преобразования. 2. На основе полученных математических соотношений сформирована алгоритмическая процедура преобразования чисел из одной СОК в другую, учитывающая всевозможные отличия между двумя СОК как по количеству чисел в основании каждой СОК, так и по их составу. 3. Произведена оценка основных характеристик процесса преобразования с учетом возможностей современных процессоров, что позволило сделать вывод о возможности практической реализации разработанной процедуры. Рассматриваемый этап использования СОК в процессе обработки числовой информации связан с одним из наиболее трудоемких этапов обработки, поэтому практическая реализация приведенного алгоритма позволит значимо повысить эффективность использования СОК в системах обработки данных, в частности в микропроцессорных устройствах.
1. Magomedov Sh. G. Formirovanie sostava makrokomand mikroprocessora s vychislitel'noy bazoy na osnove sistemy ostatochnyh klassov / Sh. G. Magomedov, G. A. Popov, V. P. Shevchuk // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. 2014. № 2. S. 38-44.
2. Magomedov Sh. G. Algoritm i shema slozheniya chisel v arifmetiko-logicheskom ustroystve s ispol'zovaniem sistemy ostatochnyh klassov / Sh. G. Magomedov // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. 2014. № 1. S. 62-68.
3. Erdnieva N. S. Ispol'zovanie special'nyh moduley sistemy ostatochnyh klassov dlya izbytochnogo predstavleniya / N. S. Erdnieva // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. 2013. № 2. S. 75-85.
