Revisiting sum of residues modular multiplication

Yinan Kong*, Braden Phillips

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)
    27 Downloads (Pure)


    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).

    Original languageEnglish
    Article number657076
    Pages (from-to)1-9
    Number of pages9
    JournalJournal of Electrical and Computer Engineering
    Publication statusPublished - 2010

    Bibliographical note

    Copyright the Author(s) 2010. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.


    Dive into the research topics of 'Revisiting sum of residues modular multiplication'. Together they form a unique fingerprint.

    Cite this