A Memcomputing Approach to Prime Factorization
Tristan A. Sharp, Rishabh Khare, Erick Pederson, Fabio L. Traversa · 2023
We report preliminary results on using the MEMCPU™Platform to compute the prime factorization of large biprimes. The approach described here uses a congruence model that returns smooth congruences to address the bottleneck of standard sieve methods. The model has size-dependent structure, and the MEMCPU Platform requires structure-dependent tuning for optimal performance. Therefore, we tuned the platform on sample problems up to a given size according to available resources. Then we generated RSA-like benchmark biprimes to perform rigorous scaling analysis. The MEMCPU timings over the tuned range followed low degree polynomials in the number of bits, markedly different from other tested methods including general number field sieve. MEMCPU’s model was scaled up to 300-bit factorization problems while following a 2nddegree polynomial fit. We also discuss the approach to tuning the MEMCPU Platform for problems beyond the reach of today’s most advanced methods. Finally, basic analysis of the acceleration expected from an ASIC implementation is provided and suggests the possibility of real time factorization of large biprimes.