Hardware simulation model suitable for recursive computations: Karatsuba-Ofman's multiplication algorithm
Nadia Nedjah, Luiza de Macedo Mourelle · 2004
Summary form only given, as follows. Multiplication of long integers is a cornerstone primitive in most public-key cryptosystems. Multiplication can be best performed using Karatsuba-Ofman's divide-and-conquer approach. However, Karatsuba-Ofman's algorithm is recursive. It is a fairly hard task to design a hardware that implements it using a repetitive style. We propose an elegant recursive hardware model for Karatsuba-Ofman's multiplication algorithm. The generated hardware is efficient in terms of response time and compact in terms of hardware area. The model is expressed in the most popular hardware description language VHDL and functional and timing simulations are used to validate the model and evaluate its requirements in terms of hardware area and propagation delay of the output signals.