Residue systems efficiency for modular products summation: application to elliptic curves cryptography

J. C. Bajard; S. Duquesne; M. Ercegovac; N. Meloni

doi:10.1117/12.679541

25 August 2006 Residue systems efficiency for modular products summation: application to elliptic curves cryptography

J. C. Bajard, S. Duquesne, M. Ercegovac, N. Meloni

Proceedings Volume 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI; 631304 (2006) https://doi.org/10.1117/12.679541
Event: SPIE Optics + Photonics, 2006, San Diego, California, United States

Abstract

Residue systems of representation, like Residue Number Systems (RNS) for primary field(GF(p)) or Trinomial Residue Arithmetic for binary field (GF(2^k)), are characterized by efficient multiplication and costly modular reduction. On the other hand, conventional representations allow in some cases very efficient reductions but require costly multiplications. The main purpose of this paper is to analyze the complexity of those two different approaches in the summations of products. As a matter of fact, the complexities of the reduction in residue systems and of the multiplication in classical representations are similar. One of the main features of this reduction is that it doesn't depend on the field. Moreover, the cost of multiplication in residue systems is equivalent to the cost of reduction in classical representations for special well-chosen fields. Taking those properties into account, we remark that an expression like A * B + C * D, which requires two products, one addition and one reduction, evaluates faster in a residue system than in a classical one. So we propose to study types of expressions to offer a guide for choosing a most appropriate representation. One of the best domain of application is the Elliptic Curves Cryptography where addition and doubling points formulas are composed of products summation. The different kinds of coordinates like affine, projective, and Jacobean, offer a good choice of expressions for our study.

Citation Download Citation

J. C. Bajard, S. Duquesne, M. Ercegovac, and N. Meloni "Residue systems efficiency for modular products summation: application to elliptic curves cryptography", Proc. SPIE 6313, Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, 631304 (25 August 2006); https://doi.org/10.1117/12.679541

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available