Modular Reduction without Pre-computation for Special Moduli

We present Montgomery modular multiplication algorithms for special moduli that do not require the pre-computation step. We generalize previous approaches and remove pre-computation steps where the inverse of the modulus is computed in Montgomery modular reduction. The special moduli are of type n² = 1 bmod β^r in Montgomery multiplication, where r ranges from 1 to s = ≤ftlceillog _βnright rceil . In particular, every Mersenne number (power of 2 less one), as well as the Generalized Mersenne prime moduli used to define the NIST Prime Curves P-256 and P-384 in FIPS 186-3 have this special form. This shows that, in addition to general interest to modular multiplication and finite field arithmetic, this trick can be applied to currently existing crypto systems. We also prove that there is no way to remove the precomputation step in the Barret reduction by way of a contradiction of the derived moduli requirement.