Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Barrett's reduction; Montgomery's reduction; lookup-table-based reduction; run-length-based reduction

Date: received 14 Jan 2014

Contact author: caozhj at shu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20140115:143728 (All versions of this report)

Short URL: ia.cr/2014/040

Discussion forum: Show discussion | Start new discussion