By Joe PicklesJan 23 2023A team of researchers from academic institutions all over China has developed an algorithm that allows quantum computers to perform prime factorization. Previously, the fastest quantum algorithm for this process was Shor’s Algorithm, which required millions of qubits to work; the new algorithm needs just hundreds. This has significant implications for cryptography, as many cryptographic methods depend on prime numbers for security.
Image Credit: Zapp2Photo/Shutterstock.com
Prime Factorization
Prime factorization is the process of expressing an integer as the product of prime numbers only. For example, 140 would be expressed as 2x2x5x7. For each integer, there is only one correct factorization, and that factorization is unique to that integer; this is known as the fundamental theorem of arithmetic. Mathematicians have studied the process of prime factorization for centuries, though for most of this time, it appeared not to have a practical application. With the rise of computers, this changed.
In 1976, researchers at Stanford University discovered that prime factorization works for cryptographic purposes. This discovery created a brand-new field called Public Key Cryptography (PKC) and ushered in a new age of secure communication.
Previously in key cryptography, the “key” used to encrypt information was also the one used to decrypt it. In PKC, there are instead two keys, a private one and a public one. The public key can be used by anyone to encrypt information, but only those with the private key can then decrypt that information. This is incredibly useful for systems where lots of users need to send information securely to one central recipient, such as companies receiving bank details from their customers.
Prior to the prime factorization discovery, PKC was not feasible. If one tried to use existing cryptographic techniques to create the keys, the private key could be reverse-engineered from the public key because the two must always be linked in some way for the system to work. With Prime Factorization, the keys are still linked, but in a manner that is virtually impossible to break.
While one can quickly find the prime factors of small integers, even supercomputers struggle when the integers are large enough. On the other hand, it is relatively easy to find large prime numbers. In PKC, two large prime numbers are chosen, and these are used as the private key. The public key is the product of these two primes, and this is often a number that is around one thousand digits long. Classical computers would take an incredibly long time to discover the private key from this public key, making the encryption uncrackable without the private key.
Shor’s Algorithm
Quantum Computers can trivialize some tasks that would take classical computers a very long time to complete. The fact that Qubits exist as a probabilistic superstition of two states means that quantum computers excel at trial-and-error tasks, as they are effectively able to try multiple solutions to a problem simultaneously.
Shor’s Algorithm, named after the mathematician who created it in 1994, is a hypothetical algorithm that would allow a quantum computer to quickly perform prime factorization. While there exist classical algorithms for prime factorization, the time it takes these algorithms to factorize numbers grows almost exponentially as the number grows. The time it takes Shor’s Algorithm is negligible in comparison.
In the field of post-quantum cryptography, it is feared that Shor’s Algorithm could devastate PKC. Many systems rely on PKC for security, and once quantum computers can run Shor’s Algorithm, they will make short work of the encryption. Luckily, quantum computers are currently incapable of this. Shor’s Algorithm requires around a million reliable Qubits to run, and quantum computers are nowhere near that scale yet. However, the newly developed algorithm enables quantum computers to factorize primes even more quickly.
The New Algorithm
Researchers from institutions across China have collaborated to develop this new algorithm. It adapts Schnorr’s algorithm (a factorization process for classical computers) for use by quantum computers. Schnorr’s algorithm is built around the Shortest Vector Problem (SVP), a common optimization problem in computer science.
In an SVP, the goal is to find the smallest possible vector that can be made by combing a given integer vector basis. This can be used to solve problems that have been abstracted to the “lattice space,” a multi-dimensional representation of a problem as points evenly separated in space. Schnorr applied SVP principles to develop a novel method of prime factorization. While it did not actually speed up prime factorization for classical computers, the algorithm is well suited to quantum computers.
The team used the algorithm as a basis to build their new one, using the power of quantum computing to quickly test solutions to the SVP. They incorporated another algorithm called Babai’s Algorithm, which tests planes in the lattice space to narrow down the SVP combinations. Working in tandem, the two algorithms make short work of prime factorization with the abstraction method.
An early indication of this algorithm’s success is that it performed prime factorization on a 48-bit integer with just a 10-qubit system. The integer was of an order of magnitude around ten to the fourteen. This is still tiny when compared to public keys in use today, but it is a massive improvement over previous quantum computer capability. The relationship between the increase in the size of the integer and the time taken to factorize it is sub-linear for this algorithm, meaning that slightly more powerful quantum computers will be able to tackle much larger numbers. The team believes that with just 372 qubits, the most complex PKC method currently in use could be cracked quickly.
The Impact
This 372 Qubit ultimatum shows that cybersecurity companies need to find a solution to this problem in the near future. Until now, post-quantum cryptography was a field of hypotheticals, but this research shows that the threat of quantum hacking may soon be very real. The discovery of this prime factorization method may help companies future-proof their PKC systems, but it is unclear yet how long they have. The team is unable to predict what optimizations to hardware or software may come that will make this algorithm even more powerful. Only time will tell if the entire PKC system is obsolete, or if a smaller fix may keep it usable.
References and Further Reading
Peshin, A. How Are Prime Numbers Used In Cryptography? Science ABC. (2018) https://www.scienceabc.com/innovation/how-are-prime-numbers-used-in-cryptography.html
Shor, P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science. (1994) https://ieeexplore.ieee.org/document/365700
Yan, B. Tan, Z. Wei, S. Jiang, H. Wang, W. et al. Factoring integers with sublinear resources on a superconducting quantum processor. arXiv:2212.12372v1 [quant-ph]. (2022)
Disclaimer: The views expressed here are those of the author expressed in their private capacity and do not necessarily represent the views of AZoM.com Limited T/A AZoNetwork the owner and operator of this website. This disclaimer forms part of the Terms and conditions of use of this website.