COMPARATIVE ANALYSIS OF EXPONENTIAL AND SUB-EXPONENTIAL INTEGER FACTORIZATION ALGORITHMS

Аннотация

Integer factorization remains one of the central challenges in modern
number theory and continues to play a decisive role in the security of contemporary
cryptographic systems. Asymmetric cryptographic schemes—especially RSA—derive
their strength from the practical difficulty of breaking down a large composite number
into its prime factors. With continuous progress in both computing power and
algorithmic design, understanding how well different factorization methods perform
has become increasingly important for anticipating cryptographic resilience and
identifying where vulnerabilities might emerge. This paper provides an in-depth
comparison of the most prominent exponential and sub-exponential factorization
algorithms. Among the methods examined are classical approaches such as Fermat’s
technique, Pollard’s ρ, Pollard–Strassen, Shanks’ SQUFOF, Pollard’s p−1, and
Lehman’s algorithm, as well as more advanced strategies including Dixon’s method,
the Continued Fraction Method (CFRAC), the Quadratic Sieve, Lenstra’s Elliptic
Curve Method, and the Number Field Sieve. Each algorithm is explored through its
mathematical foundation, computational complexity, structural characteristics, and
practical range of effectiveness. By bringing together theoretical perspectives and
established performance insights, the paper offers a coherent view of how factorization
algorithms have evolved and why they matter for the security of modern cryptographic
systems.