Speeding up the Multiplication Algorithm for Large Integers
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 arithmeticDownloads
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
Downloads
How to Cite
License
Copyright (c) 2020 Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
