Subquadratic Space-Complexity Parallel Systolic Multiplier Based on Karatsuba Algorithm and Block Recombination

摘要

Recently, high-performance elliptic curve cryptography has gained great attention for resource-constrained applications. In this paper, we use (a, b)-way Karatsuba algorithm to derive a new way of k-way Karatsuba algorithm and block recombination (KABR) approach. We have derived a new parallel systolic multiplication with subquadratic space complexity based on k-way KABR approach. By theoretical analysis, it is shown that the proposed structure using k-way BRKA has significantly less computation delay, less area-delay product, and less area. Moreover, the proposed structure can provide the desired tradeoff between space and time complexity.