Classification and experimental studies of the factorization algorithms efficiency

Abstract

The subject of the study is factorization algorithms, namely experimental testing of the efficiency of modern algorithms for integer factorization, identifying patterns between factorization algorithms and the size of the numbers being factorized in terms of the time required to perform the factorization operation. The purpose of the article is to analyze the performance of factorization algorithms using various composite numbers, in particular medium-sized numbers (  digits), which allows evaluating their efficiency and execution time. In the course of the research, the following tasks must be performed: classify modern factorization algorithms, experimentally verify the efficiency of modern Pollard factorization algorithms (  and ), the elliptic curve method, the Dixon algorithm, and the quadratic sieve. To achieve the goal, general scientific methods were used: analysis of the subject area and mathematical apparatus, set theory, numbers and fields, planning, and experimental research. Results achieved. Experimental studies have shown that Pollard’s algorithms are effective for numbers with small divisors, but lose performance as the size of the numbers increases. The elliptic curve method has proven its usefulness in finding medium-sized divisors and has shown better scalability compared to classical stochastic methods. The Dixon algorithm, despite its relative simplicity of implementation, has demonstrated stochastic fluctuations in execution time, which limits its practical value in scenarios with strict time constraints. The most stable and predictable results were achieved for the quadratic sieve, which confirmed its suitability for factoring medium-sized numbers and provided the smallest spread of time values under conditions of multiple runs on identical data sets. Conclusions. The experiments fully confirm the theoretical expectations regarding the performance of the methods under study. The results indicate that simple algorithms (Pollard, elliptic curve method) are appropriate for preprocessing and detecting weak keys, while the quadratic sieve is the optimal choice for factoring medium-sized numbers. For large RSA modules, it is practical to use more complex algorithms, such as the general number field sieve. Further development of factorization algorithms involves parallelizing the factorization process and developing algorithms that use screening of impossible solutions.