Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
Authors:
- 30 November 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 56 (1) , 44-57
Abstract
In 1999, Solinas introduced families of moduli called the generalized Mersenne numbers (GMNs), which are expressed in low-weight polynomial form, p=f(t), where t is limited to a power of 2. GMNs are very useful in elliptic curve cryptosystems over prime fields since modular reduction by a GMN requires only integer additions and subtractions. However, since there are not many GMNs and each GMN requires a dedicated implementation, GMNs are hardly useful for other cryptosystems. Here, we modify GMN by removing restriction on the choice of t and restricting the coefficients of f(t) to 0 and plusmn1. We call such families of moduli low-weight polynomial form integers (LWPFIs). We show an efficient modular multiplication method using LWPFI moduli. LWPFIs allow general implementation and there exist many LWPFI moduli. One may consider LWPFIs as a trade-off between general integers and GMNsKeywords
This publication has 20 references indexed in Scilit:
- Arithmetic Operations in the Polynomial Modular Number System2005
- Five, six, and seven-term Karatsuba-like formulaeIEEE Transactions on Computers, 2005
- Precise Bounds for Montgomery Modular Multiplication and Some Potentially Insecure RSA Moduli2002
- The Special Function Field SieveSIAM Journal on Discrete Mathematics, 2002
- Analyzing and comparing Montgomery multiplication algorithmsIEEE Micro, 1996
- New Modular Multiplication Algorithms for Fast Modular Exponentiation1996
- More on squaring and multiplying large integersIEEE Transactions on Computers, 1994
- Elliptic curve cryptosystemsMathematics of Computation, 1987
- Arithmetic Complexity of Computations1980
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978