COMPUTATION FACTORIZATION OF NUMBER AT CHIP MULTITHREADING MODE

Authors

  • I. O. Prots’ko Lviv National Polytechnic University, Lviv, Ukraine
  • O. V. Gryschuk LtdС “Lohika”, Lviv, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2019-3-13

Keywords:

Factorization of numbers, prime factors, residuals of weight coefficients, threads pool, parallel computation

Abstract

Context. Ensuring high-speed calculation by computer systems of the classical task of factorization of integer value on simple factors
requires the development of effective algorithmic methods using the latest information technologies. Fast computation of factorization of
numbers to provide high cryptocapability of information data, using multidimensional representation of one-dimensional sequences of
information data and other applications is sufficiently in demand in many practical tasks.
Objective.The purpose of the work is to improve the method of trial divisions to compute the factorization of integer value with using
parallelization of computations and efficient use of computing resources of computer systems, which ensures faster computation of the
values of prime factors of the decomposition.
Method. It is proposed to use the residuals of each digit of the binary representation of the factorization number in order to check for
divisibility in the method performing of trial divisions into prime numbers.
Results. The result of the study is to develop of a program of parallel execution of the factorization of integer value in computer systems
with multi-core processors.
Conclusions. In the research, a method of checking for divisibility using the residuals of each digit of the binary representation of the
factorization number was applied, which allows for multi-threaded mode to execute the decomposition of the number into the factors. The
basic idea of applying the corresponding mathematical apparatus is to use the residuals of the integer exponent of the number two from prime
numbers. As a result, the accumulation of residuals is performed, which is checked for equality with the corresponding prime number and its
degrees. The possibility of a multithreaded software organization for computing the number factorization ensures its parallel execution in
multi-core processors of computer systems

Author Biographies

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

PhD, Associate Professor of Information Systems and Technologies Department

O. V. Gryschuk, LtdС “Lohika”, Lviv

Software Developer

References

Vinogradov I. M. Osnovy teorii chisel. Moscow, Nauka, 1981, 167 p.

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

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.

Orlov V. A., Medvedev N. V., Shimko N. A., Domracheva A. B. Teoriya chisel v kriptografii: ucheb. Posobiye. Moscow, Izd-vo

MGTU, 2011, 223 p.

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

Hindriksen V. How expensive is an operation on a CPU [Electronic resource]. Access mode: https://streamcomputing.eu/blog/2012-07-16/how-expen- sive-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-sraspredelyonnoy-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.

de Meulenaer G., Gosset F., de Dormale G. M., Quisquater J. J. Integer factorization based on elliptic curve method: towards better exploitation of reconfigurable hardware, Field-Programmable Custom Computing Machines: IEEE Symposium FCCM. Napa,

California, 23–25 April 2007, proceedings, Published by IEEE Computer Society, 2007, pp. 197–206.

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

Protsko I., Teslyuk V. (Ukraine)Pat. 116912 Ukraine, G06F7/04(2006.01), G06F17/10(2006.01). Device of canonical factorization a number on factors; applicant Lviv National Polytechnic University, № а201604083; update. 14.04.2016; pubdate.

05.2018, bul. №10, 4 p.

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

Division algorithm [Electronic resource]. Access mode:https://en.wikipedia.org/wiki/Division_algorithm#Restoring_division

Architectures-optimization [Electronic resource] Appendix C. Access mode: https://www.intel.com/ content/dam/doc/manual/64-ia-32-architectures-optimi- zation-manual.pdf

Downloads

Published

2019-10-01

How to Cite

Prots’ko, I. O., & Gryschuk, O. V. (2019). COMPUTATION FACTORIZATION OF NUMBER AT CHIP MULTITHREADING MODE. Radio Electronics, Computer Science, Control, (3), 117–122. https://doi.org/10.15588/1607-3274-2019-3-13

Issue

No. 3 (2019): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2019 I. O. Prots’ko, O. V. Gryschuk

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.