Умножение и деление в системе остаточных классов с использованием полей Галуа GF(p) Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Червяков Николай Иванович, Бабенко Михаил Григорьевич, Ляхов Павел Алексеевич, Лавриненко Ирина Николаевна, Лягин Алексей Михайлович

Предложен алгоритм умножения и деления в системе остаточных классов , основанный на теории полей Галуа GF(p). Применение полей Галуа GF(p) для решения проблем арифметического умножения и деления устраняет многие ограничения существующих алгоритмов. Преимущество предложенного алгоритма заключается в том, что он не имеет ограничений на делимое и делитель, не использует обобщенную позиционную систему счисления и расширение системы остаточных классов .

MULTIPLICATION AND DIVISION IN THE RESIDUE NUMBER SYSTEM USING GALOIS FIELDS GF(p)

The current paper presents an algorithm of multiplication and division in the residual classes based on the theory of Galois fields GF(p). The use of Galois fields GF(p) to solve the problems of arithmetic multiplication and division eliminates a lot of limitations of existing algorithms. The advantage of theproposed algorithm is that it has no restrictions on the dividend and the divisor and it does not use the generalized positional notation and the expansion of the residue number systems.

Текст научной работы на тему «Умножение и деление в системе остаточных классов с использованием полей Галуа GF(p)»

Н.И. Червяков, М.Г. Бабенко, П.А. Ляхов, И.Н. Лавриненко, А.М. Лягин

УМНОЖЕНИЕ И ДЕЛЕНИЕ В СИСТЕМЕ ОСТАТОЧНЫх КЛАССОВ С ИСПОЛьЗОВАНИЕМ ПОЛЕй ГАЛУА GF(p)

N.I. Chervyakov, M.Gr. Babenko, P.A. Lyakhov, I.N. Lavrinenko, A.M. Lyagin

MULTIPLICATION AND DIVISION IN THE RESIDUE NUMBER SYSTEM

USING GALOIS FIELDS GF(p)

Предложен алгоритм умножения и деления в системе остаточных классов, основанный на теории полей Галуа GF(^). Применение полей Галуа GF(^) для решения проблем арифметического умножения и деления устраняет многие ограничения существующих алгоритмов. Преимущество предложенного алгоритма заключается в том, что он не имеет ограничений на делимое и делитель, не использует обобщенную позиционную систему счисления и расширение системы остаточных классов.

КОМПЬЮТЕРНАЯ АРИФМЕТИКА; СИСТЕМА ОСТАТОЧНЫХ КЛАССОВ; МОДУЛЯРНАЯ АРИФМЕТИКА; ПОЛЯ ГАЛУА; ТЕОРИЯ ЧИСЕЛ; ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ.

The current paper presents an algorithm of multiplication and division in the residual classes based on the theory of Galois fields GF(^). The use of Galois fields GF(^) to solve the problems of arithmetic multiplication and division eliminates a lot of limitations of existing algorithms. The advantage of the proposed algorithm is that it has no restrictions on the dividend and the divisor and it does not use the generalized positional notation and the expansion of the residue number systems.

COMPUTER ARITHMETIC; RESIDUE NUMBER SYSTEM; MODULAR ARITHMETIC; GALOIS FIELD; NUMBER THEORY; PARALLEL COMPUTING.

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

Некоторые алгоритмы деления в СОК

в общем случае были разработаны ранее. Эти алгоритмы можно разделить на две категории: с использованием умножения и с использованием вычитания [2, 3]. Большинство алгоритмов на основе умножения предварительно вычисляют обратную величину делителя, после чего эта величина умножается на делимое. Алгоритмы на основе вычитания используют вычитание кратных делителя из делимого до тех пор, пока полученный результат не будет меньше делителя. Некоторые известные алго-

ритмы деления в СОК на основе умножения изложены в [4—8]. Все эти алгоритмы используют преобразование в обобщенную позиционную систему счисления (ОПСС) для нахождения обратной величины делителя и сравнения чисел. Кроме того, эти алгоритмы являются медленными, т. к. требуют выполнения большого количества арифметических действий. Некоторые алгоритмы на основе вычитания представлены в [9, 10]. Эти алгоритмы не требуют вычислений в ОПСС, однако используют некоторые другие немодульные операции [11, 12]. Алгоритм с вычитанием, представленный в [10], кажется наиболее привлекательным для применения на практике, поскольку использует эффективный метод проверки четности для сравнения и обнаружения переполнения диапазона. Большинство существующих алгоритмов обладают различными недостатками, что делает их менее пригодными для решения задачи деления в СОК.

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

Так как эти методы являются итерационными, то их сравнение можно провести по двум критериям:

по общему количеству выполненных итераций;

по количеству операций, выполненных за одну итерацию

Сравнительная оценка по количеству итераций, выполненных, в алгоритмах Ферма и Ньютона приведена на основе компьютерного моделирования, результаты которого показаны на рис. 1 и 2.

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

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

