.png){kind=icon}
.png){kind=icon}
Return
A Discrete Logarithm Number System for Integer Arithmetic Modulo 2k: Algorithms and Lookup Structures
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2008.204.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a k-bit encoding of the k-bit binary integers based on a discrete logarithm representation. The representation supports a discrete logarithm number system (DLS) that allows integer multiplication to be reduced to addition and integer exponentiation to be reduced to multiplication. We introduce right-to-left bit serial conversion, deconversion, and unified conversion/deconversion algorithms between binary and DLS. The conversion algorithms utilize O(k) additions, do not require the use of a multiplier, and are applicable at least up to 128-bit integers. We illustrate the use of the representation in determining a novel and efficient integer power modulo 2(k) operation vertical bar x(y)vertical bar(2k) and compare hardware performance with a current state-of-the-art method. Furthermore, we describe properties of the conversion mappings that allow compact table lookup structures to be employed for direct conversion to and deconversion from the DLS encoding. Our lookup architecture allows 16-bit conversion and deconversion mappings to be realized with table sizes of order 2-8 Kbytes, which is up to a 64 x size reduction of the 128 Kbytes of an arbitrary 16-bits-in, 16-bits-out function table. Performance and area results that demonstrate the effectiveness of the table lookup architecture are given. The lookup methodology extends to other 16-bit integer functions such as multiplicative inverse and squaring operations.
Keywords:
High-speed arithmetic
arithmetic and logic units
computer arithmetic
discrete logarithm
number encodings
conversions
bit serial
integer power
table lookup
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K
View more organizations