Основные понятия модулярной арифметики

В обычной жизни мы обычно пользуемся позиционной системой счисления. В позиционной системе счисления значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) [1]. Однако существуют и так называемые «непозиционные системы счисления», к одной из которых относится «система счисления в остатках» (или в оригинале Residue Number System (RNS)), являющаяся основой модулярной арифметики. Модулярная арифметика базируется на «Китайской теореме об остатках» [2], которая для нашего случая звучит следующим образом:

Для любой системы взаимно простых чисел p₁, … p_n, любое число X из диапазона [0; M), где M = p₁*p₂*…*p_n взаимооднозначно представимо в виде вектора (a₁, a₂, …, a_n), гдеa_i = X%p_i (здесь и далее «%» — операция взятия остатка от целочисленного деления X наp_i).

p₁, … p_n – модули системы

a₁, a₂, …, a_n – остатки (вычеты) числа по заданной системе модулей

На первый взгляд непонятно какое преимущество может дать такая система, однако существует 2 свойства, которые позволяют эффективно использовать модулярную арифметику в некоторых областях микроэлектроники:

1. Отсутствие переноса разрядов в сложении и умножении. Пусть нам дано два числа X₁ и X₂, представленные в виде системы остатков (x₁₁, x₁₂, …, x_1n) и (x₂₁, x₂₂, …, x_2n) по системе взаимнопростых чисел (p₁, p₂, …, p_n). В этом случае:

2. X₃ = X₁ + X₂ = ((x₁₁+x₂₁)%p₁, (x₁₂+x₂₂)%p₂, …, (x_1n+x_2n)%p_n)

3. X₄ = X₁ * X₂ = ((x₁₁*x₂₁)%p₁, (x₁₂*x₂₂)%p₂, …, (x_1n*x_2n)%p_n)

4. То есть что бы сложить или умножить два числа, достаточно сложить или умножить соответствующие элементы вектора, что для микроэлектроники означает, что это можно сделать параллельно и из-за малых размерностей p₁, p₂, …, p_n сделать очень быстро.

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

Обычное умножение	Модулярное умножение

Но не всё так гладко, как хотелось бы. В отличие от позиционной системы счисления, следующие операции (называемые «немодульными») выполняются сложнее, чем в позиционной системе счисления: сравнение чисел, контроль переполнения, деление, квадратный корень и.т.д. Первые успешные попытки применения модулярной арифметики в микроэлектронике были предприняты ещё в 1950-х годах, но из-за сложностей с немодульными операциями интерес несколько утих. Однако в настоящее время модулярная арифметика снова возвращается в микроэлектронику по следующим причинам:

· большое распространение мобильных процессоров, в которых требуется высокая скорость при маленьком потреблении энергии. Отсутствие переноса в арифметических операциях сложения/умножения позволяет снизить потребление энергии.

· увеличивающаяся плотность элементов на кристалле в некоторых случаях не позволяет провести полное тестирование, поэтому растет важность устойчивости процессоров к возможным ошибкам.

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

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

Прямое преобразование

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

Пример: Пусть требуется найти представление числа X = 25 по системе модулей (3, 5, 7). X = (25%3, 25%5, 25%7) = (1, 0, 4).

Реализация нахождения вычета в микроэлектронике по заданному модулю строится на следующих свойствах вычетов:

(a+b) % p = (a%p + b%p)%p

(a*b) % p = (a%p * b%p)%p

Любое число X можно записать в виде X%p = (x_n-1*2^n-1 + x_n-2*2^n-2 + x₀*2⁰)%p = ((x_n-1)%p*2^n-1%p) + ((x_n-2)%p*2^n-2%p) + … + x₀%p)%p. Поскольку в данном случае x_n-1, … x₀ равны 0 или 1, то фактически нам требуется сложить вычеты вида (2ⁱ%p).

Пример: пусть задано число 25 или в двоичной системе счисления 11001 и требуется найти остаток по модулю 7.

25%7 = (1*2⁴ + 1*2³ + 0*2² + 0*¹ + 1*2⁰)%7 = (2⁴%7 + 2³%7 + 1%7)%7 = (2 + 1 + 1)%7 = 4

Систему используемых модулей подбирают под конкретную задачу. Например, для представления 32-х битных чисел достаточно следующей системы модулей: (7, 11, 13, 17, 19, 23, 29, 31) – все они взаимнопросты друг с другом, их произведение равно 6685349671 > 4294967296. Каждый из модулей не превышает 5 бит, то есть операции сложения и умножения будут производиться над 5-битными числами.

