PARALLIZATION OF THE COMPUTATION OF CANONICAL SPLIT A NUMBER ON THE FACTORS

Abstract

The cоmputation of the canonical factorization of a number using the modified trial divisions method has been considered. The performing operations of the division a number of factorization into prime numbers for the testing on a repetition factor demands a respective loss of the execute time in modern computer systems. To reduce them, the presentation of the number of factorization in the binary form is used for the process of analysis on repetition factors. The residuals of weighting coefficient are defined for each digit of the binary representation the number of factorization, which is equal to one. The obtained values ​​of the residuals are accumulated and then the accumulated value is checked for the equality with the corresponding value from the set of prime numbers. In case of equality, we obtain an element of canonical factorization and again check the degrees of this element for a repetition factor. Otherwise, we proceed to the next larger prime number for further checking for a repetition factor. The independence of the subtasks to perform the check of the binary representation of a number on divisibility by prime numbers makes it possible to parallelize the execution of the factorization of a number in multi-core microprocessors of computer systems. Among the levels of the parallelism can be consistently identified: the definition of residual weighting coefficients, the accumulation of residuals for bits equel to one of the binary representation of the number of factorization, the checking for a repetition factor from the sets of primes. Software implementation in C++, according to the algorithm, schedules the computations in multithreads, using a pool of threads. In the algorithm for parallelizing the computations of the canonical factorization, depending on the entered value of the expansion number, the corresponding value of the number of primes with their powers is determined and is evenly distributed between the streams to perform an analysis of divisibility. As a result, the dependence of the run time the computation of the factorization of a number from the number of threads is defined in multi-core processors of Intel Core i3/i5/i7. For the each computer system exist the optimal number of the threads, which supports the minimal time of the canonical factorization of a number on the prime numbers.