Knowing the quotient of the Euclidean division of an integer by the modulus allows to easily recover the remainder. We propose a way to compute efficiently, without divisions, an approximation of this quotient. From this approximation, both full and partial reductions are deduced. The resulting algorithms are modulus specific: the sequence of operations to perform in order to get a reduction depends on the modulus and the size of the input.
We analyse the cost of our algorithms for a usecase coming from post-quantum cryptography. We show that with this modulus, on a CPU with a slow multiplication, our method gives an algorithm faster than prior art algorithms.
Category / Keywords: implementation / modular reduction, lattice-based cryptography Date: received 30 Mar 2022, last revised 8 Apr 2022 Contact author: simon montoya at idemia com Available format(s): PDF | BibTeX Citation Version: 20220408:163915 (All versions of this report) Short URL: ia.cr/2022/411