Paper 2014/040

A Fast Modular Reduction Method

Zhengjun Cao, Ruizhong Wei, and 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. MINOR revision.
Keywords
Barrett's reductionMontgomery's reductionlookup-table-based reductionrun-length-based reduction
Contact author(s)
caozhj @ shu edu cn
History
2014-01-15: received
Short URL
https://ia.cr/2014/040
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2014/040}},
      url = {https://eprint.iacr.org/2014/040}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.