Rapid prototyping of recursive hardware: Karatsuba-Ofman's multiplication algorithm

• Autorzy: Nedjah N. , Macedo Mourelle L. de
• Języki publikacji: EN

Abstrakty

EN

It is a fairly hard task TO design hardware that implements recursive computations using a repetitive style, which is supported in mast hardware description languages suck as VHDL and Verilog. In this paper we show how one can very elegant and rapidly yield hardware models that implement recursive computations. The hardware model is expressed in the most popular hardware description language VHDL As a case study, we implement the Karatsuba-Ofman's divide-and-conquer multiplication algorithm. The generated hardware is efficient in terms of response time and compact in terms of hardware area.

Słowa kluczowe

EN

VHDL; Karatsuba-Ofman's algorithm; recursion

PL

VHDL; algorytm Karatsuby-Ofmana; rekurencja

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2004
• Tom: Vol. 12, nr 1
• Strony: 43--59
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Nedjah N.

• Departament of Systems Engineering and Computation, Faculty of Engineering, State University of Rio de Janeiro, Rio de Janeiro, Brazil

autor

Macedo Mourelle L. de

• Departament of Systems Engineering and Computation, Faculty of Engineering, State University of Rio de Janeiro, Rio de Janeiro, Brazil

Bibliografia

• [1] Rivest R.L., Shamir A. and Adleman L.: A method for obtaining signatures and public-key cryptosystems, Communication of ACM, vol. 21, pp. 120-126, 1978.
• [2] Diffie W. and Hellman M.E.: New directions in cryptography, IEEE Transactions on Information Theory, vol. 22, pp. 644-654, 1976.
• [3] ElGamal T.: A public-key cryptosystems and signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469-472, 1985.
• [4] Koç Ç. K.: High speed RSA implementation, Technical report, RSA Laboratories, RSA Data Security Inc. CA, version 2, 1994.
• [5] Lim C.H., Hwang H.S. and Lee P.J.: Fast modular reduction with precomputation, In Proceedings of Korea-Japan Joint Workshop on Information Security and Cryptology, Lecture Notes in Computer Science, vol. 488, pp. 323-334, 1991.
• [6] Knuth D.E.: The art of computer programming: seminumerical algorithms, vol 2, 2nd Edition, Addison-Wesley, Reading, Mass., 1981.
• [7] Zuras D.: On squaring and multiplying large integers, In Proceedings of International Symposium on Computer Arithmetic, IEEE Computer Society Press, pp. 260-271, 1993.
• [8] Dhem J.F.: Design of an efficient public-key cryptographic library for RISC-based smart cards, Ph.D. Thesis, Faculty of Applied Science, Catholic University of Louvain, May 1998.
• [9] Jung M., Madlener F., Ernst M. and Huss S.A.: A reconfigurable coprocessor for finite field multiplication in GF(2n), Proc. of IEEE Workshop on Heterogeneous Reconfigurable systems on Chip, Hamburg, Germany, 2002.
• [10] Paar C.: A new architecture for a parallel finite field multiplier with low complexity based on composite fields, IEEE Transactions on Computers, vol. 45, no. 7, pp. 856-861, 1996.
• [11] Navabi Z.: VHDL - analysis and modelling of digital systems, 2nd Edition, MacGrawHill, 1998.
• [12] Ashenden P.J.: Recursive and Repetitive Hardware Models in VHDL, Joint Technical Report, TR 160/12/93/ECE, University of Cincinnati, and TR 93-19, University of Adelaide, 1993.
• [13] Xilinx, Inc. Foundation Series Software, http://www.xilinx.com.
• [14] Kim J.H., Ryu J. H.: A high speed and low power VLSI multiplier using a redundant binary Booth encoding, Proc. of 6th Korean Semiconductor Conference, PA-30. 1999