Система остаточных классов 1

Ни для кого не секрет, что математика – наука абстрактная и в своем "чистом" виде никакого отношения к реальному миру не имеет. Многие, конечно попробуют эту мысль оспорить. Однако заставляет задуматься хотя бы тот факт, что разные народы в различные периоды времени даже считали по-разному. Стоит только вспомнить крайне неэффективную систему счисления древних римлян. Греки вместо чисел использовали буквы собственного алфавита, как и славяне. В Вавилоне появилась шестидесятеричная система счисления, которая нашла отражение в подсчете времени (60 минут в часе, 60 секунд в минуте) и углов. И египтяне конечно же отличились, первыми придумав десятичную, хотя и непозиционную, систему счисления. Иными словами – кто как придумал, тот так и считал.

Настоящую революцию произвела придуманная в Индии не позднее V века позиционная десятичная система счисления. Основным достижением индийцев стало использование в качестве одной из цифр нуля. Именно этот факт делает данную систему счисления столь удобной – теперь можно записать любое число, используя всего 10 различных символов и не изобретая новый для каждого нового разряда. Величина числа зависит от позиции в нем цифр и их количества.

Изобретение современной позиционной системы счисления (арабских цифр) дало серьезный импульс развитию математики. Была фактически решена проблема арифметических операций – их теперь можно было выполнять интуитивно понятным, быстрым и эффективным способом, который не меняется уже более пятнадцати веков. Дальнейшее развитие идеи позиционности сделало принципиально возможным создание современной вычислительной техники – она функционирует на основе двоичной системы счисления.

Проблема

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

Современные вычислительные системы, несмотря на всю свою мощь, все-таки ограничены. И дело даже не в том, что они не могут, например, сделать точный прогноз погоды или расшифровать ДНК. Ограниченность проявляется в самой незначительной, казалось бы, части – диапазоне работы с числами. Просто компьютер способен работать лишь с ограниченным отрезком чисел, который определяется разрядной сеткой процессора. Многие устройства "понимают" числа размером 32 бита (двоичных разряда), другие – 64. Крайне мало 128-ми битных вычислительных элементов, все остальное – вообще единичные случаи. Малая разрядность чисел приводит к невысокой точности вычислений, а многие алгоритмы и вовсе требуют запредельной разрядности. Так например схема шифрования RSA в современном варианте считается достаточно безопасной при длине ключа 2048 бит, что вызывает определенные затруднения при реализации.

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

Назовем некоторое число b основанием системы счисления. Тогда число X, представленное в системе счисления с основанием b набором из n цифр \{x_{0},x_{1},...,x_{n}\}, определяется следующим образом:

X=\sum_{i=0}^{n}x_{i}b^{i}.

Например, в десятичной системе счисления число 5318 есть ни что иное, как 5\cdot10^{3}+3\cdot10^{2}+1\cdot10^{1}+8\cdot10^{0}. Таким же образом все работает в двоичной, троичной, восьмеричной системе и так далее. А теперь представим, что основанием системы счисления является число 2^{32}. Все числа от 0 до 2^{32}-1=4294967295 будут условными цифрами данной системы. Причем данный диапазон полностью покрывает все 32-х битные числа. То есть теперь любое число можно представить в виде набора тридцатидвухбитных цифр. Такой подход применяется для организации вычислений с большими числами на стандартной аппаратуре. При этом мы все равно не избавляемся от сложностей: нельзя забывать о необходимости выполнять переносы между разрядами нашего большого числа, возникающие при выполнении операций сложение и умножение, что делает вычисления достаточно медленными. Некоторый выход из ситуации предлагает модулярная арифметика.

Система остаточных классов

Ранее мы пришли к выводу, что позиционность не всегда хорошо. Рассмотрим теперь непозиционный подход к системам счисления. Под непозиционностью понимается отсутствие очевидной связи между разрядами или, иными словами, отсутствие переносов. Одной из самых используемых непозиционных систем счисления является Система остаточных классов (СОК, Residue Number System – RNS). СОК основывается на теории сравнений и была предложена советским математиком Израилем Яковлевичем Акушским в 50-е годы двадцатого века. Теорию вычислений в СОК иногда называют модулярной арифметикой, основной теоремой которой является Китайская теорема об остатках (КТО, Chinese remainder theorem – CRT), одна из формулировок которой приведена ниже [1].

Теорема. Пусть p_1,p_2,...,p_n есть некоторые натуральные взаимнопростые числа и P=p_1\cdot{p_2}\cdot{...}\cdot{p_n}. Тогда любое число X, такое что 0\leqslant{X}\leqslant{P} может быть однозначно представлено в виде последовательности (x_1,x_2,...,x_n), где x_i=X\mod{p_i}.

Последовательность (x_1,x_2,...,x_n) и есть представление числа X в системе остаточных классов. Каждое из чисел x_i называется разрядом числа в СОК. Отметим, что числа x_i являются остатками от деления на числа p_i, откуда 0\leqslant{x_i}<p_i. Именно этот факт отражает основные свойства СОК – снижение разрядности. Все дело в том, что для вычисления суммы или произведения двух чисел, представленных в СОК, достаточно сложить и умножить соответственные остатки-разряды:

