Быстрое индексное умножение по модулю

    Введение


    Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

    Постановка задачи


    Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
    0 <= a < p
    0 <= b < p
    p – простое число.
    mod p – операция нахождения остатка по модулю.
    И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).

    Простейшие методы решения


    1. Первое что приходит в голову: умножить, потом разделить и взять остаток. Этот подход имеет право на существование, но чрезвычайно затратен по количеству операций и довольно сложен для реализации.
    2. Второе, что можно придумать, это реализовать эту операцию двумерной таблицей умножения размера p на p. Что имеет смысл если p мало, однако при росте значения p квадратично растут затраты на хранение таблицы (рис. 1).


    Рисунок 1. Таблица умножения по модулю p для p = 11.

    Умножитель на базе индексного метода


    Однако существует метод, который требует одной (или для удобства двух) таблиц размерности p. Метод основан на замене умножения сложением. И может быть схематично проиллюстрирован следующим рисунком (рис. 2):

    Рисунок 2. Индексное умножение.

    Поясним, почему это возможно. Индексное представление числа основывается на понятии первообразного корня по простому модулю p [1]. Первообразным корнем w является целое число, возведение которого в степень 0, 1, 2, …, (p-2) дает неповторяющиеся вычеты по модулю p. Первообразный корень всегда существует для любого простого p (доказано Гауссом в 1801 году). В этом случае каждому целому числу q из промежутка (0; p) можно поставить в соответствие число i такое что: q = (wi) mod p. И таким образом получить следующее соответствие:
    (a*b) mod p <-> w^((ia+ib) mod (p-1)) [2].

    Рассмотрим пример для модуля p = 11. Первообразный корень w для этого значения модуля равен 2. Как несложно убедиться возведение w в степень 0, 1, … 9 дает неповторяющиеся результаты:
    • (20) mod 11 = 1 mod 11 = 1
    • (21) mod 11 = 2 mod 11 = 2
    • (22) mod 11 = 4 mod 11 = 4
    • (23) mod 11 = 8 mod 11 = 8
    • (24) mod 11 = 16 mod 11 = 5
    • (25) mod 11 = 32 mod 11 = 10
    • (26) mod 11 = 64 mod 11 = 9
    • (27) mod 11 = 128 mod 11 = 7
    • (28) mod 11 = 256 mod 11 = 3
    • (29) mod 11 = 512 mod 11 = 6

    Для получения таблицы преобразования между обычным {q} и индексным {i} представлением необходимо отсортировать полученные пары значений в порядке возрастания. Таким образом, таблица прямого преобразования для модуля p = 11 будет выглядеть следующим образом:
    q 1 2 3 4 5 6 7 8 9 10
    i 0 1 8 2 4 9 7 3 6 5
    А таблица обратного преобразования для модуля p = 11 будет выглядеть так:
    i 0 1 2 3 4 5 6 7 8 9
    q 1 2 4 8 5 10 9 7 3 6

    Найдем значение выражения (3*5) mod 11. Числа 3 и 5 имеют соответствующие индексы 8 и 4 (см. таблицу 1). Просуммировав эти индексы по модулю (11-1) = 10 получим результат (8+4) mod 10 = 12 mod 10 = 2. Из таблицы 2 находим, что обратное преобразование для индекса 2 дает конечный результат, равный 4.

    Структурную схему индексного умножителя по модулю m=11 для рассмотренного примера можно посмотреть на следующем рисунке (рис 3):

    Рисунок 3. Схема индексного умножителя для p = 11.

    Нулевые значения для входов


    Если внимательно посмотреть на таблицы, то видно, что там не присутствуют нулевые значения для входных данных. Это связано с тем, что wi != 0 ни при каких значениях i. Этот случай обрабатывается отдельно (либо вводится понятие сингулярности со специальными правилами её обработки). Если на одном из входов умножителя появляется 0, то на выходе тоже будет 0, что непосредственно следует из правил умножения.

    Распараллеливание умножителя


    Оказывается умножение можно сделать ещё быстрее. Если число (p-1) можно разбить на попарно взаимнопростые множители p-1 = m1*m2*…*mr, то операция сложения может быть разбита на r операций сложений меньшей размерности. В этом случае индекс преобразуется в вектор длины r, по следующей формуле: (i mod m1, i mod m2, …, i mod mr). А суммирование производится независимо по каждому элементу вектора.

    Рассмотрим это на примере. Для p = 11 значение p-1 = 10 и оно может быть разбито на взаимнопростые множители единственным образом: 10 = 2*5 (m1 = 2, m2 = 5). В этом случае таблица 1 может быть расписана следующим образом:
    q 1 2 3 4 5 6 7 8 9 10
    i 0 1 8 2 4 9 7 3 6 5
    (i mod 2, i mod 5) (0, 0) (1, 1) (0, 3) (0, 2) (0, 4) (1, 4) (1, 2) (1, 3) (0, 1) (1, 0)
    А таблица обратного преобразования соответственно так:
    (i mod 2, i mod 5) (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 0) (1, 1) (1, 2) (1, 3) (1, 4)
    q 1 9 4 3 5 10 2 7 8 6

    Найдем, как и в прошлом примере, значение (3*5) mod 11. Сначала ищем соответствующие вектора в таблице: 3 -> (0, 3), 5 –> (0, 4). Затем поэлементно складываем ((0 + 0) mod 2, (3 + 4) mod 5) = (0, 2). Из таблицы обратного преобразования находим ответ: (0, 2) -> 4. Схема параллельного умножителя приведена ниже (рис. 4):

    Рисунок 4. Схема параллельного индексного умножителя для p = 11.

    Как искать первообразный корень?


    Если честно не задавался этим вопросом. Я использую полный перебор, начиная с 2 до p. Либо можно использовать готовую последовательность: oeis.org/A046145. Если есть более эффективный метод пишите в комментах.

    Как проектировать сумматор по модулю (p-1)?


    Из-за особенностей входных данных сумматора по модулю (p-1), а именно, что на оба входа приходит число меньше, чем p-1, а значит их сумма меньше чем 2*(p-1). Из этого следует, что можно использовать любой из стандартных сумматоров, выход которого корректируется по следующему алгоритму: если значение больше или равно (p-1), то вычесть из результата (p-1), иначе оставить без изменений.

    Verilog-генератор


    На досуге я написал он-лайн генератор Verilog'а для реализации индексного умножителя по модулю. Там же рисуется схема его работы.
    Verilog для умножения по модулю 11
    Verilog для умножения по модулю 31
    Генератор Verilog для произвольного числа до 1000

    Литература


    [1] ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B2%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D1%8C_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB%29
    [2] www.researchgate.net/publication/224735018_A_fast_RNS_Galois_field_multiplier

    От автора


    Если у вас есть дополнения по статье буду рад их увидеть в комментариях. И ещё статья получилась бедной на ссылочки с подробностями, если у кого что есть кидайте. =)
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 22
    • +1
      Вряд ли тянет на дополнение, но сразу вспомнилась история про «Летмишоую» :-)
      • 0
        В микроэлектронике всегда хотят умножение заменить на что попроще, в том числе на таблицы и сложение. Умножение на константу скорее всего заменяется как раз серией сложений со сдвигами. )
      • +2
        стесняюсь спросить — а для чего это может понадобиться?
        (например я понимаю, зачем менять вычисления с плавающей точкой на целочисленные — в смысле понимаю, зачем нужно сложение и умножение, как часто оно нужно и какие бенефиты от «выполнения на низком уровне»)
        А какие типичные применения «индексного умножения по модулю»?
        • +1
          Ну стесняться незачем. =) Эта статья узкоспециализирована. Теоертически умножение по модулю может возникнуть и просто так в какой-то обыденной задаче. Но вообще этот математический аппарат обычно используется в модулярной арифметике, где все операции выполняются над вычетами (остатками от деления). А модулярная арифметика в свою очередь используется в приборах где требуется высокая скорость арифметических операций (типа DSP) или высокая помехоустойчивость с контролем ошибок.
          • 0
            Да еще и модуль простой должен быть
            • +1
              Ну их обычно такими и стараются выбирать (за исключением разве что случаев 2n, 2n+1, 2n-1). Поскольку вcе модули в базисе должны быть взаимно простыми.
              • 0
                Мне, не зная специфики применения действительно трудно понять почему «их обычно такими и стараются выбирать» :) Но сам метод интересный
                • +1
                  Кольцо вычетов является полем только если модуль простой. На деле это как раз означает существование первообразного корня, отсутствие делителей нуля (a != 0, b !=0, a * b = 0) и прочие радости.
                  • 0
                    А такой вопрос: для данного алгоритма подойдут только простые модули p или любые, которые имеют первообразный корень (2, 4, p^a, 2p^a, где p>2)?
                    • 0
                      Точно не уверен, но, по всей видимости, хватит только наличия первообразного корня.
                      • 0
                        Вопрос интересный, надо будет проверить.
            • +3
              Добавлю, что статью писал больше для тех кто впоследствие прийдет с поисковиков. Туго с этим материалом в рунете…
              • 0
                Вычисления по простому модулю используются в шифровании, избыточном кодировании (самовосстанавливающиеся коды как на компакт-дисках и т.п.) и других подобных приложениях.
                • +2
                  Для реализации вычислений над конечными полями, которые используются, среди прочего, в теории кодов, исправляющих ошибки (см., например, Коды Рида-Соломона, используемые при записи данных на компакт-диски и еще много где).

                  Сама идея сходна использованию логарифмов: вместо умножения двух вещественных чисел можно складывать их логарифмы (именно на этом основан принцип работы логарифмической линейки).
                • 0
                  В статье не указано главное — то, что речь идет о «железном» вычислении, а не о программном.
                  • +1
                    Извиняюсь, нашел где это написано.
                    Стыдно-то как…
                  • –2
                    Спасибо за статью, но вообще это арифметика для 8-ого класса физмат. школы.
                    • 0
                      Вероятно я учился в неправильной физ-мат школе. =) ИМХО, тут слишком большой математический аппарат задействован (см. ключевые слова), что бы додуматься до чего-то подобного в 8 классе. Разве что ПРО-олимпиадники справятся.
                      • –1
                        Задействованный «математический аппарат» как раз и называется арифметикой остатков. В моей гуманитарной гимназии города зажопинска это был годичный курс по 1 уроку в неделю, так и назывался «арифметика». Как в других школах — не знаю.
                        Что до ключевых слов, то они абстрактны и мне ничего не говорят. Про «логарифметику» ничего не знает даже яндекс.
                    • +1
                      > Как искать первообразный корень? Я использую полный перебор, начиная с 2 до p

                      Можно ускорить проверку числа на первообразность. Пусть p-1 = k1a1k2a2k3a3… — разложение на простые множители, тогда если g(p-1)/ki mod p не равно 1 для всех i, а gp-1 равно 1, то g — первообразный корень.
                      Всего таких k для каждого числа очень мало. Разложить все числа от 2 до p на простые множители можно тоже относительно быстро с помощью решета Эратосфена.

                      Таким образом можно перебрать за приемлемое время первообразный хоть для p порядка 109 :)
                      • 0
                        Спасибо. Это какая-то известная теорема?
                        • 0
                          Не знаю, это не сложно придумать.

                          Пусть i наименьшее число, что gi равно 1, тогда если i = p-1, то g первообразный иначе нет.
                          Очевидно, что gi*x равно 1 для целых x и только они (из-за наименьшести i). Тогда из того что мы проверили gp-1 = 1 следует что p-1=i*x, то есть i делит p-1, что тоже самое что «i равно p-1, или i делит хоть что-то из (p-1)/ki». Если i = p-1 — все отлично, иначе если i делит (p-1)/ki то g(p-1)/ki тоже будет равно 1, что мы собственно и проверяем.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.