Speeding up the Multiplication Algorithm for Large Integers

  • H. M. Bahig Computer Science and Information Department, College of Computer Science and Engineering, University of Hail, Saudi Arabia
  • A. Alghadhban Electrical Engineering Department, College of Engineering, University of Hail, Saudi Arabia
  • M. A. Mahdi Computer Science and Information Department, College of Computer Science and Engineering, University of Hail, Saudi Arabia
  • K. A. Alutaibi Computer Engineering Department, College of Computer Science and Engineering, University of Hail, Saudi Arabia
  • H. M. Bahig Mathematics Department, Faculty of Science, Ain Shams University, Egypt
Volume: 10 | Issue: 6 | Pages: 6533-6541 | December 2020 | https://doi.org/10.48084/etasr.3932

Abstract

Multiplication is one of the basic operations that influence the performance of many computer applications such as cryptography. The main challenge of the multiplication operation is the cost of the operation as compared to other basic operations such as addition and subtraction, especially when the size of the numbers is large. In this work, we investigate the use of the window strategy for multiplying a sequence of large integers to design an efficient sequential algorithm in order to reduce the number of bit-multiplication operations involved in multiplying a sequence of large integers. In our implementation, several parameters are considered and measured for their effect on the proposed algorithm and the best-known sequential algorithm in the literature. These parameters are the size of the sequence of integers, the size of the integers, the size of the window, and the distribution of the data. The experimental results prove the effectiveness of the proposed algorithm are compared to the ones of the best-known sequential algorithm, and the proposed algorithm is able to achieve a reduction in computing time greater than 50% in most cases.

Keywords: multiplication, big data, cryptography, algorithm performance, computer arithmetic

Downloads

Download data is not yet available.

References

R. P. Brent and P. Zimmermann, Modern Computer Arithmetic. Cambridge ; New York: Cambridge University Press, 2010. DOI: https://doi.org/10.1017/CBO9780511921698

E. S. I. Harba, "Secure Data Encryption Through a Combination of AES, RSA and HMAC," Engineering, Technology & Applied Science Research, vol. 7, no. 4, pp. 1781-1785, Aug. 2017. DOI: https://doi.org/10.48084/etasr.1272

M. B. Apsara, P. Dayananda, and C. N. Sowmyarani, "A Review on Secure Group Key Management Schemes for Data Gathering in Wireless Sensor Networks," Engineering, Technology & Applied Science Research, vol. 10, no. 1, pp. 5108-5112, Feb. 2020. DOI: https://doi.org/10.48084/etasr.3213

R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120-126, Feb. 1978. DOI: https://doi.org/10.1145/359340.359342

K. A. Fathy, H. M. Bahig, and A. A. Ragab, "A Fast Parallel Modular Exponentiation Algorithm," Arabian Journal for Science and Engineering, vol. 43, no. 2, pp. 903-911, Feb. 2018. DOI: https://doi.org/10.1007/s13369-017-2797-3

H. M. Bahig and K. A. Fathy, "An efficient parallel strategy for high-cost prefix operation," The Journal of Supercomputing, Nov. 2020. DOI: https://doi.org/10.1007/s11227-020-03473-x

G. Bilardi and L. De Stefani, "The I/O complexity of toom-cook integer multiplication," in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, USA, Jan. 2019, pp. 2034-2052. DOI: https://doi.org/10.1137/1.9781611975482.123

R. Brumnik, V. Kovtun, A. Okhrimenko, and S. Kavun, "Techniques for Performance Improvement of Integer Multiplication in Cryptographic Applications," Mathematical Problems in Engineering, vol. 2014, Feb. 2014, Art. no. 863617. DOI: https://doi.org/10.1155/2014/863617

S. A. Cook and S. O. Aanderaa, "On the Minimum Computation Time of Functions on JSTOR," Transactions of the American Mathematical Society, vol. 142, pp. 291-314, Aug. 1969. DOI: https://doi.org/10.1090/S0002-9947-1969-0249212-8

A. De, P. P. Kurur, C. Saha, and R. Saptharishi, "Fast Integer Multiplication Using Modular Arithmetic," SIAM Journal on Computing, vol. 42, no. 2, pp. 685-699, Jan. 2013. DOI: https://doi.org/10.1137/100811167

M. J. Fischer and L. J. Stockmeyer, "Fast on-line integer multiplication," in Proceedings of the fifth annual ACM symposium on Theory of computing, New York, NY, USA, Apr. 1973, pp. 67-72. DOI: https://doi.org/10.1145/800125.804037

M. Fürer, "Faster integer multiplication," in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, New York, NY, USA, Jun. 2007, pp. 57-66. DOI: https://doi.org/10.1145/1250790.1250800

