A carry-free architecture for Montgomery inversion

Savaş, Erkay (2005) A carry-free architecture for Montgomery inversion. IEEE Transactions on Computers, 54 (12). pp. 1508-1519. ISSN 0018-9340

This is the latest version of this item.

[thumbnail of 3011800001174.pdf] PDF
Restricted to Registered users only

Download (904kB) | Request a copy


A new carry-free Montgomery inversion algorithm which is suitable for hardware implementation is presented. The algorithm utilizes a new redundant sign digit (RSD) representation and arithmetic to avoid carry propagation in addition and subtraction, which are the atomic operations in the Montgomery inversion algorithm. The proposed algorithm is described in such a way that its hardware realization is straightforward. The algorithm enables very fast computation of multiplicative inversion in GF(p), which is the most time-consuming operation in elliptic and hyperelliptic curve cryptography. Complexity analysis and a gate level implementation of the algorithm reveal that the proposed algorithm provides a speedup of at least 1.95 over the original Montgomery inversion algorithm.
Item Type: Article
Uncontrolled Keywords: Montgomery inversion; redundant signed representation; elliptic curve cryptography
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 30 Dec 2005 02:00
Last Modified: 25 May 2011 14:11
URI: https://research.sabanciuniv.edu/id/eprint/600

Available Versions of this Item

Actions (login required)

View Item
View Item