未登录,请登录后再发表信息
最新评论 (0)
播放视频

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
但留给你的存取码用数字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,
任意假设一个与N有公因数的g
that guess to the power p over 2 plus or minus one
将它乘以p/2次方 然后±1
is a much much better guess, if we can find p.
要是能求出p 则此式子得出的数字更好
And we CAN find p almost immediately with a single (if complex) quantum computation.
我们能通过一台量子计算机几乎马上找到p
So, first we make some random crappy guess
那么 首先我们任取一个数g
like, I don’t know, a hundred and one.
哪个数呢 那就101吧
Then we check to see if 101 shares a factor with 314191
然后检索101和314191是否有公因数
it doesn’t.
它没有
So our goal is to find the special power p
所以我们的目标是 找到那个有特殊力量的p
for which 101to the p over 2 plus or minus 1
它能使101的p/2次方±1
is a better guess for a number that shares factors with 314191.
和314191有公因数
To do this,
为了做到这点
we need to find p so that 101 to the p is one more than a multiple of 314191.
我们需要找到p 使101的p次方是314191的倍数加一
This is where we use my quantum computer
这就是我们使用量子计算机的时候
which can raise 101 to any power
它可以把101转化成任何次幂
and calculate how much more that power is than a multiple of 314191.
且计算它的多少次幂才能大于314191的倍数
If we start with a superposition of all the numbers up to 314191,
如果我们从所有数字开始叠加到314191
then the quantum computation
那么量子计算机
will give us the superposition of 101 plus 101 squared plus 101 cubed, and so on.
将会算出101 101的平方 101的立方等等的叠加
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.
比如说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,
这导致了74126的余数
which must all be “p” apart from each other,
必须是所有p和其他数的分离
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,
这意味着20和4367和8714等等的叠加
and the difference between them is p.
它们的不同就是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,
我们只知道它们被一系列p分离
or a frequency of 1 over p,
或者1的频率超过p
though we still don’t know what p is.
尽管我们仍然不知道p的数值
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
会得到1/p 2/p 3/p等等的叠加
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,
量子傅里叶变换不仅会输出1/p
it outputs a superposition of multiples of 1 over P
它输出了1/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,
由 1/4347 2/4347 2/4347叠加得到一个数据
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.
例如 假设为5/4347
And then we’d do the calculation again, and get,
然后我们再做一次计算 并且得到
say, 6 over 4347.
假设为6/4347
And then 2 over 4347, and so on.
然后是2/4347等等
Pretty soon we’d be able to tell that 1 over 4347 is the common factor of all of those,
很快我们就能够得出1/4347是它们的公因数
and so p is 4347.
所以p就是4347
And you can check that 101 to the 4347
然后你可以检查101的4347次方
is indeed exactly 1 more than a multiple of 314191
的确是314191的倍数加1
(though it’s a very very big multiple).
尽管它是一个非常非常大的倍数
So to get our better guess for a number that shares a factor with 314191,
所以我们为了得到与314191有公因数的猜想数
let’s take 101 to the power of 4347 over 2 plus one
让我们把101的4347/2次方加上1
oh, crap.
哦 废话
4347 is odd!
4347是奇数
So we can’t divide it by 2 and get a whole number.
所以我们把它除以2得到整数
So we have to start over.
所以我们不得不重新开始
Well, let’s pick another random guess, say, 127.
好的 让我们再随便猜一个 比如127
After going through the same process of creating a simultaneous superposition of raising 127
经过同一个求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.
我们最终会发现127 p的对应值为17388
And so raising 127 to p over 2 gives 127 to the 8694, plus or minus one,
所以将p带入 得到127的8694次方±1
for our new and improved guess of a number that shares factors with 314191.
作为我们对314191公因数改进后的最新猜测数
Using Euclid’s algorithm on 314191
对于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.
和127的8694次方减1 得到一个公因数379
And 829 times 379 does indeed give us 314191!!
并且829乘以379确实等于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已经很长时间 并且向你们强烈推荐
who are sponsoring this video.
它赞助了这一期视频
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也是一个VPN
Dashlane is free from up to 50 passwords for as long as you like,
只要你喜欢 Dashlane最多能免费提供50个密码
so you should really just go to dashlane.com/minutephysics right now to check it out.
所以马上去dashlane.com/minutephysics体验一下吧
And if you like Dashlane after trying it out (which I imagine you probably will),
并且 若在试用后发现你喜欢Dashlane(我猜测很可能会)
the first 200 people will get 10% off Dashlan premium by going to
前200人可在该网站上使用促销代码minutephysics
dashlane.com/minutesphysics and using promo code minutephysics
获得10%的额外折扣
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
同样也能在dashlane.com/minutephysics(促销码minutephysics)获得
Thanks to dashlane for supporting minutephysics.
感谢dashlane对《分钟物理》的支持
to simplify and secure my online life.
用这些功能来简化 和保护网络生活

发表评论

译制信息
视频概述

密码加密,以及使用舒尔算法下的分解

听录译者

收集自网络

翻译译者

好礼物

审核员

审核员LG

视频来源

https://www.youtube.com/watch?v=FRZQ-efABeQ

相关推荐