A=(a_1,a_2,...,a_n),\;B=(b_1,b_2,...,b_n)

A+B\mod\,P= \\ =(a_1+b_1\mod\,p_1,a_2+b_2\mod\,p_2,...,{a_n+b_n\mod\,p_n)}

A\cdot{B}\mod\,P= \\ =(a_1\cdot{b_1}\mod\,p_1,a_2\cdot{b_2}\mod\,p_2,...,{a_n\cdot{b_n}\mod\,p_n)}

Преимущества такого подхода очевидны: мы выполняем операции одновременно по различным основаниям так как они не зависят друг от друга. Иными словами, помимо снижения разрядности мы добавляем параллелизм, который принципиально невозможен в позиционной системе. Это идеально ложится под современные вычислительные средства: параллельные вычисления развиваются в последнее время максимально возможными темпами, проявляясь не только в архитектуре компьютеров, но и при разработке встраиваемых решений, основанных, например, на ПЛИС архитектуры FPGA.

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

Рис. 1. Ускорение операции возведения в степень при использовании СОК.

Основной проблемой модулярной арифметики и СОК в частности является существование так называемых немодульных операций. К такому классу операций относятся, например, сравнение и деление чисел. Данные операции имеют позиционную природу и не могут быть выполнены без вычисления какой-либо характеристики числа, определяющей его позицию в числовом ряде, что приводит к восстановлению позиционного представления числа в том или ином роде. Работы многих исследователей направлены на максимальную оптимизацию немодульных операций в СОК. Однако наиболее эффективными остаются алгоритмы, сводящие использование таких операций к минимуму. Хорошей областью для применения СОК таким образом является криптография, сводящаяся к умножению, сложению и возведению в степень [3].

Пример

Рассмотрим работу в СОК с основаниями \{2,3,5,7\}. Динамическим диапазоном для данной системы будет число P=2 \cdot 3 \cdot 5 \cdot 7 = 210, следовательно, в соответствии с КТО все числа, представимые в ней, не должны превышать этого числа. Переведем числа 63 и 79 в нашу СОК, для этого возьмем остатки от деления данных чисел по каждому из модулей и составим из них кортежи:

63=(1,0,3,0),\;79=(1,1,4,2)

Найдем сумму данных чисел:

63+79=\\=(1+1\mod\,2,0+1\mod\,3,3+4\mod\,5,0+2\mod\,7)=\\=(0,1,2,2).

Для проверки результата найдем позиционное значение суммы и так же переведем его в СОК.

63+79=142=(0,1,2,2).

Умножим полученное число на 2 в СОК. Здесь 2=(0,2,2,2)

142 \cdot 2 = (0,1,2,2) \cdot (0,2,2,2) = (0,2,4,4),

что соответствует реальности, так как 142 \cdot 2=284\mod\,210=74=(0,2,4,4).

Вывод

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

  • СОК позволяет упростить и уменьшить архитектуру вычислительных электронных устройств, за счет чего повышается не только скорость, но и энергетическая эффективность продуктов.
  • СОК часто используется как средство для синтеза устройств высокой надежности, ее "параллельная" природа позволяет за счет введения избыточных оснований строить высокоэффективные помехоустойчивые коды.
  • Криптографические приложения не ограничиваются одним лишь ускорением работы с длинными числами; СОК является хорошей базой для построения схем разделения секрета, обладающих выгодными относительно аналогов свойствами.
  • В системах цифровой обработки сигналов (ЦОС, DSP) СОК показала себя как выгодный инструмент повышения эффективности цифровых фильтров, о чем свидетельствует огромное количество работа в данной области.
  • Некоторые приложения нашла СОК в системах связи, примером чему является оптимизация технологии CDMA за счет внедрения модулярных преобразований.

Все преимущества, возникающие при применении СОК, получены благодаря тому, что мы изменили свой взгляд на системы счисления. Иногда нетривиальный взгляд на математические объекты может дать перспективные результаты.

Литература

  1. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Нейрокомпьютеры в остаточных классах. – М.: Радиотехника, 2003. – 272 с.
  2. Дерябин М.А., Зайцев А.А. Использование модулярной арифметики для ускорения выполнения операций с числами большой разрядности. // Вестник УГАТУ – Уфа: Издательство УГАТУ, 2013. Т. 17, № 5 (58). – С. 245–251.
  3. Червяков Н. И., Евдокимов А. А., Галушкин А. И., Лавриненко И. Н., Лавриненко А. В. Применение искусственных нейронных сетей и системы остаточных классов в криптографии. – М.: «Физматлит», 2012. – 280 с.

One comment on “Система остаточных классов

  1. Pingback: Перевод чисел между системами счисления ← Максим Дерябин

Leave a Reply


Add your ORCID here. (e.g. 0000-0002-7299-680X)