Все выпуски

[ Switch to English ]

Применение китайской теоремы об остатках для работы с длинной арифметикой

Трухин В.О., Стронгин В.С., Лобанова Э.А., Макаров А.Г., Нефедев К.В.
 pdf (179K)

В работе рассматривается применение китайской теоремы об остатках (КТО) для повышения эффективности вычислений с большими целыми числами в задачах высокопроизводительных вычислений. Актуальность исследования обусловлена тем, что в ряде задач теоретической физики, численного моделирования и переборных алгоритмов используются числа разрядности, существенно превышающей возможности стандартных машинных типов данных, что приводит к необходимости применения длинной арифметики и сопровождается значительными вычислительными затратами. Традиционные методы представления длинных чисел в виде последовательностей слов плохо масштабируются и недостаточно эффективно используют архитектуру графических процессоров (GPU).

Предложенный подход основан на представлении числа в системе вычетов по набору попарно взаимно простых модулей. Такое разложение позволяет заменить операции над многобайтными числами на независимые модульные операции над массивами остатков, что обеспечивает возможность их естественного распараллеливания. Арифметические операции сложения, вычитания и умножения выполняются покомпонентно в модульной системе, а восстановление исходного числа осуществляется с использованием алгоритмов, основанных на расширенном алгоритме Евклида. Показано, что при последовательных вычислениях предложенный метод не имеет существенного преимущества по сравнению с классической длинной арифметикой, однако при реализации на GPU достигается значительный рост производительности за счет массового параллелизма и независимости операций по модулям. Дополнительным достоинством является снижение риска переполнения и более эффективная организация доступа к памяти благодаря использованию чисел фиксированной разрядности.

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

Ключевые слова: большие числа, суперкомпьютеры, модульная арифметика, параллельные вычисления
Цитата: Трухин В.О., Стронгин В.С., Лобанова Э.А., Макаров А.Г., Нефедев К.В. Применение китайской теоремы об остатках для работы с длинной арифметикой // Компьютерные исследования и моделирование, 2026, т. 18, № 5, с. 1121-1128
Citation in English: Trukhin V.O., Strongin V.S., Lobanova E.A., Makarov A.G., Nefedev K.V. Application of the Chinese Remainder Theorem to multi-precision computations // Computer Research and Modeling, 2026, vol. 18, no. 5, pp. 1121-1128
DOI: 10.20537/2076-7633-2026-18-5-1121-1128
URL: http://crm.ics.org.ru/journal/article/3773/
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Copyright © 2026 Трухин В.О., Стронгин В.С., Лобанова Э.А., Макаров А.Г., Нефедев К.В.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Website Copyright © 2009–2026 Институт компьютерных исследований