You are looking at a specific version 20141225:140522 of this paper. See the latest version.

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 and Dhananjay S. Phatak and Steven D. Houston and Alan T. Sherman

Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Reduced-Precision Residue Number SystemResidue Number System (RNS)modular exponentiationQuotient-First Scaling (QFS) algorithmcomputer arithmeticFPGA hardware
Contact author(s)
cn1 @ umbc edu
History
2014-12-25: received
Short URL
https://ia.cr/2014/1009
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.