Symmetric Folding: An Efficient Method for Accelerating Witness-Based Random Search

The performance of witness-based random search algorithms is highly influenced by the distribution density of witnesses. To optimize this distribution, we propose a novel method based on the symmetric folding of the objective dataset. Our approach involves establishing mathematical models for symmetrically folding points and regions in two-dimensional space and deriving a set of rigorously proven properties for folding operations on matrix-formed datasets, complete with computational formulations. Theoretical analysis and numerical experiments demonstrate that the proposed symmetric folding technique can nearly double the probability of successfully identifying a target element via random sampling. The efficacy of the method is validated by a case study on identifying a nontrivial divisor of an odd composite integer, demonstrating that the symmetric folding of the structured dataset can significantly improve the efficiency of randomized search procedures.