Will, M. A., & Ko, R. K. L. (2016). Computing Mod with a Variable Lookup Table. In P. Mueller, S. M. Thampi, M. Z. A. Bhuiyan, R. Ko, R. Doss, & J. M. A. Calero (Eds.), SSCC 2016: International Symposium on Security in Computing and Communication (Vol. 625, pp. 3–17). Singapore: Springer Nature Singapore Pte Ltd. https://doi.org/10.1007/978-981-10-2738-3_1
Abstract
Encryption algorithms are designed to be difficult to break without knowledge of the secrets or keys. To achieve this, the algorithms require the keys to be large, with some having a recommend size of 2048-bits or more. However most modern processors only support computation on 64-bits at a time. Therefore standard operations with large numbers are more complicated to implement. One operation that is particularly challenging to efficiently implement is modular reduction. In this paper we propose a highly-efficient algorithm for solving large modulo operations; it has several advantages over current approaches as it supports the use of a variable sized lookup table, has good spatial and temporal locality allowing data to be streamed, and only requires basic processor instructions. Our proposed algorithm is theoretically compared to widely used modular algorithms, and shows improvements over other algorithms using predefined lookup tables.
Publisher
Springer Nature Singapore Pte Ltd
Rights
© Springer Nature Singapore Pte Ltd. 2016.This is the author's accepted version. The final publication is available at Springer via dx.doi.org/10.1007/978-981-10-2738-3_1
