ANALYSIS OF THE USE OF MULTITHREADED COMPUTING TECHNOLOGIES TO FACTORIZE OF NUMBERS BY A BINARY ALGORITHM

Authors

  • I. Prots’ko Lviv National Polytechnic University, Lviv, Ukraine., Ukraine
  • R. Rykmas LtdС “Uniservice”, Lviv, Ukraine., Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2021-4-11

Keywords:

factorization, prime factors, multithreading, heterogeneous computation, parallel computation, remainder.

Abstract

Context. Providing high-speed computation by computer systems of factorization of number into prime factors requires the development of effective algorithmic methods using computational technologies. Fast computation of factorization of numbers is used in such applications as, protection of information data, in algorithms of discrete transforms for transition from one to multidimensional computations and others.

Objective. The purpose of the work is to analyze the implementation of technologies of multithreaded computation of factorization of integer value by the binary algorithm of the method of trial divisions using computer systems with multi-core processors and graphics accelerators.

Method. A binary algorithm of trial divisions that uses the remainders of each digit of the binary representation of a number to perform a divisibility check on prime factors of the canonical factorization of number in parallel.

Results. The analysis and comparison of multithreaded computations of software implementations of factorization of number by binary algorithm using hyper-threading, AMP C++, CUDA technologies in computer systems with multi-core processors and graphics accelerators. The results of the process of number factorization for multithreaded computing technologies using the same parallel core function are analyzed.

Conclusions. In the study of realizations of number factorization by the binary algorithm in the multithreaded mode, the technology of hyper-threading calculations using multicore processors is most effectively performed. Heterogeneous computing using AMP C++ or CUDA technologies on computer systems and graphics accelerators requires consideration of GPU microarchitecture features for parallel computing core functions.

Author Biographies

I. Prots’ko, Lviv National Polytechnic University, Lviv, Ukraine.

Dr. Sc., Associate Professor, Department of Automated Control Systems.

R. Rykmas, LtdС “Uniservice”, Lviv, Ukraine.

Software Developer.

References

Knuth D. E. The art of computer programming. 3-ed. Vol. 1: Seminumerical Algorithms, Menlo Park. California, Addison-Wesley, 1998, 762 p.

McClellan J. H., Rader C. M.. Number Theory in Digital Signal Processing. Englewood Clis, NJ, Prentice-Hall, 1979, 276 p.

Stalling W. Cryptography and Network Security: Principles and Practice. 6-ed. Upper Saddle River, NJ, Prentice Hall, 2013, 672 p.

Samuel S., Wagstaff Jr. The Joy of Factoring, Providence, RI: American Mathematical Society, 2013, pp. 138–141.

Brent R. P. Some parallel algorithms for integer factorisation, European Conference on Parallel Processing, Toulouse, 1999, Part of the Lecture Notes in Computer Science book series. Berlin, Springing-Verlag, 1999, Vol. 1685, pp. 1–22.

Hindriksen V. How expensive is an operation on a CPU [Electronic resource], Access mode: https://streamcomputing.eu/blog/2012-07-16/how-expensive-is-an-operation-on-a-cpu

Mishra M., Chaturvedi U., Saibal K., Pal S. K. A multithreaded bound varying chaotic firefly algorithm for prime factorization, Advance Computing Conference: 4th IEEE International conference, Gurgaon, India. February 2014: proceedings. Published by IEEE Computer Society, 2014, pp. 1322–1325. DOI: 10.1109/IAdCC. 2014.6779518

Makarenko A. V., Pykhteyev A. V., Yefimov S. S. Parallel’naya realizatsiya i sravnitel’nyy analiz algoritmov faktorizatsii s raspredelennoy pamyat’yu [Electronic resource]. Access mode: http://cyberleninka.ru/article/n/parallelnaya-realizatsiya-isravnitelnyy-analiz-algoritmov-faktorizatsii-v-sistemah-s- raspredelyonnoy-pamyatyu

Huang L. New prime factorization algorithm and its parallel computing strategy, Information Technologies in Education and Learning: International Conference (ICITEL 2015), Atlantis, 2015, proceedings. Published by Atlantis Press, 2015, pp. 1–4.

Koundinya A. K., Harish G., Srinath N. K. et al. Performance Analysis of parallel Pollard’s Rho algorithm, International Journal of Computer Science & Information Technology (IJCSIT), 2011, Vol. 5, No. 2, pp. 157–163. DOI: 10.5121/ijcsit.2013.5214

Kim D. K., Choi P., Lee M.-K. et al. Design and analysis of efficient parallel hardware prime generators, Journal of semiconductor technology and science, 2016, Vol. 16, No. 5, pp. 564–581. DOI: 10.5573/ JSTS. 2016.16.5.564

Gower J. E., Wagstaff S. S. Square form factorization, Mathematics of Computation, 2008, Vol. 77, No. 261, pp. 551–588.

Meulenaer de G. Gosset F., Dormale de G. M., Quisquater J. J. Integer factorization based on elliptic curve method: towards better exploitation of reconfigurable hard-ware, FieldProgrammable Custom Computing Machines: IEEE Symposium FCCM, Napa, California, 23–25 April 2007, proceedings. Published by IEEE Computer Society, 2007, pp. 197– 206.

Ishmukhametov S. T. Metody faktorizatsii natural’nykh chisel: uchebnoye posobiye. Kazan’, Kazan’skiy universitet, 2011, 190 p.

Prots’ko I. O., Gryschuk O. V. Computation factorization of number at chip multithreading mode, Radio, Electronics, Computer Science, Control, 2019, No. 3, pp. 117–122. DOI 10.15588/1607-3274-2019-3-13

Prots’ko I.O. Binarno-bitovi alhorytmy: prohramuvannya i zastosuvannya. L’viv, Triada plyus, 2020, 120 p.

Library CTPL [Electronic resource]. Access mode: https://github.com/vit-vit/CTPL.

Kirk D. B., Hwu Wen-mei W. Programming Massively Parallel Processors: A Hands-on Approach, Second Edition, Waltham. Morgan Kaufmann, 2012, 518 p.

C++ AMP: Language and Programming Model, Version 1.0, August 2012 [Electronic resource]. Access mode: https://download.microsoft.com

Downloads

Published

2021-01-11

How to Cite

Prots’ko, I., & Rykmas, R. (2021). ANALYSIS OF THE USE OF MULTITHREADED COMPUTING TECHNOLOGIES TO FACTORIZE OF NUMBERS BY A BINARY ALGORITHM . Radio Electronics, Computer Science, Control, (4), 122–128. https://doi.org/10.15588/1607-3274-2021-4-11

Issue

No. 4 (2021): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2022 І. О. Процько, Р. В. Рикмас

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA 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) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.