A new Euclidean division algorithm for residue number systems

Author

Bajard, Jean-Claude ; Didier, Laurent-Stéphane ; Muller, Jean-Michel

Author_Institution

Univ. de Provence, Marseille, France

fYear

1996

Firstpage

45

Lastpage

54

Abstract

We propose in this paper a new algorithm and architecture for performing divisions in residue number systems. Our algorithm is suitable for residue number systems with large moduli, with the aim of manipulating very large integers on a parallel computer or a special-purpose architecture. The two basic features of our algorithm are on one hand the use of a high-radix division method, and on the other hand the use of a floating-point arithmetic that should run in parallel with the modular arithmetic

Keywords

computational geometry; digital arithmetic; floating point arithmetic; residue number systems; Euclidean division algorithm; floating-point arithmetic; high-radix division method; large moduli; modular arithmetic; parallel computer; residue number systems; special-purpose architecture; very large integers; Algorithm design and analysis; Cathode ray tubes; Computer architecture; Concurrent computing; Floating-point arithmetic; Newton method;

fLanguage

English

Publisher

ieee

Conference_Titel

Application Specific Systems, Architectures and Processors, 1996. ASAP 96. Proceedings of International Conference on

Conference_Location

Chicago, IL

ISSN

2160-0511

Print_ISBN

0-8186-7542-X

Type

conf

DOI

10.1109/ASAP.1996.542800

Filename

542800