Generating compact residue number systems bases

[Генерация компактных базисов системы остаточных классов]

V. V. Lutsenko, M. G. Babenko

North-Caucasus Federal University

Аннотация: Современные вычислительные задачи, связанные с обработкой больших чисел, требуют не только высокой точности, но и значительной скорости операций. В данном контексте применение системы остаточных классов предлагает подход к параллельной обработке больших чисел, который применяется в криптографии, обработке сигналов и искусственных нейронных сетях. Ключевой задачей при построении системы остаточных классов является определение её базиса. В статье представлен алгоритм генерации компактных базисов системы остаточных классов, основанный на теореме Диемитко. Предложенный алгоритм генерирует базисы в среднем на 15,5% быстрее, чем построение базисов на основе псевдо-Мерсенновских чисел, и на 75,7% быстрее, чем метод общей фильтрации. Проведённый сравнительный анализ показал, что использование компактных базисов обеспечивает в среднем 12% ускорение модульных операций по сравнению со специальными наборами модулей.

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

Язык публикации: английский

DOI: 10.15514/ISPRAS-2025-37(5)-3