Quantum simulator offers faster route for prime factorization

[Jim__]

From phys.org:

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

______________________________________________________________________________________

...

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 number 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 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 prime number tables, and found very similar distributions.

more ...