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 On2612310log261231122682893 and SchnhageStrassen multiplication algorithm with the run-time bit complexity defined as On log268289n log268289log2682892612310n2612311. 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.