Jan 15, 2024A Memcomputing Approach to Prime Factorization
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 2 nd 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.
Sep 27, 2023Implementation of digital MemComputing using standard electronic components
Digital MemComputing machines (DMMs), which employ nonlinear dynamical systems with memory (time nonlocality), have proven to be a robust and scalable unconventional computing approach for solving a wide variety of combinatorial optimization problems. However, most of the research so far has focused on the numerical simulations of the equations of motion of DMMs. This inevitably subjects time to discretization, which brings its own (numerical) issues that would be absent in actual physical systems operating in continuous time. Although hardware realizations of DMMs have been previously suggested, their implementation would require materials and devices that are not so easy to integrate with traditional electronics. In this study, we propose a novel hardware design for DMMs that leverages only conventional electronic components. Our findings suggest that this design offers a marked improvement in speed compared to existing realizations of these machines, without requiring special materials or novel device concepts. Moreover, the absence of numerical noise promises enhanced stability over extended periods of the machines’ operation, paving the way for addressing even more complex problems.
Sep 18, 2023Scaling up prime factorization with self-organizing gates: A memcomputing approach
We report preliminary results on using the MEMCPU(tm) 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.
Mar 21, 2023MemComputing vs. Quantum Computing: some analogies and major differences
Feb 15, 2021Global minimization via classical tunneling assisted by collective force field formation
Feb 6, 2021Directed percolation and numerical stability of simulations of digital Memcomputing machines
Dec 22, 2020Coupled oscillator networks for von Neumann and non von Neumann computing
Nov 12, 2020Efficient solution of Boolean satisfiability problems with digital memcomputing
Jan 15, 2020Mode-Assisted Unsupervised Learning of Restricted Boltzmann Machines
Mar 19, 2019Aircraft Loading Optimization: MemComputing the 5th Airbus Problem
Mar 18, 2019Digital Memcomputing: from Logic to Dynamics to Topology
Oct 08, 2018Taming a non-convex landscape with dynamical long-range order: memcomputing the Ising spin-glass
Aug 29, 2018 MemComputing Integer Linear Programming
Jun 30, 2018Stress-testing memcomputing on hard combinatorial optimization problems
Memcomputing is a novel paradigm of computation that utilizes dynamical elements with memory to both store and process information on the same physical location. Its building blocks can be fabricated in hardware with standard electronic circuits, thus offering a path to its practical realization. In addition, since memcomputing is based on non-quantum elements, the equations of motion describing these machines can be simulated efficiently on standard computers. In fact, it was recently realized that memcomputing, and in particular its digital (hence scalable) version, when simulated on a classical machine provides a significant speed-up over state-of-the-art algorithms on a variety of non-convex problems.