• 科普

SCIENCE

英语

ENGLISH

科技

TECHNOLOGY

MOVIE

FOOD

励志

INSPIRATIONS

社会

SOCIETY

TRAVEL

动物

ANIMALS

KIDS

卡通

CARTOON

计算机

COMPUTER

心理

PSYCHOLOGY

教育

EDUCATION

手工

HANDCRAFTS

趣闻

MYSTERIES

CAREER

GEEKS

时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

Shor的算法是如何对31419进行分解的？

How Shor's Algorithm Factors 314191

As a followup to the main video about

how quantum computer factor large numbers to break encryption.

I want to demonstrate how Shor’s algorithm

would factor a real live number!

Like, maybe you were bequeathed a bank vault full of pies,

but the access code left to you was encrypted using the number 314191

and you can’t get to the pies until you know the factors.

Luckily, I happen to have

a working quantum computer that can run Shor’s algorithm.

As a refresher, here’s a rough overview

how Shor’s algorithm factors large numbers quickly.

for any crappy guess at a number that shares factors with N,

that guess to the power p over 2 plus or minus one

is a much much better guess, if we can find p.

And we CAN find p almost immediately with a single (if complex) quantum computation.

So, first we make some random crappy guess

like, I don’t know, a hundred and one.

Then we check to see if 101 shares a factor with 314191

it doesn’t.

So our goal is to find the special power p

for which 101to the p over 2 plus or minus 1

is a better guess for a number that shares factors with 314191.

To do this,

we need to find p so that 101 to the p is one more than a multiple of 314191.

This is where we use my quantum computer

which can raise 101 to any power

and calculate how much more that power is than a multiple of 314191.

If we start with a superposition of all the numbers up to 314191,

then the quantum computation

will give us the superposition of 101 plus 101 squared plus 101 cubed, and so on.

and then the superposition of the remainders.

So we measure just the state of the remainders,

and we’ll get one remainder as output

say 74126.

From which we know that

the rest of the quantum state is left in a superposition of the powers

that resulted in the remainder of 74126,

which must all be “p” apart from each other,

which I explained in the other video.

Because we’re not actually dealing with particularly big numbers,

I’ve done the calculation

and can tell you that this would mean

we had a superposition of 20 and 4367 and 8714 and so on,

and the difference between them is p.

but in a real situation we of course

wouldn’t know what the numbers in the superposition are

we just know they’re separated with a period of p,

or a frequency of 1 over p,

though we still don’t know what p is.

The next step is to put the superposition through a quantum Fourier transform,

which would result in a superposition of 1 over p plus 2 over p plus 3 over p and so on

this is a part I glossed over in the main video,

but for technical reasons

the quantum Fourier transform doesn’t just output 1 over p,

it outputs a superposition of multiples of 1 over P

Again, because these are small numbers I can tell you that

we’d have a superposition of 1 over 4347 and 2 over 4347 and 3 over 4347 and so on,

but in practice we wouldn’t actually know what they were.

So, we measure the superposition,

and we’d randomly get one of the values as the output.

Say, for example, 5 over 4347.

And then we’d do the calculation again, and get,

say, 6 over 4347.

And then 2 over 4347, and so on.

Pretty soon we’d be able to tell that 1 over 4347 is the common factor of all of those,

and so p is 4347.

And you can check that 101 to the 4347

is indeed exactly 1 more than a multiple of 314191

(though it’s a very very big multiple).

So to get our better guess for a number that shares a factor with 314191,

let’s take 101 to the power of 4347 over 2 plus one

oh, crap.

4347 is odd!
4347是奇数
So we can’t divide it by 2 and get a whole number.

So we have to start over.

Well, let’s pick another random guess, say, 127.

After going through the same process of creating a simultaneous superposition of raising 127

to all possible powers

and then doing a quantum Fourier transform and so on,

we’d end up finding that the value of p corresponding to 127 is 17388.

And so raising 127 to p over 2 gives 127 to the 8694, plus or minus one,

for our new and improved guess of a number that shares factors with 314191.

Using Euclid’s algorithm on 314191

with 127 to the 8694 + 1 gives a common factor of 829
127的8694次方加1得到公因数829
and using it on 314191 with 127 to the 8694 – 1 gives a common factor of 379.

And 829 times 379 does indeed give us 314191!!

So we can break the encryption

and you can have your pie!

If you want to make sure your digital life

is more secure than the bank vault in this video,

then I highly recommend using a password manager

to generate and securely store

a long and unique password for each site and service you use.

I myself have long used and highly recommend Dashlane,

Dashlane has legitimately improved my online life.
Dashlane合理地改善了我的网络生活
It generates and remembers a long unique password

for each of my internet accounts so I don’t have to,

it lets me know when my passwords are weak

or when a site or app I use has been hacked,

it securely stores and with my permission autofills my credit card,

bank account and address into on website

so I don’t have to waste time typing that stuff in over and over,

it lets me securely share passwords with family and coworkers,

and on top of all that, Dashlane is a VPN, too!

Dashlane is free from up to 50 passwords for as long as you like,

so you should really just go to dashlane.com/minutephysics right now to check it out.

And if you like Dashlane after trying it out (which I imagine you probably will),

the first 200 people will get 10% off Dashlan premium by going to

dashlane.com/minutesphysics and using promo code minutephysics

Dashlane premium gets you the VPN, unlimited storage
Dashlane能提供VPN服务 无限存储
and syncing of passwords, remote account access, and more.

Again, that’s dashlane.com/minutephysics with promo code minutephysics

Thanks to dashlane for supporting minutephysics.

to simplify and secure my online life.