Montgomery Reduction Algorithm for Modular Multiplication Using Low-Weight Polynomial Form Integers
Authors:
- 1 June 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636889,p. 230-239
Abstract
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].Keywords
This publication has 8 references indexed in Scilit:
- Low-Weight Polynomial Form Integers for Efficient Modular MultiplicationIEEE Transactions on Computers, 2006
- Arithmetic Operations in the Polynomial Modular Number System2005
- Five, six, and seven-term Karatsuba-like formulaeIEEE Transactions on Computers, 2005
- Finite field multiplier using redundant representationIEEE Transactions on Computers, 2002
- Closest point search in latticesIEEE Transactions on Information Theory, 2002
- Montgomery exponentiation needs no final subtractionsElectronics Letters, 1999
- A new representation of elements of finite fields GF(2/sup m/) yielding small complexity arithmetic circuitsIEEE Transactions on Computers, 1998
- Modular Multiplication Without Trial DivisionMathematics of Computation, 1985