Efficient Squaring of Large Integers

Wu-Chuan YANG; Peng-Yueh HSEIH; Chi-Sung LAIH

Efficient Squaring of Large Integers

Wu-Chuan YANG, Peng-Yueh HSEIH, Chi-Sung LAIH

Full Text Views

0

Share
Cite this

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 well-known, 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 error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar 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 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1189-1192

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Wu-Chuan YANG, Peng-Yueh HSEIH, Chi-Sung LAIH, "Efficient Squaring of Large Integers" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1189-1192, May 2004, doi: .
Abstract: 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 well-known, 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 error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar 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 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1189/_p

Copy

@ARTICLE{e87-a_5_1189,
author={Wu-Chuan YANG, Peng-Yueh HSEIH, Chi-Sung LAIH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Squaring of Large Integers},
year={2004},
volume={E87-A},
number={5},
pages={1189-1192},
abstract={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 well-known, 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 error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar 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 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Efficient Squaring of Large Integers
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1189
EP - 1192
AU - Wu-Chuan YANG
AU - Peng-Yueh HSEIH
AU - Chi-Sung LAIH
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - 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 well-known, 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 error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar 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 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.
ER -