|
Published Articles >> Table of Contents >> Abstract
13th IEEE Symposium on Computer Arithmetic (ARITH-13 '97)
p. 234
An IWS Montgomery Modular Multiplication Algorithm
Jean-Claude Bajard, Université de Provence, France
Laurent-Stéphane Didier, Université de Provence, France
Peter Kornerup, University of Odense, Denmark
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.1997.614900
Send link to a friend
| Abstract |
|
The authors present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large, and implementing the system an a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm call be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up.
|
 Additional Information
|
Index Terms- residue number systems, RNS Montgomery modular multiplication algorithm, very large operands, mixed radix, residue number system, processor ring, redundant high-radix implementation, table look-up, computation time
Citation:
Jean-Claude Bajard, Laurent-Stéphane Didier, Peter Kornerup,
"An IWS Montgomery Modular Multiplication Algorithm,"
arith,
p. 234,
13th IEEE Symposium on Computer Arithmetic (ARITH-13 '97),
1997
|
|
