Quotient Approximation Modular Reduction, by Aurélien Greuet and Simon Montoya and Clémence Vermeersch
admin
1 min read
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.
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.
