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

Abstract

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