GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

The security of much of the modern digital world rests on a simple mathematical trick: it is incredibly easy to multiply two large prime numbers together, but it is hard to figure out which two numbers were used just by looking at the result. This one-way street is the foundation of RSA encryption, the system that protects online banking, private messages, and secure communications. For decades, the only known way to break this code was to try every possible combination of numbers until the right pair was found, a task so vast that even the most powerful supercomputers would take longer than the age of the universe to solve for large keys. While quantum computers promise to one day crack this code instantly, they are not yet ready for the job. This leaves a gap where classical computers must find a new way to solve the problem, not by brute force, but by treating the search for the missing numbers as a puzzle of energy and balance.

Researchers at the Indian Institute of Technology Madras have developed a new method to tackle this challenge using a standard graphics processing unit, the kind of chip found in high-end computers for gaming and video rendering. Instead of trying to guess the numbers directly, they transformed the problem into a landscape of hills and valleys, where the solution lies at the very bottom of the deepest valley. They mapped the bits of the two hidden prime numbers onto a grid of tiny switches, each of which can be in one of two states. The goal was to find the specific arrangement of these switches that creates the lowest possible energy state, a configuration that mathematically encodes the two correct prime factors.

To solve this, the team used a technique called simulated annealing, which mimics the physical process of cooling metal to remove defects. In their digital version, the system starts with a random arrangement of switches and a high level of "heat," allowing the switches to flip freely. As the system cools down, the switches settle into a more stable pattern. The researchers designed their software to run on a single powerful graphics chip, the NVIDIA GH200, which can perform thousands of calculations at once. Because the mathematical map they created is mostly empty—meaning most switches do not interact with each other—they organized the work so that the computer only focused on the connections that actually existed. This allowed them to update many switches simultaneously without causing errors, a feat that required a clever sorting method to ensure that no two interacting switches were changed at the exact same moment.

The system did not always find the perfect answer immediately. In their tests, the annealer consistently landed very close to the correct solution, often getting within a few percent of the true numbers. To bridge this final gap, the researchers added a second step: a guided search that checked numbers near the computer's best guess. They used a filtering method to skip over numbers that could not possibly be prime, drastically reducing the work required. For a 100-bit number, the entire process, from the initial setup to finding the final factors, took just over six minutes on a single machine. This is significantly faster than traditional methods, which would take hours for the same task.

The researchers tested their pipeline on numbers ranging from 16 to 128 bits. While they successfully factored 100-bit numbers in a matter of minutes, they noted that the method still relies on a final search step to find the exact answer. The speed of this final step depends heavily on how close the initial guess was to the truth. The team found that their method consistently provided a much better starting point than older, simpler guesses, which reduced the time needed for the final search by a large margin. They also demonstrated that using a specific mathematical technique known as Coppersmith's method could further speed up the process for larger numbers, potentially reducing the time from months to days for 128-bit numbers.

This work does not break current encryption standards, as the numbers tested are far smaller than those used in real-world security, which typically involve numbers with hundreds of digits. However, it proves that a classical computer, when guided by the right mathematical structure and optimized for parallel processing, can solve this type of problem much more efficiently than previously thought. The study suggests that the bottleneck is no longer the raw speed of the computer, but rather how well the initial guess can be refined. If future improvements can get the computer even closer to the solution, the final search step could become so small that the entire process might one day run in polynomial time, a theoretical speed that would change the landscape of cryptography. For now, the researchers have shown that by respecting the unique shape of the problem and using the massive parallel power of modern graphics chips, it is possible to turn a seemingly impossible mathematical lock into a solvable puzzle.