A low-complexity LUT-based squaring algorithm
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 GuajardoPaar 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 GuajardoPaar algorithm and the YangHeihLaih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.
squaring information security fast algorithm design modular multiplication public-key cryptosystem