Subquadratic Space-Complexity Parallel Systolic Multiplier Based on Karatsuba Algorithm and Block Recombination

1. Nangate standard cell library. http://www.si2.org/openeda.si2.org/projects/nangatelib/

2. Public key cryptography for the financial services industry: The elliptic curve digital signature algorithm (ecdsa) (1999)

   Google Scholar 

3. Digital signature standard (dss). Federal Information Processing Standards, Publication 186–2 (2000)

   Google Scholar 

4. Cook, S.: On the minimum computation time of functions, master’s thesis, Harvard University (1966)

   Google Scholar 

5. El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)

   Google Scholar 

6. Hasan, M.A., Meloni, N., Namin, A.H., Nègre, C.: Block recombination approach for subquadratic space complexity binary field multiplication based on toeplitz matrix-vector product. IEEE Trans. Computers 61, 151–163 (2012)

   Article  Google Scholar 

7. Jain, S.K., Song, L., Parhi, K.K.: Efficient semisystolic architectures for finite-field arithmetic. IEEE Trans. VLSI Syst. 6, 101–113 (1998)

   Article  Google Scholar 

8. Karatsuba, A.A., Ofman, Y.: Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7, 595–596 (1963)

   Google Scholar 

9. Lee, C.-Y., Horng, J.-S., Jou, I.-C., Lu, E.-H.: Low-Complexity Bit-Parallel Systolic Montgomery Multipliers for Special Classes of GF(2\(^{\text{m}}\)). IEEE Trans. Computers 54, 1061–1070 (2005)

   Article  Google Scholar 

10. Lee, C.-Y., Meher, P.K.: Efficient bit-parallel multipliers over finite fields GF(2\({}^{\text{m}}\)). Computers & Electrical Engineering 36, 955–968 (2010)

    Article  MATH  Google Scholar 

11. Lee, C.-Y., Meher, P.K.: Efficient subquadratic space complexity architectures for parallel MPB single- and double-multiplications for all trinomials using toeplitz matrix-vector product decomposition. IEEE Trans. on Circuits and Systems, 62-I (2015)

    Google Scholar 

12. Lee, C.-Y., Meher, P.K.: Subquadratic space-complexity digit-serial multipliers over \(GF(2^m)\) using generalized (a, b)-way karatsuba algorithm. IEEE Trans. on Circuits and Systems 62-I (2015)

    Google Scholar 

13. C.-Y. Lee, P. K. Meher, and C.-P. Chang, Efficient m-ary exponentiation over \(GF(2^m)\) using subquadratic ka-based three-operand montgomery multiplier. IEEE Trans. on Circuits and Systems 61-I, 3125–3134 (2014)

    Google Scholar 

14. Lee, C.-Y., Meher, P. K., Lee, W.-Y.: Subquadratic space complexity digit-serial multiplier over binary extension fields using toom-cook algorithm. In: The International Symposium on Integrated Circuits (ISIC) (2014)

    Google Scholar 

15. Lee, C.-Y., Yang, C.-S., Meher, B.K., Meher, P.K., Pan, J.-S.: Low-complexity digit-serial and scalable SPB/GPB multipliers over large binary extension fields using (b, 2)-way karatsuba decomposition. IEEE Trans. on Circuits and Systems 61-I, 3115–3124 (2014)

    Google Scholar 

16. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications, 2nd edn. Cambridge University Press (1997)

    Google Scholar 

17. Montgomery, P.L.: Five, six, and seven-term karatsuba-like formulae. IEEE Trans. Computers 54, 362–369 (2005)

    Article  MATH  Google Scholar 

18. Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Soviet Mathematics Doklady 3, 714–716 (1963)

    Google Scholar 

19. van der Hoeven, J., Lecerf, G.: On the complexity of multivariate blockwise polynomial multiplication. In: ISSAC 2012, pp. 211–218 (2012)

    Google Scholar 

20. Xie, J., Meher, P.K., Mao, Z.: High-throughput finite field multipliers using redundant basis for FPGA and ASIC implementations. IEEE Trans. on Circuits and Systems 62-I, 110–119 (2015)

    Google Scholar 

21. Xie, X.-N., Chen, G., Li, Y.: Novel bit-parallel multiplier for \(GF(2^m)\) defined by all-one polynomial using generalized karatsuba algorithm. Inf. Process. Lett. 114, 140–146 (2014)

    Article  MATH  Google Scholar 

Download references