A low-complexity LUT-based squaring algorithm

AbstractThe 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