2023/09/15 by Tristan A. Sharp, Sharp, Tristan, Rishabh Khare +5 · 1 citation
Computer Science · #Adaptation and Self-Organizing Systems (nlin.AO) #Coding theory and cryptography #Cryptography and Security (cs.CR) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2309.08198
openalex publication_date 2023/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We report preliminary results on using the MEMCPU\texttrademark Platform to compute the prime factorization of large biprimes. The first approach, the direct model, directly returns the factors of a given biprime. The second approach, the congruence model, returns smooth congruences to address the bottleneck of standard sieve methods. The models have size-dependent structure, and the MEMCPU Platform requires structure-dependent tuning for optimal performance. Therefore, for both models, 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 than other tested methods including general number field sieve. MEMCPU's congruence model was the most promising, which was scaled up to 300-bit factorization problems while following a 2nd degree 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.