eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
You are looking at a specific version 20140115:143728 of this paper.
See the latest version.
Paper 2014/040
A Fast Modular Reduction Method
Zhengjun Cao and 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
-
CC BY
