A low-complexity LUT-based squaring algorithm

✍ Scribed by Te-Jen Chang; Chia-Long Wu; Der-Chyuan Lou; Ching-Yin Chen

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 648 KB
• Volume: 57
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2008.11.018

✦ Synopsis

The computation of large modular multi-exponentiation is a time-consuming arithmetic operation used in cryptography. The standard squaring algorithm is well-known and the Guajardo-Paar algorithm fixes the improper carry handling bug produced by the standard squaring algorithm, but produces error-indexing bug. In this paper, a novel squaring algorithm is proposed, which stores base products in the Look-Up Table before the squaring computation and base size comparison method. The proposed algorithm can not only evaluate squaring efficiently but also avoid bugs produced in other proposed algorithms (the Guajardo-Paar algorithm and the Yang-Heih-Laih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.