Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Overlap-free Karatsuba–Ofman polynomial multiplication algorithms

Overlap-free Karatsuba–Ofman polynomial multiplication algorithms

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

The authors describe how a simple way to split input operands allows for fast VLSI implementations of subquadratic GF(2)[x] Karatsuba–Ofman multipliers. The theoretical XOR gate delay of the resulting multipliers is reduced significantly. For example, it is reduced by about 33 and 25% for n = 2t and n = 3t (t > 1), respectively. To the best of our knowledge, this parameter has never been improved since the original Karatsuba–Ofman algorithm was first used to design GF(2n) multipliers in 1990.

Inspec keywords: computational complexity; polynomials

Other keywords: fast VLSI implementations; XOR gate delay; overlap-free Karatsuba-Ofman polynomial multiplication algorithms; subquadratic GF(2)[x] Karatsuba-Ofman multipliers

Subjects: Computational complexity; Interpolation and function approximation (numerical analysis)

References

    1. 1)
      • C. Paar . A new architecture for a parallel finite field multiplier with low complexity based on composite fields. IEEE Trans. Comput. , 7 , 856 - 861
    2. 2)
      • Gathen, J.V.Z., Shokrollahi, J.: `Efficient FPGA-based Karatsuba multipliers for polynomials over ', Proc. 12th Workshop on Selected Areas in Cryptography (SAC 2005), 2006, p. 359–369, (LNCS, 3897).
    3. 3)
      • P.L. Montgomery . Five, six, and seven-term Karatsuba-like formulae. IEEE Trans. Comput. , 3 , 362 - 369
    4. 4)
      • Leone, M.: `A new low complexity parallel multiplier for a class of finite fields', Proc. Cryptographic Hardware and Embedded Systems (CHES 2001), 2001, p. 160–170, (LNCS, 2162).
    5. 5)
      • M. Elia , M. Leone , C. Visentin . Low complexity bit-parallel multipliers for GF(2m) with generator polynomial xm+xk+1. IEE Electron. Lett. , 7 , 551 - 552
    6. 6)
      • Bajard, J.C., Imbert, L., Jullien, G.A.: `Parallel montgomery multiplication in ', Proc. 17th IEEE Symp. on Computer Arithmetic (ARITH 2005), June 2005, p. 164–171.
    7. 7)
      • H. Fan , Y. Dai . Fast bit parallel GF (2n) multiplier for all trinomials. IEEE Trans. Comput. , 4 , 485 - 490
    8. 8)
      • H. Fan , M.A. Hasan . A new approach to subquadratic space complexity parallel multipliers for extended binary fields. IEEE Trans. Comput. , 2 , 224 - 233
    9. 9)
      • Moenck, R.T.: `Practical fast polynomial multiplication', Proc. 1976 ACM. Symp. on Symbolic and Algebraic Computation, 1976, p. 136–148.
    10. 10)
      • Ernst, M., Jung, M., Madlener, F., Huss, S., Blumel, R.: `A reconfigurable system on chip implementation for elliptic curve cryptography over ', Proc. Cryptographic Hardware and Embedded Systems (CHES 2002), 2003, p. 381–399, (LNCS, 2523).
    11. 11)
      • C. Paar , V.B. Cleischmann , P. Roelse . Efficient multiplier schemes for Galois fields GF(24n). IEEE Trans. Comput. , 2 , 162 - 170
    12. 12)
      • A. Weimerskirch , C. Paar . (2003) Generalizations of the Karatsuba algorithm for efficient implementations.
    13. 13)
      • Seroussi, G.: `Table of low-weight binary irreducible polynomials', Technical Report HPL-98-135, 1998, [Online]. Available at: http://www.hpl.hp.com/techreports/98/HPL-98-135.html.
    14. 14)
      • Chang, N.S., Kim, C.H., Park, Y.H., Lim, J.: `A non-redundant and efficient architecture for Karatsuba–Ofman algorithm', Proc. Eighth Int. Conf. on Information Security (ISC 2005), 2005, p. 288–299, (LNCS, 3650).
    15. 15)
      • Winograd, S.: `Arithmetic complexity of computations', SIAM, 1980.
    16. 16)
      • J.V.Z. Gathen , J. Gerhard . (2003) Modern computer algebra.
    17. 17)
      • K.Y. Chang , D. Hong , H.S. Cho . Low complexity bit-parallel multiplier for GF(2m) defined by all-one polynomials using redundant representation. IEEE Trans. Comput. , 12 , 1628 - 1630
    18. 18)
      • Grabbe, C., Bednara, M., Shokrollahi, J., Teich, J., Gathen, J.V.Z.: `FPGA designs of parallel high performance ', Proc. Int. Symp. on Circuits and Systems (ISCAS 2003), 2003, II, p. 268–271.
    19. 19)
      • G. Hanrot , P. Zimmermann . A long note on mulders' short product. J. Symbol. Comput. , 391 - 401
    20. 20)
      • M.A. Hasan , V.K. Bhargava . Architecture for low complexity rate-adaptive Reed–solomon encoder. IEEE Trans. Comput. , 7 , 938 - 942
    21. 21)
      • Jung, M., Madlener, F., Ernst, M., Huss, S.: `A reconfigurable coprocessor for finite field multiplication in ', Proc. IEEE Workshop Heterogeneous reconfigurable Systems on Chip, 2002.
    22. 22)
      • A. Karatsuba , Y. Ofman . Multiplication of multidigit numbers on automata. Sov. Phys.-Dokl. (English translation) , 7 , 595 - 596
    23. 23)
      • Peter, P., Langendorfer, P.: `An efficient polynomial multiplier in ', Proc. Conf. on Design, Automation and Test in Europe 2007, 2007, p. 1253–1258.
    24. 24)
      • Dyka, Z., Langendoerfer, P.: `Area efficient hardware implementation of elliptic curve cryptography by iteratively applying Karatsuba's method', Proc. Conf. on Design, Automation and Test in Europe 2005, 2005, p. 70–75.
    25. 25)
      • B. Sunar . A generalized method for constructing subquadratic complexity GF(2k) multipliers. IEEE Trans. Comput. , 9 , 1097 - 1105
    26. 26)
      • Afanasyev, V.B.: `Complexity of VLSI implementation of finite field arithmetic', Proc. II. Intern. Workshop on Algebraic and Combinatorial Coding Theory, 1990, p. 6–7.
    27. 27)
      • Cheng, L.S., Miri, A., Yeap, T.H.: `Improved FPGA implementations of parallel Karatsuba multiplication over ', Proc. 23rd Biennial Symp. on Communications, 2006.
    28. 28)
      • Paar, C.: `Efficient VLSI architectures for bit-parallel computation in Galois fields', 1994, PhD, University of Essen, Germany.
    29. 29)
      • H. Fan , M.A. Hasan . Comments on “five, six, and seven-term Karatsuba-like formulae” . IEEE Trans. Comput. , 5 , 716 - 717
    30. 30)
      • M.A. Hasan , V.K. Bhargava . Division and bit-serial multiplication over GF(qm). IEE Proc.-E , 3 , 230 - 236
    31. 31)
      • Gathen, J.V.Z., Shokrollahi, J.: `Fast arithmetic for polynomials over ', Proc. IEEE Workshop on Information Theory, 2006, p. 107–111.
    32. 32)
      • Rodríguez-Henríquez, F., Koç, C.K.: `On fully parallel Karatsuba multipliers for ', Proc. Int. Conf. Computer Science and Technology (CST 2003), 2003, p. 405–410.
    33. 33)
      • Erdem, S.S., Koç, C.K.: `A less recursive variant of Karatsuba–Ofman algorithm for multiplying operands of size a power of two', Proc. 16th IEEE Symp. on Computer Arithmetic (Arith-16 2003), 2003, p. 28–35.
    34. 34)
      • S.S. Erdem , T. Yanik , C.K. Koç . Polynomial basis multiplication over GF(2m). Acta Appl. Math.: Int. Survey J. Appl. Math. Math. Appl. , 33 - 55
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2009.0039
Loading

Related content

content/journals/10.1049/iet-ifs.2009.0039
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address