
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Squaring of Large Integers
WuChuan YANG PengYueh HSEIH ChiSung LAIH
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E87A
No.5
pp.11891192 Publication Date: 2004/05/01 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: public key cryptography, algorithm, big integer, squaring, multiplication,
Full Text: PDF(685.8KB)>>
Summary:
The efficient squaring algorithm is an important role in large integer arithmetic. All multiplication algorithms can be used for squaring large integers, but their performance can be greatly improved by using the standard squaring algorithm. The standard squaring algorithm is quite wellknown, but unfortunately there is an improper carry handling bug in it. Recently, Guajardo and Paar proposed a modified squaring algorithm to fix the bug in the standard squaring algorithm. In this paper, we first point out that there is still an errorindexing bug in the GuajardoPaar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the GuajardoPaar squaring algorithm but also improves the performance in squaring computation. Our analyses and our simulations indicate that the proposed squaring algorithm is about 2.5 times faster in comparison with the standard multiplication algorithm in Pentium Series CPU. The performance of 1024bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.

