Speeding Up RSA and Elliptic Curve Systems by Choosing Suitable Moduli
Huapeng Wu, M.A. Hasan, Ian F. Blake · Birkhäuser Basel eBooks · 2004
In this paper we propose a method to speed up the modular operation by choosing suitable moduli. When the modulus N can be represented as a sum of a few positive or negative powers of 2, we show that a modular operation ( X mod N ),where X is not greater than the square of the modulus N ,can be computed with a few addition/subtraction operations with the operands of about the same size as the modulus. No evidence has been shown that use of such moduli in RSA and elliptic curve cryptosystems can compromise the security of the systems. Mathematics Subject Classification (2000). Primary 68W99; Secondary 94A60.