Montgomery Reduction Algorithm for Modular Multiplication Using Low-Weight Polynomial Form Integers
Jaewook Chung, M.A. Hasan · Proceedings/Proceedings - Symposium on Computer Arithmetic · 2007
In this paper, we extend a recent piece of work on low-weight polynomial form integers (LWPFIs). We present a new coefficient reduction algorithm based on the Montgomery reduction algorithm and provide its detailed analysis results. We give a condition for eliminating the final subtractions at the end of our Montgomery reduction algorithm adapted to perform the coefficient reduction. Our experimental results show that a new coefficient reduction algorithm is indeed more efficient than the one presented in [1].