Особое значение так же имеет система модулей вида: (2ⁿ-1, 2ⁿ, 2ⁿ+1) в связи с тем, что прямое и обратное преобразование для них выполняется простейшим образом. Что бы получить остаток от деления на2ⁿ достаточно взять последние n цифр двоичного представления числа.

Арифметические операции

Пример: пусть задана система модулей (3, 5, 7), то есть мы можем выполнять операции, результат которых не превышает 3*5*7 = 105. Умножим два числа 8 и 10.

8 = (8%3, 8%5, 8%7) = (2, 3, 1)

10 = (10%3, 10%5, 10%7) = (1, 0, 3)

8*10 = ((2*1)%3, (3*0)%5, (1*3)%7) = (2, 0, 3)

Проверяем

80 = (80%3, 80%5, 80%7) = (2, 0, 3)

Обратное преобразование

Обратное преобразование из системы счисления в остаточных классах в позиционную систему счисления производится одним из двух способов:

1. На базе Китайской теоремы об остатках или системы ортогональных базисов

2. На базе полиадического кода (другие названия mixed-radix system, система, со смешанным основанием)

Остальные предложенные в различной литературе способы, по сути, являются смесью этих двух.

Способ, основанный на Китайской теореме об остатках, базируется на следующей идее:

X = (x₁, x₂, … x_n) = (x₁, 0, …, 0) + (0, x₂, …, 0) + … + (0, 0, …., x_n) = x₁*(1, 0, …, 0) + x₂*(0, 1, …, 0) + … + x_n*(0, 0, …, 1).

То есть для обратного преобразования требуется найти систему ортогональных базисов B1 = (1, 0, …, 0), B2 = (0, 1, …, 0), …, BN = (0, 0, …, 1). Эти вектора находятся один раз для заданного базиса, а для их поиска требуется решить уравнение вида: (M_i*b_i)%p_i = 1, где M_i = M/p_i, а b_i – искомое число. В этом случае позиционное представление B_i = M_i*b_i и

X = (x₁*(M₁*b₁) + x₂*(M₂*b₂) + … + x_n*(M_n*b_n))%M

Пример: пусть задана система модулей (3, 5, 7), найдем значения M_i и b_i (0 < i <= 3)

M = 3*5*7 = 105

M₁ = 105/3 = 35

M₂ = 105/5 = 21

M₃ = 105/7 = 15

(35*b₁)%3 = 1 => b₁ = 2

(21*b₂)%5 = 1 => b₂ = 1

(15*b₃)%7 = 1 => b₃ = 1

Теперь преобразуем какое-нибудь число в системе остаточных классов. Положим

X = (2, 3, 1) = (2*35*2 + 3*21*1 + 1*15*1)%105 = (140 + 63 + 15)%105 = 218%105 = 8

Минус этого метода заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел (M₁, …, M_n), а так же операция взятия остатка по модулю большого числа M.

Способ на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел p₁, … p_n, как [4]:

X = a₁ + a₂*p₁ + a₃*p₁*p₁ + a_n-1*p₁*p₂*…*p_n-2 + a_n*p₁*p₂*…*p_n-1, где 0 < a_i < p_i

· X%p₁ = x₁ = a₁

· (X – a₁)%p₂ = (x₂-a₁)%p₂ = a₂*p₁

· (X - (a₁ + a₂*p₁))%p₃ = (x₃ – (a₁ + a₂*p₁))%p₃ = a₃*p₁*p₂

· …

Отсюда вытекает следующий итеративный процесс поиска исходного числа:

· SUM = x₁

· SUM = SUM + (x₂-SUM)%p₂

· SUM = SUM + (x₃-SUM)%p₃

· …

· SUM = SUM + (x_n-SUM)%p_n

Пример: Рассмотрим тот же пример — найдем позиционное представление числа X = (2, 3, 1) в системе модулей (3, 5, 7)

1. SUM = 2

2. SUM = SUM + (x₂-SUM)%p₂ = 2 + (3-2)%5 = 3

3. SUM = SUM + (x₃-SUM)%p₃ = 3 + (1 - 3)%7 = 3 + (-2)%7 = 3 + (7-2)%7 = 3 + 5 = 8

Замечание: в данном случае в процессе вычитания у нас получилось отрицательное число, которое мы как бы скомпенсировали, добавив 7%7 = 0.