MODULE REDUCTION IN RESIDUE NUMBER-SYSTEMS

Authors
POSCH KC POSCH R
Citation
Kc. Posch et R. Posch, MODULE REDUCTION IN RESIDUE NUMBER-SYSTEMS, IEEE transactions on parallel and distributed systems, 6(5), 1995, pp. 449-454
Citations number
12
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
6
Issue
5
Year of publication
1995
Pages
449 - 454
Database
ISI
SICI code
1045-9219(1995)6:5<449:MRIRN>2.0.ZU;2-Y
Abstract
Residue number systems provide a good means for extremely long integer arithmetic. Their carry-free operations make parallel implementations feasible. Some applications involving very long integers, such as pub lic key encryption, rely heavily on fast module reductions. This paper shows a new combination of residue number systems with efficient modu le reduction methods. Two methods are compared, and the faster one is scrutinized in detail. Both methods have the same order of complexity, O(log n), with n denoting the amount of registers involved.