Revisiting Sum of Residues Modular Multiplication
In the 1980s, when the introduction of public key cryptography spurred interest in modular multiplication, many implementations performed modular multiplication using a sum of residues. As the field matured, sum of residues modular multiplication lost favor to the extent that all recent surveys have...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2010-01-01
|
| Series: | Journal of Electrical and Computer Engineering |
| Online Access: | http://dx.doi.org/10.1155/2010/657076 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550396770385920 |
|---|---|
| author | Yinan Kong Braden Phillips |
| author_facet | Yinan Kong Braden Phillips |
| author_sort | Yinan Kong |
| collection | DOAJ |
| description | In the 1980s, when the introduction of public key
cryptography spurred interest in modular multiplication, many
implementations performed modular multiplication using a sum
of residues. As the field matured, sum of residues modular
multiplication lost favor to the extent that all recent surveys
have either overlooked it or incorporated it within a larger class
of reduction algorithms.
In this paper, we present a new taxonomy of modular multiplication
algorithms. We include sum of residues as one of four
classes and argue why it should be considered different to the
other, now more common, algorithms. We then apply techniques
developed for other algorithms to reinvigorate sum of residues
modular multiplication. We compare FPGA implementations of
modular multiplication up to 24 bits wide. The sum of residues
multipliers demonstrate reduced latency at nearly 50% compared
to Montgomery architectures at the cost of nearly doubled circuit
area. The new multipliers are useful for systems based on the
Residue Number System (RNS). |
| format | Article |
| id | doaj-art-0d499ce49ede47edacaba2f1cebef4f4 |
| institution | Kabale University |
| issn | 2090-0147 2090-0155 |
| language | English |
| publishDate | 2010-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Electrical and Computer Engineering |
| spelling | doaj-art-0d499ce49ede47edacaba2f1cebef4f42025-02-03T06:06:50ZengWileyJournal of Electrical and Computer Engineering2090-01472090-01552010-01-01201010.1155/2010/657076657076Revisiting Sum of Residues Modular MultiplicationYinan Kong0Braden Phillips1Department of Electronic Engineering, Macquarie University, North Ryde, NSW 2109, AustraliaDepartment of Electrical and Electronic Engineering, The University of Adelaide, North Terrace, SA 5005, AustraliaIn the 1980s, when the introduction of public key cryptography spurred interest in modular multiplication, many implementations performed modular multiplication using a sum of residues. As the field matured, sum of residues modular multiplication lost favor to the extent that all recent surveys have either overlooked it or incorporated it within a larger class of reduction algorithms. In this paper, we present a new taxonomy of modular multiplication algorithms. We include sum of residues as one of four classes and argue why it should be considered different to the other, now more common, algorithms. We then apply techniques developed for other algorithms to reinvigorate sum of residues modular multiplication. We compare FPGA implementations of modular multiplication up to 24 bits wide. The sum of residues multipliers demonstrate reduced latency at nearly 50% compared to Montgomery architectures at the cost of nearly doubled circuit area. The new multipliers are useful for systems based on the Residue Number System (RNS).http://dx.doi.org/10.1155/2010/657076 |
| spellingShingle | Yinan Kong Braden Phillips Revisiting Sum of Residues Modular Multiplication Journal of Electrical and Computer Engineering |
| title | Revisiting Sum of Residues Modular Multiplication |
| title_full | Revisiting Sum of Residues Modular Multiplication |
| title_fullStr | Revisiting Sum of Residues Modular Multiplication |
| title_full_unstemmed | Revisiting Sum of Residues Modular Multiplication |
| title_short | Revisiting Sum of Residues Modular Multiplication |
| title_sort | revisiting sum of residues modular multiplication |
| url | http://dx.doi.org/10.1155/2010/657076 |
| work_keys_str_mv | AT yinankong revisitingsumofresiduesmodularmultiplication AT bradenphillips revisitingsumofresiduesmodularmultiplication |