Any number can, in theory, be written as the product of prime numbers. For small numbers, this is easy (for example, the prime factors of 12 are 2, 2, and 3), but for large numbers, prime factorization becomes extremely difficult—so difficult that many of today’s cryptography algorithms rely on the complexity of the prime factorization of numbers with hundreds of digits to keep private information secure.
However, no one is exactly sure of just how difficult it is to decompose very large numbers into their prime factors. This question, called the factorization problem, is one of the biggest unsolved problems in computer science, despite the use of advanced mathematical and computer science strategies in attempts to solve it.
Now in a new study published in Physical Review Letters, researchers Jose Luis Rosales and Vicente Martin at the Technical University of Madrid have taken a different approach to the problem. The researchers have shown that the arithmetic used in factoring numbers into their prime factors can be translated into the physics of a device—a “quantum simulator”—that physically mimics the arithmetic rather than trying to directly calculate a solution like a computer does.
Although the researchers have not yet built a quantum simulator, they show that the prime factors of large numbers would correspond to the energy values of the simulator. Measuring the energy values would then give the solutions to a given factoring problem, suggesting that factoring large numbers into primes may not be as difficult as currently thought.
“The work opens a new avenue to factor numbers, but we do not yet know about its power,” Rosales told Phys.org. “It is very striking to find a completely new way to factor that comes directly from quantum physics. It does not demonstrate that factoring numbers is easy, but finding new ways to factor certainly does not add to the strength of algorithms based on its assumed complexity.” Source: Quantum physics offers new way to factor numbers