Name: 量子计算机如何破解加密（How Quantum Computers Break Encryption | Shor's Algorithm Explained）
Uploaded: 2021-04-29T06:57:45.000Z
Duration: 17 min 31 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

The goal of encryption is to garble data is such a way so that no one who has the data

can read it unless they're the intended recipient.

程度副詞

And the encryption of pretty much all private information sent over the internet relies

immensely on one numerical phenomenon - as far as we can tell, it's really really hard

to take a really big number and find its factors using a normal, non-quantum computer.

Unlike multiplication, which is very fast (just multiply the digits together and add

them up ), finding the prime numbers that multiply together to give you an arbitrary,

big, non-prime number appears to be slow - at least, the best approach we currently have

that runs on a normal computer - even a very powerful one - is very slow.

Like, to find the factors of this number , it took 2000 years of computer processor time!

Now, it's not yet proven that we won't eventually find a fast way to break encryption

just with normal computers, but it's certain that anybody with a large working quantum

computer today would pose an immediate privacy and security threat to the whole internet.

And that's due to something called “Shor's Algorithm.”

Well actually it's due to quantum superposition and interference; they're just taken advantage

of by an algorithm developed by Peter Shor, which I'm now going to attempt to explain.

The kind of encryption we're talking about garbles or “locks” messages using a large

number in such a way that decrypting or “unlocking” the data requires knowing the factors of that

number . If somebody doesn't have the factors, either they can't decrypt the data, or they

have to spend a really really long time or a huge amount of investment in computing resources

Our current best methods essentially just guess a number that might be a factor, and

check if it is . And if it isn't, you try again.

There are so many numbers to check that even the fast clever ways to make really good guesses

For example, my computer took almost 9 minutes to find the prime factors of this number.

So if you used this number to encrypt your data, it would only be safe from me for 9

If, on the other hand, you used a number like the one that took 2000 years of computer processor

time to factor , your data would definitely be safe from me and my laptop, but not from

somebody with access to a server farm . This is similar to how putting a lock on your

door and bars on your windows doesn't guarantee you won't have stuff stolen from your house,

but does make it take more time and more work.

Encrypting data isn't a guarantee of protection - it's a way of making it harder to access;

hopefully enough harder that no one thinks it's worth trying.

But quantum computation has the potential to make it super super easy to access encrypted

data - like having a lightsaber you can use to cut through any lock or barrier, no matter

Roughly speaking, to factor a given number Shor's algorithm starts with a random crappy

guess that might share a factor with your target number, (but which probably doesn't),

and then the algorithm transforms it into a much better guess that probably DOES share

There's nothing intrinsically quantum mechanical about this - you can, in fact, run a version

of Shor's algorithm on a regular computer to factor big numbers, but perhaps unsurprisingly

the “turning your bad guess into a better guess” part of the process takes a very

On the other hand, this key step happens to be ridiculously fast on quantum computers.

So, our task is to explain how Shor's algorithm turns a crappy guess into a better guess (which

is purely mathematics), and why quantum computers make that fast (which is where the physics

It all starts with a big number, N, that you'll need to find the factors of to break into

If you don't know what the factors are (which you don't), you can make a guess; just pick

some number g that's less than N . We actually don't need the guess to be a pure factor

of N - it could also be a number that shares some factors with N, like how 4 isn't a

factor of 6, but shares a factor with it.

Numbers that share factors are ok because there's a two-thousand-year-old method to

check for and find common factors - it's called Euclid's algorithm and it's pretty

All this is to say that to find a factor of N, we don't have to guess a factor of N - guessing

numbers that share factors with N works, too, thanks to Euclid.

And if Euclid's algorithm found any shared factors with N, then we'd be done!

You could just divide N by that factor to get the other factor and break the encryption.

But for the big numbers used in encryption, it's astronomically unlikely that any single

guess will actually share a factor with N.

Instead, we'll use a trick to help transform your crappy guess into a pair of guesses that

are way more likely to share factors with N. The trick is based on a simple mathematical

fact: for any pair of whole numbers that don't share a factor, if you multiply one of them

by itself enough times, you'll eventually arrive at some whole number multiple of the

other number, plus 1 . That is, if a and b are integers that don't share factors, then

eventually a^p will be equal to m times b + 1, for some power p and some multiple m

. We don't have the time to get into why this is true, but hopefully a few illustrations

While seven squared isn't one more than a multiple of 15, and neither is seven cubed,

Or take 42 and 13 - 42 squared isn't one more than a multiple of 13 , but 42 cubed

This same kind of thing works for any pair of numbers that don't share factors, though

So, for the big number, N, and your crappy guess, g, we're guaranteed that some power

of g is equal to some multiple of N, plus 1 . And here's the clever part - if we rearrange

this equation by subtracting the 1 from both sides, we can rewrite g^p-1 as (g^p/2 + 1)(g^p/2

- 1) . You can multiply that back together to convince yourself that it works.

And now we have an equation that almost looks like “something” times “something”

is equal to N, which is exactly what we're trying to find - factors of N!

These two terms are precisely the new and improved guesses that Shor's algorithm prescribes:

take the initial crappy guess, multiply it by itself p/2 times, and either add or subtract

Of course, since we're dealing with a multiple of N rather than N itself, the terms on the

left hand side might be multiples of factors of N, rather than the factors themselves.

Like how 7^4/2+1 = 50, and 7^4/2-1 = 48, neither of which is a factor of 15.

But we can find shared factors by using Euclid's algorithm again, and once we do, we'll have

字幕列表影片播放

量子计算机如何破解加密（How Quantum Computers Break Encryption | Shor's Algorithm Explained）

eventually

figure

access

multiple