Integer Factorization: Solution via Algorithm for Constrained Discrete Logarithm Problem

Abstract

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(³√n) complexity and, if the search is balanced, it has complexity O(n^1/3log^1/α n), where alpha>1.