Exploring the Potential of Shor's Algorithm for Cryptography

Complexitiy of Pime Factorization

In cryptography, the prime factorization problem is used as the basis for several important algorithms, including the RSA (Rivest-Shamir-Adleman) algorithm for public-key encryption.

In simpler terms, two large prime numbers are chosen and multiplied together to obtain a large composite number. This composite number is made public, while the two prime factors are not. If a user wants to send a message securely, she/he can use the public composite number to encrypt the message, but only the person with the secret prime factors can decrypt the message.

The security of the RSA algorithm is based on the fact that finding the prime factors of a large composite number is believed to be computationally far fetched.

Shor’s Algorithm : Brief Intro

Shor’s algorithm is famous for factoring integers in polylogarithmic time i.e. the problem size gets larger, the time it takes to solve the problem grows much more slowly than the size of the problem itself.

Shor's algorithm does this by creating a quantum superposition of all possible values, and then use a quantum register to obtain information about the prime factors. This information is then used to efficiently find the prime factors by "collapsing" the superposition and provide a specific value.

It has potential to perform many computations in parallel using quantum superposition and interference, allowing it to factor large numbers much faster than classical algorithms with many important applications in areas such as cryptography.

Factors constraining the usage of the algorithm

1. It needs a large number of qubits, [thousands may be] to factorize RSA size large number, current state of quantum hardware is not there, yet!
2. To perform such an operation, qubits need to remain in superposition state for a particular length of time, called coherence, which is insuffcient as of now.
3. Environmental noise causes errors in quantum computations, which leads to ineffective execution of Shor's algorithm. Error-corrected qubits is still a major challenge and area of research.

Despite these challenges, reasearchers continue looking for work around and trying to develop new methods to make Shor's Algorithm work on quantum computers.