Integer Factorization: Solution via Algorithm for Constrained Discrete Logarithm Problem
Boris S. Verkhovsky
DOI : 10.3844/jcssp.2009.674.679
Journal of Computer Science
Volume 5, Issue 9
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.
© 2009 Boris S. Verkhovsky. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.