Paper 2014/1009

A Preliminary FPGA Implementation and Analysis of Phatak’s Quotient-First Scaling Algorithm in the Reduced-Precision Residue Number System

Christopher D. Nguyen, Dhananjay S. Phatak, Steven D. Houston, and Alan T. Sherman


We built and tested the first hardware implementation of Phatak’s Quotient-First Scaling (QFS) algorithm in the reduced-precision residue number system (RP-RNS). This algorithm is designed to expedite division in the Residue Number System for the special case when the divisor is known ahead of time (i.e., when the divisor can be considered to be a constant, as in the modular exponentiation required for the RSA encryption/decryption). We implemented the QFS algorithm using an FPGA and tested it for operand lengths up to 1024 bits. The RP-RNS modular exponentiation algorithm is not based on Montgomery’s method, but on quotient estimation derived from the straightforward division algorithm, with substantial amount of precomputations whose results are read from look-up tables at run-time. Phatak’s preliminary analysis indicates that under reasonable assumptions about hardware capabilities, a single modular multiplication’s (or QFS’s) execution time grows logarithmically with respect to the operand word length. We experimentally confirmed this predicted growth rate of the delay of a modular multiplication with our FPGA implementation. Though our implementation did not outperform the most recent implementations such as that by Gandino, et al., we determined that this outcome was solely a consequence of tradeoffs stemming from our decision to store the lookup tables on the FPGA.

Note: We hope this preliminary work will be helpful to anyone wishing to carry out another implementation of this promising method.

Available format(s)
Publication info
Reduced-Precision Residue Number SystemResidue Number System (RNS)modular exponentiationQuotient-First Scaling (QFS) algorithmcomputer arithmeticFPGA hardware
Contact author(s)
cn1 @ umbc edu
2014-12-25: received
Short URL
Creative Commons Attribution


      author = {Christopher D.  Nguyen and Dhananjay S.  Phatak and Steven D.  Houston and Alan T.  Sherman},
      title = {A Preliminary {FPGA} Implementation and Analysis of Phatak’s Quotient-First Scaling Algorithm in the Reduced-Precision Residue Number System},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1009},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.