Dissertation/Thesis Abstract

Fast modular exponentiation using residue domain representation: A hardware implementation and analysis
by Nguyen, Christopher Dinh, M.S., University of Maryland, Baltimore County, 2013, 129; 1551346
Abstract (Summary)

Using modular exponentiation as an application, we engineered on FPGA fabric and analyzed the first implementation of two arithmetic algorithms in Reduced-Precision Residue Number Systems (RP-RNS): the partial-reconstruction algorithm and quotient-first scaling algorithm. Residue number systems (RNS) provide an alternative representation to the binary system for computation. They offer full parallel computation for addition, subtraction, and multiplication. However, base extension, division, and sign detection become harder operations. Phatak's RP-RNS uses a time-memory trade-off to achieve O(lg N) running time for base extension and scaling, where N is the bit-length of the operands, compared with Kawamura's Cox-Rower architecture and its derivatives, which appear to take O(N) steps and therefore O(N) delay to the best of our knowledge. We implemented the fully parallel RP-RNS architecture based on Phatak's description and architecture diagrams. Our design decisions included distributing the lookup tables among each channel, removing the adder trees, and removing the parallel table access thus trading size for speed. In retrospect, we should have hosted the tables in memory off the FPGA. We measured the FPGA utilization, storage size, and cycle counts. The data we present, though less than optimal, confirms the theoretical trends calculated by Phatak. FPGA utilization grows proportional K log(K) where K is the number of hardware channels. Storage grows proportional to O(N

3 lg lg N). When using Phatak's recommendations,cycle count grows proportional to O(lg N). Our contributions include documentation of our design, architecture, and implementation; a detailed testing methodology; and performance data based on our implementation to enable others to replicate our implementation and findings.

Indexing (document details)
Advisor: Sherman, Alan T., Phatak, Dhananjay S.
Commitee: Patel, Chintan
School: University of Maryland, Baltimore County
Department: Computer Science
School Location: United States -- Maryland
Source: MAI 52/04M(E), Masters Abstracts International
Subjects: Computer Engineering, Computer science
Keywords: Exponentiation, Fpga, Modular, Number, Residue, System
Publication Number: 1551346
ISBN: 978-1-303-68800-3
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy