Cryptology ePrint Archive: Report 2014/755

Computing Mod Without Mod

Mark A. Will and Ryan K. L. Ko

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 algorithms 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 implement efficiently 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, before practically compared against the state-of-the-art GNU Multiple Precision (GMP) large number library.

Category / Keywords: mod, modulo, modulus, modular reduction, algorithm, lookup table, fast modular reduction

Date: received 28 Sep 2014

Contact author: willm at waikato ac nz

Available format(s): PDF | BibTeX Citation

Version: 20140929:083250 (All versions of this report)

Short URL: ia.cr/2014/755

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]