Ключевое слово: «модулярная арифметика»

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