MemComputing Releases Manuscript Addressing Prime Factorization Capability
MemComputing circuit simulation indicates polynomial scaling.
SAN DIEGO, 9/19/23 – MemComputing, Inc., a pioneer in cutting-edge computing architectures, has released its results from a study on computing prime factorization. The analysis was solicited as part of a Small Business Innovation Research (SBIR) contract with the US Air Force. The study assessed the potential to factorize large numbers using MemComputing’s patented circuit architecture, demonstrating the feasibility to solve prime factorization at scale.
The team developed an approach based on a congruence model, which takes advantage of the electronic circuit’s dynamical behavior to identify congruences among integers with special properties that are used to efficiently factorize. The team customized the circuit design composed of Self-Organizing Gates (SOGs) to effectively address the model, focusing on test problems from 30 to 150 bits. Rigorous software emulations of the circuit were used to measure the time to produce congruences. Results showed that the circuit generated the appropriate congruences for benchmark problems up to 300 bits, and the time needed to factorize followed a 2nd-degree polynomial in the number of bits.
The next step is to extend the effective range beyond 300 bits, which requires customizing the SOG design to even larger factorization problems, with the end goal of realizing the capability in an Application Specific Integrated Circuit (ASIC). The company forecasts that solutions for problems at the scale of 2048 bits could be achieved with either emulation or ASIC, and that the latter could be in real-time.
The manuscript detailing the study and the results can be found here: https://arxiv.org/abs/2309.08198.
A video presentation and demonstration can be found here: https://www.memcpu.com/videos/prime-factorization-presentation/.
“With this latest achievement, MemComputing reaffirms its unwavering commitment to spearheading innovation in the computational domain,” said John Beane, CEO of MemComputing, Inc. “This latest development not only showcases the raw power and versatility of our technology but also paves the way for significant advancements in fields that rely heavily on prime factorization, such as computer science and cryptography.”
About MemComputing, Inc.
MemComputing, Inc. is a deep tech company that specializes in solving complex optimization problems using its cloud-based MEMCPU™ Platform. Its proprietary circuit design, rooted in physics, harnesses the power of computational memory to overcome the limitations of traditional computing methods. MemComputing is developing a range of hardware solutions designed for numerous edge-processing applications for industries such as energy, transportation, logistics, and the DoD.