MemComputing Prime Factorization of RSA Keys
Presentation and Demo
This video presents results from a U.S. Air Force SBIR project that explored using memcomputing to solve prime factorization. Memcomputing is an unconventional computing paradigm that can be realized using self-organizing circuits to solve complex optimization problems. The MEMCPU™ Platform is a cloud-based emulation of a memcomputing circuit. It has been delivering solutions for otherwise intractable commercial and DoD problems, including maritime shipping, military airlift scheduling, drone swarm mission planning, optimization of LEO satellite constellations, and various other combinatorial problems.
MemComputing’s Approach
The approach to factorization discussed in this video was developed by MemComputing and is based on sieving. The MEMCPU Platform was programmed to return congruences among integers that are used to efficiently factorize biprimes following standard sieving methods. A benchmark of RSA-like biprimes was generated for a robust performance analysis. Existing methods, e.g., the general number field sieve (GNFS) and a commercial Integer Linear Programming (ILP) solver, demonstrated super-polynomial scaling on this benchmark as expected. Memcomputing was able to be tested up to 300 bits and showed scaling following a 2nd degree polynomial fit.
MEMCPU Platform vs ASIC
This video also discusses the memcomputing circuit design procedure. It describes the challenges and solutions to continue the scaling beyond 300-bits as well as the transition to ASIC development. Extrapolation of the scaling suggests the potential to solve factorization problems of 2048 bits in weeks when in emulation mode and in real-time using an ASIC.
The final section of the video includes a demonstration using the MEMCPU Platform.