Enhanced Montgomery Multiplication

摘要

We define the Non Reduced Montgomery Multiplication of order s, of A and B, modulo N (odd integer) by NRMM~s(A,B,N) = (AB + N (―ABN~(-1) (mod 2~s))) 2~(2-s). Given an upper bound on A and B, with respect to N, we show how to choose the variable s in a way that guarantees that NRMM~s(A,B,N) < 2N. A few applications are demonstrated, showing the advantage of using NRMM~s with an appropriately chosen s, over the classical Montgomery Multiplication.