Lazy Reduction and Multi-Precision Division Based on Modular Reductions
Shuguo Li, Zhen Gu · 2018
Lazy reduction and multi-precision division are significant methods in fields involving Residue Number Systems like pairings and fully homomorphic encryption. In this paper, we present lazy reductions and multi-precision divisions based on Montgomery and Barrett modular reductions. Also, simplified parameter choices in modular reductions and a new method of multi-precision division are proposed. The proposed method of multi-precision division requires fewer cycles than the block-wise method and fewer multiplier resources than the lazy Barrett modular reduction.