ПРЕОБРАЗОВАНИЕ ПРЕДСТАВЛЕНИЙ ЧИСЕЛ В МОДУЛЯРНОЙ АРИФМЕТИКЕ В СИСТЕМАХ ОСТАТОЧНЫХ КЛАССОВ С РАЗНЫМИ ОСНОВАНИЯМИ
Авторы:
1.
Дагестанский государственный технический университет
Тип:
Статья
Страницы:
с 32
по 39
Статус:
Опубликован
Получено:
05.10.2014
Одобрено:
25.10.2014
Опубликовано:
25.10.2014
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.5
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.5
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования
Аннотация (русский):
Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную (МС) и наоборот. Однако в процессе обработки данных достаточно реализовать МС-ПСС преобразования только на самой начальной и на самой последней стадиях обработки, а в промежуточных преобразованиях использовать преобразования из одной модулярной в другую модулярную систему. Предлагается процедура преобразования чисел из одной системы остаточных классов (СОК) в другую без использования алгоритма Эвклида, т. к. его многократная реализация является наиболее трудоемким этапом нахождения представлений чисел в СОК и обратного преобразования представлений из СОК в искомые числа. Процедура опирается на использование предварительно подготовленных таблиц. На основе описанной процедуры может быть разработан алгоритм, ориентированный непосредственно на написание программного кода. Произведена оценка основных характеристик процесса преобразования. В качестве примера рассматривался четырехъядерный процессор, каждое ядро которого может обрабатывать числа длиной 64 бит. Приведенные в работе оценки показали, что затраты на заполнение таблиц оказались вполне приемлемыми, и это позволило сделать вывод о возможности практической реализации разработанной процедуры.
Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную (МС) и наоборот. Однако в процессе обработки данных достаточно реализовать МС-ПСС преобразования только на самой начальной и на самой последней стадиях обработки, а в промежуточных преобразованиях использовать преобразования из одной модулярной в другую модулярную систему. Предлагается процедура преобразования чисел из одной системы остаточных классов (СОК) в другую без использования алгоритма Эвклида, т. к. его многократная реализация является наиболее трудоемким этапом нахождения представлений чисел в СОК и обратного преобразования представлений из СОК в искомые числа. Процедура опирается на использование предварительно подготовленных таблиц. На основе описанной процедуры может быть разработан алгоритм, ориентированный непосредственно на написание программного кода. Произведена оценка основных характеристик процесса преобразования. В качестве примера рассматривался четырехъядерный процессор, каждое ядро которого может обрабатывать числа длиной 64 бит. Приведенные в работе оценки показали, что затраты на заполнение таблиц оказались вполне приемлемыми, и это позволило сделать вывод о возможности практической реализации разработанной процедуры.
Ключевые слова:
модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования
модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования
Введение Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную и наоборот. Как отмечено в [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. Магомедов Ш. Г. Формирование состава макрокоманд микропроцессора с вычислительной базой на основе системы остаточных классов / Ш. Г. Магомедов, Г. А. Попов, В. П. Шевчук // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2014. № 2. С. 38-44.
2. Магомедов Ш. Г. Алгоритм и схема сложения чисел в арифметико-логическом устройстве с использованием системы остаточных классов / Ш. Г. Магомедов // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2014. № 1. С. 62-68.
3. Эрдниева Н. С. Использование специальных модулей системы остаточных классов для избыточного представления / Н. С. Эрдниева // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2013. № 2. С. 75-85.
