Leveraging Lévy Flight for Efficient Divisor Identification in Odd Composite Integers
Xingbo Wang *
Guangzhou College of Applied Science and Technology, Guangzhou City, 511370, China and Foshan University, Foshan City, 528000, China.
*Author to whom correspondence should be addressed.
Abstract
In accordance with the distribution law of composite integers possessing a divisor of the odd semi-prime N = pq with 2 < p < q, and considering the characteristics of Lévy flight (LF), this paper presents an innovative approach that integrates LF with specific local search techniques (LS) to identify a divisor of N. This method exhibits minimal space complexity and, in theory, achieves logarithmic time complexity in optimal scenarios. A comprehensive framework for the approach is outlined, alongside the introduction of a simple-random-walk-blended LF (SRW-blended LF) algorithm. Key issues pertinent to the implementation of the algorithm are thoroughly analyzed and elucidated. Experiments conducted to factorize semi-primes demonstrate that the newly developed approach, implemented using Matlab software, yields highly satisfactory results.
Keywords: Integer factorization, randomized algorithm, Lévy flight, local search, blind search