Applications of the Montgomery exponent
Shay Gueron, Or Zuk · 2005
We define here the Montgomery exponent of order s, modulo the odd integer N, by MEXP = MEXP(A,X,N,s) = A/sup X/2/sup -s(X-1)/ (mod N), and illustrate some properties and usage of this operator. We show how A/sup X/ (mod N) can be obtained from MEXP(A, X, N, s) by one Montgomery multiplication. This suggests a new modular exponentiation algorithm that uses one Montgomery multiplication less than the number required with the standard method. This improves the performance, although the improvement is significant only when the exponent X is short (e.g., modular squaring or RSA verification). However, and even more important, this achieves code size reduction, which is appreciated when the exponentiation algorithm is written in a low-level language and stored in (expensive) ROM. We also illustrate the potential advantage in performance and code size when known cryptographic applications are modified in a way that MEXP replaces the standard modular exponentiation.