Modular reduction without precomputational phase

In this paper we show how modular reduction for integers with Barrett and Montgomery algorithms can be implemented efficiently without using a precomputational phase. We propose four distinct sets of moduli for which this method is applicable. The proposed modifications of existing algorithms are very suitable for fast software and hardware implementations of some public-key cryptosystems and in particular of Elliptic Curve Cryptography. Additionally, our results show substantial improvement when a small number of reductions with a single modulus is performed.