Review Of Fast Multiplication Algorithms For Embedded Systems Design

摘要

This paper presents a review with numerical example and complexity analysis of the fast multiplication algorithms to help embedded system designers to improve the hardware performance for many applications such as cryptosystems design. The paper presented two practical multiplication algorithms: Karatsuba multiplication algorithm with time complexity O(n^〖log〗_2'3 ) and Sch'nhage'Strassen multiplication algorithm with the run-time bit complexity defined as O(n log'(n) log'(log'〖(n〗)). In addition, interleaved multiplication algorithm can be used efficiently to compute the modular multiplication with logarithmic time complexity which enhances the linear time complexity of Montgomery modular multiplication.