**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30737

##### Efficient Large Numbers Karatsuba-Ofman Multiplier Designs for Embedded Systems

**Authors:**
M.Machhout,
M.Zeghid,
W.El hadj youssef,
B.Bouallegue,
A.Baganne,
R.Tourki

**Abstract:**

**Keywords:**
mathematical model,
finite field,
multiplication,
Karatsuba-Ofman,
long numbers,
recursivity

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1070785

**References:**

[1] D.V.Bailey, C.Paar, "Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography," Journal of Cryptology, vol. 14, 2001, pp.153-176.

[2] N.S.Chang, C.H.Kim, Y.H .Park, J.Lim,"A non-redundant and efficient design for Karatsuba-Ofman algorithm," In ISC, Springer-Verlag Berlin Heidelberg, 2005,pp. 288-299.

[3] L.S.Cheng, A.Miri, T.H.Yeap, "Improved FPGA implementations of parallel Karatsuba multiplication over GF (2n)," In Proc. 23rd Biennial Symposium on Communications conf, 2006.

[4] L.Dong-Ho, and O.Jong-Soo, "Multi-Segment GF (2m) Multiplication and its Application to Elliptic Curve Cryptography)," in Proc.GLSVLSI-07 conf. Stresa-Lago Maggiore, Italy, pp. 546-551.

[5] Z.Dyka, P. Langendoerfer,, "Area efficient hardware implementation of elliptic curve cryptography by iteratively applying karatsuba-s method," in Proc. of the Design, Automation and Test in Europe conf, pp.70-75.

[6] W.El hadj youssef, M.Zghid, M.Machhout, B.Bouallegue, R.Tourki, "Design and Performance testing of Arithmetic Operators Library for Cryptographic Applications," International Journal of Computer Sciences and Engineering Systems (IJCSES), Vol.1, No.3, 2008,pp. 201- 212.

[7] M.Ernst, M.Jung, F.Madlener, S. Huss, R.Blumel, "A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n) ,"In CHES, LNCS 2523, 2002, pp. 381-399.

[8] F. U.S. Department of Commerce (2000) ÔÇÿDigital Signature Standard (DSS)-, NIST /FIPS PUB 186-2, January.

[9] F.Rodriguez-Henriquez, N.A.Saqib, A.Diaz-Pérez, "A fast parallel implementation of elliptic curve point multiplication over GF (2m)", Microprocessors and Microsystems, Vol.28, pp.329-339.

[10] Z.Guitouni, W.El hadj youssef, M.Machhout, R.Tourki, "Implementation of Elliptic Curve Point Multiplication in Projective Systems over GF(2m)", In Proc.Fourth International Multi-Conference on Systems, Signals & Devices (SSD-07), March.

[11] J.Großschadl, R.M.Avanzi, E.Sava, S. Tillich,"Energy-Efficient Software Implementation of Long Integer Modular Arithmetic," In CHES 2005, LNCS 3659, pp. 75-90.

[12] P.Kocher, L.Ruby, G.McGraw, A.Raghunathan, R.Srivaths, "Security as a New Dimension in Embedded System Design," In Proc. DAC 2004, June, San Diego, California, USA.

[13] L. A. B.Kowada, R.Portugal, C.M.H.Figueiredo,"Reversible Karatsuba-s Algorithm," Journal of Universal Computer Science, Vol. 12, no. 5, pp.499-511.

[14] N.Nedjah, L.M.Mourelle, "Fast Less Recursive Hardware for Large Number Multiplication Using Karatsuba-Ofman-s Algorithm," In Proc. ISCIS 2003, LNCS 2869, pp. 43-50.

[15] N.Nedjah, L.M.Mourelle,"A Review of Modular Multiplication Methods and Respective Hardware Implementations," Informatica, Vol. 30, pp.111-129.

[16] P.L.Montgomery, "Five, Six, and seven-Term Karatsuba-Like Formulae," IEEE Transactions on Computers, Vol. 54, No. 3, pp. 362- 69.

[17] W.Qingxian, "The application of elliptic curves cryptography in embedded systems," In Proc. Second International Embedded Software and Systems Conf., pp.16-18.

[18] S.Peter, P.Langendorferv, "An Efficient Polynomial Multiplier in GF (2m) and its Application to ECC Designs," In Proc. DATE0 Conf EDAA.

[19] J.Von zur Gathen, J.Shokrollahi, "Efficient FPGA-based Karatsuba multipliers for polynomials over F2," In Proc.SAC 2005 conf, LNCS 3897, pp. 359-369.

[20] J.Von zur Gathen, J.Shokrollahi, "Fast arithmetic for polynomials over F2 in hardware," In Proc. IEEE Information Theory Workshop, Punta del Este, Uruguay.

[21] LC.Washington.,"Elliptic Curves: Number Theory and Cryptography,"In Chapman & Hall New York CRC Press.

[22] Weimerskirch, A. and Paar, C. (2003) ÔÇÿGeneralizations of the Karatsuba Algorithm for Efficient Implementations-, Ruhr-Universitat-Bochum, Germany, Tech. Rep.

[23] T.Wollinger, G.Guajardo, C.Paar ,"Cryptography in Embedded Systems: An Overview," In Proc. of the Embedded World 2003 Exhibition and Conference, Design & Elektronik, Nuernberg, Germany, February, pp. 735-744.