Definition: In 1994, Peter Shor, the MIT Maths Professor, devised a quantum algorithm for generating prime factors of large numbers much more efficiently than classical computers. Shor's algorithm is a quantum computer algorithm that can solve prime factors of an integer in polynomial time. It allows us to factorize into prime numbers in O(logN ^3) time and O(logN) space.
Shor’s Algorithm Explained
Finding prime factors has been a hard problem for centuries. The Factoring Problem is one of the unsolved problems in Computer Science. It may take a few seconds to find prime factors of 51, however finding prime factors of a 100 digit number might take years to factorize using multiple traditional computers working in parallel to each other.
Many encryption algorithms used for security in credit cards, and similar financial transactions, benefit by exploiting this "factoring problem". It is believed that if this factoring problem can be solved, so can the cracking of an encryption algorithm like RSA. A single quantum computer could easily solve this problem by executing Shor’s algorithm.
Shor’s algorithm can work only on computers with worka large set of quantum bits. In various quantum systems, many attempts have been made to implement Shor's algorithm; however, none has come close to implementing it with a few quantum bits. It is said that Shor’s algorithm is one of the most challenging algorithms in quantum computing known to date. The algorithm can be realized on a quantum computer.
Many encryption schemes assume that factorization of large numbers is impossible in polynomial time. If it was possible, then encryption algorithms like RSA could have been broken. This is leading to the rise of new concepts such as post quantum cryptography and Quantum hacking.
Shor’s algorithm will take 10243 operations to factorize a 1024-bit number. However, with a quantum computer running at 100 MIPS can factorize a 1024 bit number in seconds. To achieve a single, entangled state, it works by using 2 registers, of size 2048 and 1024 qubits respectively, that work coherently, to get a single entangled state.
Issues with Shor’s Algorithm
- Shor’s Algorithm is not the best method on classical computers. The algorithms like Quadratic Sieve, Lenstra Elliptic Curve Factorization and General Number Field Sieve perform better for this problem on a traditional machine.
- Despite Shor's Algorithm's incredibly fast performance, the largest number factored by a Quantum Computer using Shor's Algorithm is 21.
Applications of Shor’s Algorithm with a quantum computer
- Shor's algorithm can do prime factoring of very large numbers on a quantum computer.
- Shor’s algorithm can potentially be used to hack RSA and other secure data forms
- Shor’s algorithm can solve the problem of finding the period of a function.
Utimaco is able to provide quantum-resistant solutions that enable businesses to defend their systems against assaults based on quantum computers thanks to significant time and talent investments in post-quantum cryptography.