P. Gaudry, A. Kruppa, and P. Zimmermann, "A gmp-based implementation of schönhage-strassen's large integer multiplication algorithm," in Proceedings of the 2007 international symposium on Symbolic and algebraic computation, New York, NY, USA, Jul. 2007, pp. 167-174. DOI: https://doi.org/10.1145/1277548.1277572

D. Harvey, J. van der Hoeven, and G. Lecerf, "Even faster integer multiplication," Journal of Complexity, vol. 36, pp. 1-30, Oct. 2016. DOI: https://doi.org/10.1016/j.jco.2016.03.001

A. A. Karatsuba and Y. P. Ofman, "Multiplication of many-digital numbers by automatic computers," Doklady Akademii Nauk., vol. 145, no. 2, pp. 293-294, 1962.

C. Lüders, "Implementation of the DKSS Algorithm for Multiplication of Large Numbers," in Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, New York, NY, USA, Jun. 2015, pp. 267-274. DOI: https://doi.org/10.1145/2755996.2756643

S. R. S. Rao, "Interesting Results Arising from Karatsuba Multiplication - Montgomery family of formulae," in Proceedings of the Sixth International Conference on Computer and Communication Technology 2015, New York, NY, USA, Sep. 2015, pp. 317-322.

A. Schönhage and V. Strassen, "Schnelle multiplikation grosser zahlen," Computing, vol. 7, no. 3-4, pp. 281-292, 1971. DOI: https://doi.org/10.1007/BF02242355

A. L. Toom, "The complexity of a scheme of functional elements realizing the multiplication of integers," Soviet Mathematics Doklady, vol. 3, no. 4, pp. 714-716, 1963.

Y. Wu, "Strength reduction of multiplications by integer constants," ACM SIGPLAN Notices, vol. 30, no. 2, pp. 42-48, Feb. 1995. DOI: https://doi.org/10.1145/199873.199880

A. Zanoni, "Iterative Toom-Cook methods for very unbalanced long integer multiplication," in Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, New York, NY, USA, Jul. 2010, pp. 319-323. DOI: https://doi.org/10.1145/1837934.1837995

L. De Stefani, "On the I/O complexity of hybrid algorithms for Integer Multiplication," arXiv:1912.08045 [cs], Jul. 2020, Accessed: Nov. 28, 2020. [Online]. Available: http://arxiv.org/abs/1912.08045.

A. Rezai and P. Keshavarzi, "Compact SD: a new encoding algorithm and its application in multiplication," International Journal of Computer Mathematics, vol. 94, no. 3, pp. 554-569, Mar. 2017. DOI: https://doi.org/10.1080/00207160.2015.1119269

V. Bunimov and M. Schimmler, "Efficient Parallel Multiplication Algorithm for Large Integers," in Euro-Par 2003 Parallel Processing, Berlin, Heidelberg, 2003, pp. 923-928. DOI: https://doi.org/10.1007/978-3-540-45209-6_127

B. P. Sinha and P. K. Srimani, "A new parallel multiplication algorithm and its VLSI implementation," in Proceedings of the 1988 ACM sixteenth annual conference on Computer science, New York, NY, USA, Feb. 1988, pp. 366-372. DOI: https://doi.org/10.1145/322609.322777

J. V. Tembhurne, "Parallel Multiplication of Big Integer on GPU," in Smart and Innovative Trends in Next Generation Computing Technologies, Singapore, 2018, pp. 276-285. DOI: https://doi.org/10.1007/978-981-10-8657-1_21

J. V. Tembhurne and S. R. Sathe, "Performance evaluation of long integer multiplication using OpenMP and MPI on shared memory architecture," in 2014 Seventh International Conference on Contemporary Computing (IC3), Aug. 2014, pp. 283-288. DOI: https://doi.org/10.1109/IC3.2014.6897187

C. K. Yuen and M. D. Feng, "Parallel multiplication: a case study in parallel programming," ACM SIGPLAN Notices, vol. 29, no. 3, pp. 12-17, Mar. 1994. DOI: https://doi.org/10.1145/181587.181589

L. De Stefani, "Communication-Optimal Parallel Standard and Karatsuba Integer Multiplication in the Distributed Memory Model," arXiv:2009.14590 [cs], Sep. 2020, Accessed: Nov. 28, 2020. [Online]. Available: http://arxiv.org/abs/2009.14590.

S. G. Akl, Parallel Computation: Models and Methods, 1st edition. Upper Saddle River, NJ, USA: Prentice Hall, 1996.

H. M. Bahig, H. M. Bahig, and K. A. Fathy, "Fast and scalable algorithm for product large data on multicore system," Concurrency and Computation: Practice and Experience, Apr. 2019, Art. no. e5259. DOI: https://doi.org/10.1002/cpe.5259

Metrics

Abstract Views: 64
PDF Downloads: 43

Metrics Information
Bookmark and Share