Quantum simulator offers faster route for prime factorization

April 10, 2018 by Lisa Zyga, Phys.org report
This plot of values in the factorization ensemble of 10,000 shows that the values correlate with the band spectrum of a quantum system. The red dot marks one example: the point N = 10,969,262,131 = 47,297 x 231,923, E = 1.00441815 (where Ek is a function described in the paper). Credit: Rosales and Martin. ©2018 American Physical Society

Factoring very large numbers into their prime "building blocks" is extremely difficult for classical computers, and this difficulty underlies the security of many cryptographic algorithms. While it's easy to factor the number 20 as the product of the primes 2 x 2 x 5, for example, factoring larger numbers becomes exponentially more difficult when using classical factoring algorithms.

In a new paper published in Physical Review A, physicists Jose Luis Rosales and Vicente Martin have developed a method that may make it much easier to factor very large numbers that are known to have exactly two prime factors. The new method determines the probability that any prime is one of the two prime factors of a given number. After determining these odds, the most likely prime factor candidates can be tested first, allowing for the prime factors to be identified much more quickly than before.

"The theory shows not only where the primes are located, but also the probability for a prime to be a factor of a given number," Rosales told Phys.org. "Of course, this has implications in cryptography because [the cryptosystem] RSA ignores this regularity."

One of the interesting things about the new method is that it doesn't use any kind of computer, either classical or . Instead it involves a physical quantum system—a ""—that, when encoded with the number to factor, exhibits a of energy values that is equivalent to the probability distribution of the prime factor candidates of the encoded number.

"Our aim is to develop a new quantum theory of the factorization problem using a quantum simulator," Rosales said. "Our approach has discovered a property with no classical analogy in number theory. Every pair of primes that solve the problem re-arrange themselves to form a regular pattern: the band spectrum of the quantum simulator."

The general idea behind the quantum simulator is something called the "factorization ensemble," which the researchers introduced previously. It is based on the idea that the primes are ordered from least to greatest (for example, 2 is the first prime, 3 is the second prime, and 101 is the 26th prime). It's also possible to take the square root of any number, and then compare the result to the closest prime. For example, the square root of 27 is a little more than 5, which is the third prime. By the definition of a factorization ensemble, this means that 27 belongs to the factorization ensemble of 3.

The physicists then showed that they could transform the factorization ensemble function into a function from quantum physics (the inverted harmonic-oscillator function). After many more steps, they eventually showed that the predicted energy spectrum of a quantum system corresponds to the distribution of primes in the factorization ensemble of a number. From this information, the researchers can determine the probability that a prime is a factor of that number. To test the validity of their method, the physicists tested certain numbers and compared their results to the actual distributions obtained using tables, and found very similar distributions.

The physicists theoretically demonstrated that the proposed quantum simulator can factor numbers that are many orders of magnitude larger than those that have been factored with quantum computers. In their paper, they report the results of using their method to determine the probability distribution of the prime factors of a number with 24 digits. Further, the method does this with far fewer resources than required by classical factoring algorithms.

"In quantum theory, the algorithmic complexity is only polynomial with the number of bits of the number to factorize," Rosales said. "As a matter of fact, our first results seem to confirm that the simulator requires only (log√N)3 quantum states to reproduce its spectrum of energies, a very encouraging result."

One final point of interest is that the new method has strong connections to the Riemann hypothesis, which, if true, would suggest that the prime numbers are distributed in a predictable way—in the same way as the distribution of the zeros of the Riemann-zeta function. Proving (or disproving) the Riemann hypothesis is one of the greatest unsolved problems in mathematics, and one of the Clay Mathematics Institute's Millennium Prize Problems.

"The primes should behave as quantum numbers if Hilbert-Polya's conjecture applies," Rosales said, referring to the long-standing approach to proving the Riemann hypothesis.

Going forward, the researchers are currently working on the experimental implementation of the quantum simulator by using two entangled particles in a Penning trap.

"The fully quantum treatment of the simulator would require quantum optical analysis of the interactions of photons with two (or more) entangled ions in a Penning trap," Rosales said. "This part of the program is yet in development. The aim is to build a quantum factoring experimentally. If successfully implemented, numbers many orders of magnitude bigger than those available for its quantum processing using Shor's algorithm will be factorized and, as a by-product, the Hilbert-Polya conjecture will be tested experimentally."

Explore further: Quantum physics offers new way to factor numbers

More information: Jose Luis Rosales and Vicente Martin. "Quantum simulation of the integer factorization problem: Bell states in a Penning trap." Physical Review A. DOI: 10.1103/PhysRevA.97.032325. Also at: arXiv:1704.03174 [quant-ph]

Related Stories

Quantum physics offers new way to factor numbers

November 28, 2016

(Phys.org)—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 ...

New largest number factored on a quantum device is 56,153

November 28, 2014

(Phys.org)—Researchers have set a new record for the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012. They have shown that the exact same room-temperature ...

A newly discovered prime number makes its debut

January 31, 2018

On December 26, 2017, J. Pace, G. Woltman, S. Kurowski, A. Blosser, and their co-authors announced the discovery of a new prime number: 2⁷⁷²³²⁹¹⁷-1. It's an excellent opportunity to take a small tour through the ...

Recommended for you

2 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

Isotherm7
5 / 5 (1) Apr 10, 2018
So will RSA be dead in a year? Sometimes this seems like a racket, or a spiraling weapons race between the makers and the breakers as a source of employment for both.
ab3a
not rated yet Apr 10, 2018
It's hard to say if this is a PKI killer yet or not. One thing is certain: We're going to need to use some much bigger prime numbers.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.