Acceleration analysis of the quadratic sieve method based on the online matrix solving
Journal Title: Восточно-Европейский журнал передовых технологий - Year 2018, Vol 2, Issue 4
Abstract
<p>The algorithm for the<strong> </strong>online matrix solving<strong> </strong>is proposed. The rate of acceleration of the basic quadratic sieve method based on the online matrix solving<strong> </strong>is investigated. Acceleration of the quadratic sieve method will reduce the runtime, the complexity of the algorithm and expand the set of numbers, where this algorithm is the best.</p><p>It is shown that the modified algorithm has increased the number of successful decompositions. That is, the number of cases where the basic quadratic sieve (standard sieving interval and size of the factor base) failed to form a matrix to obtain a solution was reduced. This became possible due to the fact that in the modified algorithm there is no need to obtain all L<sup>a</sup>+2 B-smooth numbers prior to diagonalization of the matrix, as in the case of the basic method. Among other important characteristics of this method, it should be noted that when used, the same operations as in the basic quadratic sieve method are performed, only their order is changed. The computing complexity decreases if the set of B-smooth numbers, for which the power matrix vectors form a linearly dependent system, are found quickly.</p>According to the data obtained, the modified QS method, based on<strong> </strong>the online matrix solving, provides an acceleration of about 5.45 percent for numbers of 10<sup>130 </sup>in size. It is shown that improvements associated with solving the matrix cannot lead to a significant increase in the sieving interval. After all, the rate of acceleration decreases with increasing number N. Further improvement to the quadratic sieve method should be related to methods aimed at a significant reduction of the sieving interval and the size of the factor base, which in relative terms should be the greater, the higher N
Authors and Affiliations
Stepan Vynnychuk, Vitalii Misko
Keywords
Related Articles
- EP ID EP527871
- DOI 10.15587/1729-4061.2018.127596
- Views 82
- Downloads 0
Study of the influence of oxidizing parameters on the composition and morphology of Al2O3•CoOx coatings on AL25 alloy
<p>The influence of operating parameters of plasma-electrolytic oxidation in diphosphate cobalt-containing electrolyte on the process of formation of oxide coatings on alumosilicon alloy AL25 (GOST 1583) was studied. It...
Synthesis of a trend’s integral estimate based on a totality of indicators for a time series data
<p>The need for a qualitative estimation of social processes, trends, and activities executed by social governing institutions has been considered. It was determined that the information openness, availability of process...
Development of a method for ranking factors that influence the maturity of project quality management processes
<p>According to the results of the theoretical analysis of well-known and widely practically applied standards of quality management and project management, as well as models of maturity assessment of processes, 13 key r...
Acrylic acid synthesis by oxidative condensation of methanol and acetic acid on B–P–V–W–Ox/SiO2 catalyst
The process of oxidative condensation of methanol with acetic acid to acrylic acid on B–P–V–W–Ox/SiO<sub>2</sub> catalyst modified by hydrothermal method has been studied. Modification of the catalyst by hydrothermal tre...
Determining the parameters for connections among the elements of design of vehicles in terms of ergonomics and crew safety
<p>This paper reports a study into the working processes of the system «operator ‒ machine ‒ external environment» in land vehicles using the constructed mathematical model.</p><p>A significant effect has been determined...