TY  - JOUR
AU  - Verkhovsky, Boris S. 
PY  - 2009
TI  - Integer Factorization: Solution via Algorithm for Constrained Discrete Logarithm Problem
JF  - Journal of Computer Science
VL  - 5
IS  - 9
DO  - 10.3844/jcssp.2009.674.679
UR  - https://thescipub.com/abstract/jcssp.2009.674.679
AB  - Problem statement: During the last thirty years many public-key cryptographic protocols based on either the complexity of integer factorization of large semiprimes or the Discrete Logarithm Problem (DLP) have been developed. Approach: Although several factorization algorithms with sub-exponential complexity have been discovered, the recent RSA Factoring Challenge demonstrated that it was still necessary to use several thousand computers working in a coordinated effort for several months to factor an integer n that was a product of two primes. Results: In this research it was demonstrated how to find integer factors of n using an algorithm for a constrained DLP. Several numerical examples illustrate details of the algorithms.  One of these algorithms has O(3√n) complexity and, if the search is balanced, it has complexity O(n1/3log1/α n), where alpha>1.