В десятичной арифметике логарифмы часто используются для умножения и деления. В СОК используется аналогичный метод, называемый индексными вычислениями [13]. Использование индексного преобразования над полем Галуа ОР(р) сводит операции умножения и деления к операциям сложения и вычитания, соответственно. Операция умножения является модульной и поэтому может быть реализована в СОК как сложение. С точки зрения аппаратной реализации, сложение в СОК реализуется легче, чем умножение [13, 14]. Деление, напротив, является немодульной операцией в СОК, поэтому использование индексных преобразований над ОР(р) значительно улучшит время выполнения операции и снизит аппаратурные затраты.

При построении умножителей, работающих в модулярной арифметике, можно воспользоваться индексным или «дискретно-логарифмическим» представлением операндов и заменить операцию модулярного умножения операцией модулярного сложения индексов или дискретных логарифмов. Индексное представление модулярного числа основывается на понятии первообразного «корня по простому модулю». Таким корнем является целое число, возведение которого в степень 1, 2, . р— 1 дает неповторяющиеся вычеты по модулю

Индексный метод позволяет получить очень простую реализацию с помощью метода, аналогичного методу вычисления логарифмов. Умножители по модулю р. реализуются с помощью табличного поиска при малом р. (5 бит и менее) и индексного сложения при больших р. (6—10 бит)

[14]. Поэтому в тех случаях, когда диапазон обрабатываемых данных лежит в преде-

лах 6—10 бит, целесообразно использовать умножители и деления на основе индексного исчисления. Однако индексное исчисление может быть использовано только в том случае, когда модуль р. — простое число.

На практике встречаются также случаи, когда модуль р . — произвольное число, поэтому появляется необходимость разработать эффективные методы умножения, пригодные при любом модуле, независимо от того, является ли последний простым числом или нет. Так, например, если реализовать умножитель по модулю р .= 249, который не является простым числом, т. к. 249 = 83-3, то непосредственное использование индексного счисления невозможно. Так как числа 83 и 3 являются простыми, то возможно индексное исчисление по разложенным модулям.

При умножении (делении) по модулю р. сначала определяются индексы чисел, затем эти индексы складываются (вычитаются) по модулю р .—1 и по обратной таблице определяется окончательный результат

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

исходному модулю. Метод индексного исчисления эффективен при обработке данных 6—10 бит и когда модуль представляет собой простое число [14].

Сравнительная оценка общего количества итераций, выполняемых в алгоритмах Ферма и Ньютона, приведена на рис. 1 и 2.

На рис. 1 приведена сравнительная оценка в случае, когда значение делителя фиксировалось, а значение делимого менялось. На рис. 2 наоборот, неизменным оставалось значение делимого, делитель принимал различные значения.

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

Количество операций в каждой итерации в основном определяются операциями расширения и масштабирования.

Операция масштабирования состоит в выполнении деления с нулевым остатком

Рис. 1. Оценка количества итераций методов Ферма и Ньютона в зависимости от разрядности делимого

Рис. 2. Оценка количества итераций методов Ферма и Ньютона в зависимости от разрядности делителя

(Ъ вычитаний и Ъ сложений, где Ъ — количество модулей СОК, по которым проводится масштабирование).

Операции расширения выполняются на основе метода Гарнера, который содержит г операций вычитания и г операций умножения, где г — количество модулей исходной СОК.

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

В настоящей статье рассматривается очень быстрый алгоритм деления в СОК с использованием индексов в ОБ(р). Улучшенный алгоритм обладает следующими свойствами: очень быстр по сравнению с известными алгоритмами, не использует предварительную оценку частного, обратную величину для делителя и операцию расширения базы СОК.

Модулярная арифметика обладает большими возможностями обработки данных

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

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

Индексы в полях Галуа GF(^)

Число I, являющееся решением сравнения qx = A(mod p), называется индексом числа A и обозначается I = ind A. Первообразный корень q называется основанием индекса. Для нахождения индекса числа A по модулю p надо найти первообразный корень q и затем найти решение этого сравнения для данного первообразного корня.

Пример 1. Вычислить индексы по модулю 7 чисел 0, 1, 2, 3, 4, 5, 6. Первообразные корни числа 7 суть 3 и 5.

Решение. Примем основание q = 3. Вычислим 3х для x = 0, 1, 2, 3, 4, 5, 6.

30 = 1 mod 7, 31 = 3 mod 7, 32 = 2 mod 7,

33 = 6 mod 7, 34 = 4 mod 7, 35 = 5 mod 7, 36 = 6 mod 7.

Из этих сравнений следует, что

ind 1 = 0, ind 2 = 2, ind 3 = 1, ind 4 = 4, ind 5 = 5, ind 6 = 3.

Аналогично, индексы по первообразному корню 5:

ind 1 = 0, ind 2 = 4, ind 3 = 5, ind 4 = 2, ind 5 = 1, ind 6 = 3.

Антииндексом числа I называется число а, такое что

I = ind а или а = ind—1I.

Если антииндекс обозначить через N(I), то N(ind а) = а.

П р и м е р 2. Вычислить антииндексы по модулю 7 чисел 0, 1, 2, 3, 4, 5.

Р е ш е н и е . В предыдущем примере приведены индексы чисел от 0 до 6, которые равны 0, 1, 2, 3, 4, 5. Естественно, что число нуль не может иметь индекса, потому что нет такого показателя степени, возведя в которую конечное, отличное от нуля основание, можно было бы получить нуль.

📎📎📎📎📎📎📎📎📎📎