Application of the Chinese Remainder Theorem to multi-precision computations

Trukhin V.O., Strongin V.S., Lobanova E.A., Makarov A.G., Nefedev K.V.
 pdf (179K)

This work investigates the application of the Chinese Remainder Theorem (CRT) to improve the efficiency of computations involving large integers in high-performance computing tasks. The relevance of this study arises from the fact that a number of problems in theoretical physics, numerical simulation, and exhaustive search algorithms require integers whose bit length significantly exceeds the capabilities of standard machine data types. This necessitates the use of arbitraryprecision arithmetic and leads to substantial computational overhead. Traditional representations of large integers as sequences of machine words scale poorly and do not efficiently utilize the architecture of graphics processing units (GPUs).

The proposed approach is based on representing integers in a residue number system defined by a set of pairwise coprime moduli. Such a decomposition replaces operations on multi-byte integers with independent modular operations on arrays of residues, enabling natural parallelization. Arithmetic operations including addition, subtraction, and multiplication are performed componentwise within the modular system, while reconstruction of the original integer is carried out using algorithms based on the extended Euclidean algorithm. It is shown that in sequential computations the proposed method does not provide a significant advantage over classical arbitrary-precision arithmetic; however, when implemented on GPUs, a substantial performance gain is achieved due to massive parallelism and independence of operations across moduli. An additional advantage is the reduced risk of overflow and more efficient memory access organization enabled by the use of fixed-width integers.

Thus, the use of the CRT constitutes an effective tool for implementing multipoint computations with large integers in supercomputing systems and can be applied to numerical simulation, cryptography, and exhaustive search algorithms requiring high performance and scalability.

Keywords: multi-precision arithmetic, supercomputers, modular arithmetic, parallel computing
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
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-en.ics.org.ru/journal/article/3773/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Copyright © 2026 Trukhin V.O., Strongin V.S., Lobanova E.A., Makarov A.G., Nefedev K.V.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Website Copyright © 2009–2026 Institute of Computer Science