Parallel computational algorithms for generalized Chinese remainder theorem |
| |
Authors: | Yeu-Pong LaiAuthor Vitae Chin-Chen Chang Author Vitae |
| |
Affiliation: | Department of Computer Science and Information Engineering, National Chung Cheng University, Chaiyi 62107, Taiwan, ROC |
| |
Abstract: | Recently, the residue number system (RNS) has been intensively studied. The Chinese remainder theorem (CRT) is a solution to the conversion problem of a number to RNS with a general moduli set. This paper introduces the generalized CRT (GCRT) with parallel algorithms used for the conversion. The GCRT differs from the CRT because it has the advantage of having more applications than does the CRT. The GCRT, however, has a disadvantage in computational performance. To remedy this shortcoming, this paper proposes algorithms that calculate concurrently for some non-related program fragments of GCRT computation. These proposed algorithms also allow the GCRT to compute more efficiently. |
| |
Keywords: | Chinese remainder theorem Parallel computation Residue number system Butterfly network Euclidean algorithm |
本文献已被 ScienceDirect 等数据库收录! |