Paper 2022/411

Quotient Approximation Modular Reduction

Aurélien Greuet, Simon Montoya, and Clémence Vermeersch


Modular reduction is a core operation in public-key cryptography. While a standard modular reduction is often required, a partial reduction limiting the growth of the coefficients is enough for several usecases. 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.

Available format(s)
Publication info
Preprint. MINOR revision.
modular reductionlattice-based cryptography
Contact author(s)
simon montoya @ idemia com
2022-04-08: revised
2022-03-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aurélien Greuet and Simon Montoya and Clémence Vermeersch},
      title = {Quotient Approximation Modular Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/411},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.