Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
modmodulomodulusmodular reductionalgorithmlookup tablefast modular reduction
Contact author(s)
willm @ waikato ac nz
History
2014-09-29: received
Short URL
https://ia.cr/2014/755
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/755,
      author = {Mark A.  Will and Ryan K.  L.  Ko},
      title = {Computing Mod Without Mod},
      howpublished = {Cryptology ePrint Archive, Paper 2014/755},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/755}},
      url = {https://eprint.iacr.org/2014/755}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.