A Fast Modular Reduction Method

Zhengjun Cao; Ruizhong Wei; Xiaodong Lin

Paper 2014/040 Original: eprint.iacr.org/2014/040 ↗

A Fast Modular Reduction Method

Zhengjun Cao

Ruizhong Wei

Xiaodong Lin

Abstract

We put forth a lookup-table-based modular reduction method which partitions the binary string of an integer to be reduced into blocks according to its runs. Its complexity depends on the amount of runs in the binary string. We show that the new reduction is almost twice as fast as the popular Barrett's reduction, and provide a thorough complexity analysis of the method.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2014-01-15: last updated; 2014-01-15: published
Short URL: https://ia.cr/2014/040
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2014/040,
      author = {Zhengjun Cao and Ruizhong Wei and Xiaodong Lin},
      title = {A Fast Modular Reduction Method},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/040},
      year = {2014},
      url = {https://eprint.iacr.org/2014/040}
}