**This is the fourth article in a seven-part series on Algorithms and Computation, which explores how we use simple binary numbers to power our world. The first article, ****How Algorithms Run the World We Live In****, can be found here.**

A few years before Sergei Brin and Larry Page first incorporated their Google search engine into the business that helped build up the Internet as we know it, **Peter Shor** published a paper about the algorithm that was destined to break open all the locks on the connections that were supposed to keep the whole thing secure.

**Peter Shor** wasn’t some malicious anarcho-hacktivist but a mathematician working for **AT&T’s Bell Labs** looking to solve a difficult mathematical problem like every other mathematician in the field. His algorithm, known as **Shor’s Algorithm**, required a technology that barely existed in theory, much less reality, when he first described it in 1994.

**RELATED: WHAT WILL QUANTUM COMPUTING CHANGE, EXACTLY?**

There was no reason to think in the late 1990s and early 2000s that we would ever need to worry about the insecurity of **RSA encryption**, but now we know the truth: **RSA encryption** is destined to fail. Now, the improbable technology Shor used, **quantum computing**, is not only advancing at a rate similar to Moore’s Law—meaning that within a decade or two, quantum computers will be powerful enough to run **Shor’s Algorithm** and bust open **RSA encryption**—**Shor’s algorithm** itself helped inspire the development of quantum computing in the first place.

## RSA Encryption Was Once Believed Unbreakable

**RSA encryption**, which is used to encrypt everything from files on our hard drives to confidential Internet traffic, is built on the principles of **public key exchange** and the computationally difficult problem of **prime factorization**.

For a classical computer, an **efficient algorithm** for finding the **prime factors** of a **composite number** does not exist, meaning that the best we can do is find an answer a little less awful than **exponential time**. **RSA encryption** is usually qualified with a bit length, such as **128-bit**,** 256-bit**, etc., which represents the bit length of the key used to encrypt and decrypt data. So a brute-force algorithm with **exponential time complexity** working on a **128-bit encryption key** would need to attempt **2 ^{128}** values at a minimum.

This is equal to **340,282,366,920,938,463,463,374,607,431,768,211,456** possible keys and RSA encryption keys haven’t been as small as **128-bit** in more than a decade. The current standard recommended key length for an RSA encryption key is **2048-bit**, which is equal to **(340,282,366,920,938,463,463,374,607,431,768,211,456) ^{16}** possible keys.

These numbers are unfathomable to us, but there is a way to manage and even perform operations using these numbers, something known as modular arithmetic and it’s these operations that are at the heart of the RSA encryption algorithm.

In many countries that use a **12-hour clock** rather than a **24-hour clock** to keep time, they use modular arithmetic all the time, literally. If it’s **11 AM** and I ask you to meet me in **four hours**, you know that I want to meet at **3 PM**. That’s because we use the number **12**, called the **modulus**, to know when to start counting from zero again. Modular arithmetic uses this same process, only with numbers of enormous size to help perform calculations.

Like any other key exchange system, **RSA encryption** uses a **public key** and a **private key** to encrypt and decrypt data, except **RSA encryption** uses two numbers as its public key, a public exponent to use for encrypting a message and a **modulus** for the encrypting operation that produces the cipher. What makes this **modulus** so important is the fact that it is the product of **two very large prime numbers** and knowing those **two numbers** will allow you to reverse engineer the **private key** that unlocks the encryption.

The difficulty inherent to **RSA encryption** however is two-fold: the enormity of the numbers involved means you can’t brute force your way to the **private key** and the fact that **prime factorization** of this unbelievably large number is something no **classical computer** can hope to do in **trillions of years**.

## How Quantum Computers and Shor’s Algorithm Defeats RSA Encryption

Without getting bogged down in the finite details, **Shor’s Algorithm** is a three-part answer to the problem of **prime factorization** for * any* integer, so it works no matter how large the integer involved. The

**first part**is performed on a

**classical computer**in

**polynomial time**, but it is only the set-up for the

**second and most important part**. The

**second part**requires the use of specially constructed

**quantum circuits**to perform the

**quantum computation**needed to find the

**value**you need for the

**third part**, which allows you to find the

**prime factors**of the integer on a

**classical computer**.

The first part of the algorithm is transforming the problem of **prime factorization** into an **equivalent** problem that is solvable, namely, finding the **period** of a **modular operation**. If you can find the **period** of this function using as the integer you want to factor as a **modulus**, you can find the prime factors fairly quickly on a classical computer with some additional calculations.

The problem is that, like **prime factorization**, finding the **period** of this modular operation isn’t something a **classical computer** can do in **polynomial time**, but **Shor** showed in the **second part** of the algorithm that using a **theoretical quantum computer** your could calculate this **period** and, most importantly, he was able to prove mathematically that this part of the **quantum algorithm** ran in **polynomial time**. After finding the **period**, a **classical computer** could use it to find the **prime factors** of any integer.

## How Peter Shor and Shor’s Algorithm Kick Started Quantum Computing

**Peter Shor** showed that a theoretical **quantum computer** could solve an intractable mathematical problem in ways that a **classical computer** never could by side-stepping the need to calculate single values at a time. **Quantum computers** can perform operations on **qubits** in **superposition** and literally reduce the time complexity of a problem exponentially.

When **Shor** devised his algorithm, **quantum computing** didn’t exist in any meaningful way. The idea had been around for a while, but it was entirely theoretical, impractical to even attempt to build, and no one could see the utility in trying to build one since there was no example of anything a **quantum computer** could do that a **classical computer** could not.

By showing how a **quantum computer** could actually be useful in a way that **classical computers** couldn’t by solving a classically intractable problem in **polynomial time**, **Peter Shor** sparked the interests of researchers around the world who began their own research into **quantum computing** and now actual, working quantum computers are being built. It will be a decade at least before a quantum computer has enough qubits to break **RSA encryption**, but its end is certain and already cryptographers have opened up new avenues of research into Post-Quantum Cryptography to make sure that everything that needs to remain secure does.

After **Peter Shor’s** algorithm proved that hard problems for **classical computers **could be solved, others began looking at other hard problems that might also be solved by quantum computers, and for good reason; of the many problems that remain to be solved, the potential benefit to solving them is as enormous as the problems themselves.

**Come back tomorrow for the fourth article in our series on Algorithms and Computation, ****The Traveling Salesman and the Problem of Optimization Algorithms****.**

.(tagsToTranslate)Peter Shore(t)RSA encryption(t)Shor

This is a syndicated post. Read the original post at Source link .