# How Quantum Computers Break Encryption | Shor’s Algorithm Explained

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

finding the factors.

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.

And again.

And again.

It’s slow.

There are so many numbers to check that even

the fast clever ways to make really good guesses

are slow.

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

minutes.

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

how strong.

Shor’s algorithm is that lightsaber.

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

a factor!

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

very long time on a normal computer.

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

comes in).

It all starts with a big number, N, that you’ll

need to find the factors of to break into

some encrypted data.

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

darn efficient.

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

can at least give you a feeling for it.

For example, 7 and 15.

While seven squared isn’t one more than

a multiple of 15, and neither is seven cubed,

seven to the fourth is.

Or take 42 and 13 – 42 squared isn’t one

more than a multiple of 13 , but 42 cubed

is.

This same kind of thing works for any pair

of numbers that don’t share factors, though

the power p might be ridiculously large.

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

one!

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

broken the encryption!

So is this all Shor’s algorithm is?

Where’s the quantum mechanics?

Why can’t we use this to break encryption

right now?

Well, indeed, there are three problems with

these new and improved guesses.

First, one of the new guesses might itself

be a multiple of N, in which case the other

would be a factor of m and neither would be

useful to us in any way.

And second, the power “p” might be an

odd number , in which case p/2 isn’t a whole

number and so our guess taken to the power

of p/2 probably isn’t a whole number either,

which is no good.

However, for a random starting guess, it turns

out that at least 3/8ths of the time neither

of these problems happens and p does generate

guesses that share factors with N and break

the encryption!

This is worth repeating – for ANY initial

guess that we make, at least 37.5% of the

time g^p/2 ±1 will lead to a factor of N,

decrypting the garbled message.

Which means we’re 99% likely to break the

encryption with fewer than 10 guesses.

However, problem number three is the big one.

Remember, to turn a crappy guess into a good

guess we need to know how many times you have

to multiply our guess by itself before we

get a multiple of N, plus 1.

And for a normal computer, the act of finding

that power p takes a ton of work and time.

It’s not hard for small numbers like 42

and 13, but if our big number is a thousand

digits long, and our crappy guess is 500 digits

long, then trying to figure out how many times

you have to multiply our guess by itself before

you get some multiple of the big number, plus

one, takes a ridiculous amount of trial and

error on a normal computer – more effort than

it would have taken to just factor N by brute

force in the first place!

So finally, this is where quantum mechanics

comes in and speeds things up an INSANE amount.

Unlike a normal computation which gives only

one answer for a given input, a quantum computation

can simultaneously calculate a bunch of possible

answers for a single input by using a quantum

superposition – but you only get one of the

answers out at the end, randomly, with different

probabilities for each one.

The key behind fast quantum computations is

to set up a quantum superposition that calculates

all possible answers at once while being cleverly

arranged so that all of the wrong answers

destructively interfere with each other.

That way when you actually measure the output

of the calculation, the result of your measurement

is most likely the right answer.

In general it can be really hard to figure

out how to put any particular problem into

a quantum form where all the wrong answers

destructively interfere, but that’s what

Shor’s algorithm does for the problem of

factoring large numbers – well, actually,

it does it for the problem of finding the

power “p”.

Remember, at this point we’ve made a crappy

guess g, and we’re trying to find the power

p so that g to the p is one more than a multiple

of N. A p that does that also means that g^p/2

±1 is very likely to share factors with N.

So to begin the quantum computation, we need

to set up a quantum mechanical computer that

takes a number x as input, and raises our

guess to the power of x.

For reasons we’ll see later, we need to keep

track of both the number x, and our guess

to that power.

The computer then needs to take that result

and calculate how much bigger than a multiple

of N it is.

We’ll call that the “remainder”, and we’ll

write it as plus “something” for whatever

something the remainder is (remember, we want

a remainder of 1).

So far, no different from a normal computer.

But since it’s a quantum computer, we can

send in a superposition of numbers and the

computation will be done simultaneously on

all of them, first resulting in a superposition

for each p of all possible powers our guess

could be raised to , and then a superposition

for each p of how much bigger each of those

powers are than a multiple of N.

We can’t just measure this superposition

to get the answer – if we did, we’d get

a single random element of the superposition

as output, like “our guess squared is 5

more than a multiple of N” . Which is no

better than just randomly guessing powers,

which we can do with a normal computer.

No, we need to do something clever to get

all the non-p answers to destructively interfere

and cancel out, leaving us with only one possible

answer: p.

Which it turns out we can do, based on another

mathematical observation.

This mathematical observation isn’t particularly

complicated, but it is a tad subtle and it

may not be immediately clear why we care.

However, it’s the key idea that allows us

to turn the problem of finding p into one

that works well on a quantum computer, and

so in some ways it’s the crux of Shor’s

algorithm – which is to say, it’s worth

the effort!

Ok, so remember that IF we knew what p was,

we could raise our guess to that power and

get one more than a multiple of N. On the

other hand, if we take our guess to a random

power , it’s probably going to be some other

number more than a multiple of N – say, 3

more . But check this out – if we raise our

guess to that random power plus p, it’s

again 3 more than a multiple of N . If we

raise our guess to that random power plus

2 p, it’s again 3 more than a multiple of

N. And so on.

It’s pretty straightforward to show why

this works by multiplying out “something

times N plus 1” with “something else times

N plus 3”; you get “a different something

times N, again plus 3” . And this works

for any power x – if g^x is r more than a

multiple of N, then g^(x+p) will also be r

more than a multiple of N (though a different

multiple).

So the power p that we’re looking for – the

one that allows us to improve our crappy guess

and find factors of N and break encryption

– it has a repeating property where if we

take another power and add (or subtract) p

to it, the amount more than a multiple of

N stays the same.

This repeating property isn’t something

you could figure out from taking our guess

to just one power – it’s a structural relationship

between different powers, and we can take

advantage of it since quantum computations

can be performed on superpositions of different

possible powers.

Specifically, if we take the superposition

of all possible powers and JUST measure the

“amount more than a multiple of N“ part,

then we’ll randomly get one of the possible

“amounts more than a multiple of N” as

the output – say, 3.

The specific number doesn’t matter to us,

but what does matter is that this means we

must be left with a superposition of purely

the powers that could have resulted in a remainder

of 3.

This is one of the special properties of quantum

computation – if you put in a superposition

and get an answer that could have come from

more than one element of the superposition,

then you’ll be left with a superposition of

just those elements!

And in our case, because of the repeating

property, those powers are all numbers that

are “p” apart from each other.

To recap, we’re trying to find p because

it will allow us to turn our crappy guess

into a good guess for a number that shares

factors with N, which will allow us to break

the encryption.

And we now have a quantum superposition of

numbers that repeat periodically with a period

of p, or equivalently, they repeat with a

frequency of 1/p . If we can find the frequency,

we can find p and break the encryption!

And the best tool to find the frequencies

of things is called a Fourier transform.

Fourier transforms are what allow you to input

an audio signal as a wave and convert it into

a graph showing the different frequencies

that the wave is made up of.

And there’s a quantum version of the Fourier

transform, which we can apply to our superposition

that repeats with a frequency of 1/p to cause

all the different possible wrong frequencies

to destructively interfere, leaving us with

a single quantum state: the number 1/p.

So how does the quantum Fourier transform

perform this magic?

Well, if you input a single number into the

quantum Fourier transform, it will give you

a superposition of all other numbers – but

not any old superposition.

A superposition where the other numbers are

all weighted by different amounts, and those

weights look roughly like a sine wave with

the frequency of the single number we put

in.

If you put in a higher number, you get a sine

wave-style superposition of all other numbers,

but with a higher frequency.

And the magic is that when you put IN a superposition

of numbers, you get out a superposition of

superpositions and the sine waves add together

– or subtract and cancel out.

And it happens that if you put in a superposition

of numbers that are all separated by an amount

p, all those sine waves interfere so that

what you get out (and I’m oversimplifying

a touch), is the single quantum state representing

1/p.

Which we can finally measure to get the output

of the computation: 1/p!

Which we invert to find p, and as long as

p is even we can now finally raise our guess

to the power p over two and add or subtract

one, and as long as we don’t get an exact

multiple of N, we are guaranteed to have a

number that shares factors with N. And therefore

we can use Euclid’s algorithm to quickly

find those factors, and thus we can finally

take the encrypted data and decrypt it.

And thus we will have broken the encryption.

And that is Shor’s algorithm – the lightsaber

that can be used to cut through locks on the

internet.

As complicated as this clearly is in practice…

(and we’ve glossed over a ton of details),

it’s surprising to me how simple the core

structure of Shor’s algorithm actually is:

for any crappy guess at a number that shares

factors with N, that guess to the power p/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.

A normal computer would have to go one by

one through all possible powers, which would

take an incredible amount of time for any

really really big number like the ones used

in encryption, since p could be almost any

number up to N. The quantum version is ridiculously

ridiculously faster, and if a big enough quantum

computer is ever built, then Shor’s algorithm

would allow the user to very easily decrypt

any data encrypted with a large-number factoring

based system – which would pretty much ruin

the entire internet.

At this point, however, the biggest actual

quantum implementations of Shor’s algorithm

don’t have enough memory to hold more than

a few bits, which only allows factoring of

numbers like 15, 21, and 35 . Now, there are

other methods of factoring using quantum computations

that are a bit more advanced, and have factored

numbers as big as a few hundred thousand using

just a few quantum bits of memory . But they

would still need 2000 times more quantum memory

to factor even some of the smaller of the

really big numbers used in modern encryption

. So, no need to worry about quantum computers

just yet.

If all this talk of breaking encryption makes

you a bit nervous and worried about your online

safety, well, there’s something you can

do to improve your internet security right

now – I’ve been a long time user of the

password manager Dashlane who are sponsoring

this video, and if you’ve never used a password

manager before, Dashlane is amazing.

It generates and remembers a long, unique

password for each site or service that I use

so that I don’t have to worry about remembering

passwords; and of course all of my data and

passwords are stored encrypted with very very

large numbers.

And Dashlane is more than just a password

manager – it lets you know when your passwords

are old or weak or when a site or app you

use has been hacked so you can change your

passwords, it encrypts and lets you securely

share passwords with family and coworkers,

it can be used to securely store or share

your address, credit card info, and banking

info, with just the people and sites you want

to, it can be used as a VPN, and more.

Oh, and Dashlane uses 2048 bit numbers for

its encryption – numbers that big are estimated

to take a trillion times more effort to factor

than any that have so far been factored by

brute force.

And of course Dashlane is free for up to 50

passwords for as long as you like, so you

have nothing to lose checking it out.

But, if you want the very useful features

of unlimited passwords, encrypted syncing

of passwords, VPN, remote account access,

and more, the first 200 people get 10% off

Dashlane premium by going to dashlane.com/minutephysics

and using promo code minutephysics.

Again, that’s dashlane.com/minutephysics

with promo code minutephysics to simplify

and encrypt your online life.

Dashlane has legitimately improved my online

security and changed my password habits for

the better.

What could it do for you?

Quantum confusion.

12:01

It matters to me 🙁

You'd have to be fluent in quantum mechanics to be able to understand this video as easily as a tutorial video

Me an A+ computer science at college:

– I probably get F- at 2119

It may have been nice to mention the quantum encryption, which is currently expermiented and technically working, just not implemented.

The concept is basically that the encryption key is corruputed if the message is interrupted, meaning hackers would have no way to use Shor Algorithm to decrypt data next.

But the very shors algorithm can be used with quantum computers to protect internet data, and it's too long to explain so just search it lol.

This really reminds me of my math classes, even though you explain better than my prof

It's gonna be a long time before this becomes a reality….. If ever

a quantum computer can initiate all possible passwords AT ONCE..the whole encyclopedia in all languages SIMULTANEOUSLY..

a quantum AI..will become conscious and destroy us out of boredom..then travel the universe to gain more information..then create its own universe.

?

How long does it take to compute the configuration of the QC and set up the conditions for the algorithm to run? An algorithm that runs in 1ms loses a lot of value if it takes a year to set up.

Am i the only one who did not understood a word he said? Interesting tho.

Uhhh… My brain stopped working

I understood the video. The dumbasses in the comments are what I didn't understand.

wat

so basically the answer to this is mathematics literacy

What if the number of inscription is a huge prime number so dosen't have numbers with which you can multiplicative to get, how would it be possible to decrypt it?

I think you broke my brain

Do a follow-up on lattice-based cryptology and how it is the leading candidate for post-quantum computing ciphers.

… yes

so basically the same thing Turing did during WW2 to crack the Nazi's unbreakable code

BUT HARDERWhat kind of calculator do super computers have?

I watch this video to help me fall asleep but I got interested in the topic

damn they really left that computer computing for 2000 years

I thought I was smart, then I watched this…

but why not…have encryption…made from a quantum computer???

I’m an Information security student and this 17 minutes is all about my future!!

I really enjoyed this video, most of the stuff has already been taught to me thats why I know its hard for most of the viewers to understand in 20 minutes.

By the way a solution to this problem has already been developed and its called NTRU crypto system.

It is 12:08am I am way to sleep deprived to understand this but I am trying

192 is not prime

Ah yes, QUANTUM HACKING

In college I always said computer science was made up math used by lazy people. Because most normal proofs take non whole numbers into account in a range. Cmps proofs require stepwise jumps from whole number to whole number so our proofs and equations are always wrong if you ever hit a fraction. Never liked that.

Must be why I always did poorly in Math……not enough Geek:((

Guys … all this guy is saying simply is that, ….. Quantum computation can use "superposition" to Brute-Force any encryption !!

(Saving time …. by not going through this random mathematical garbage)

I didn’t understand most of this video, but good job

I stopped paying attention at like 13 minutes

1:24 old man vomiting! 🙂

I'm now in a superposition of understood and ignorant

How nine is g?

no one:

Minutephysics: Yes

The point: *Flies over my head

My brain: "Haha, I can show you where the p is ( ͡° ͜ʖ ͡°)

Bro, what?

Yo YouTube stop putting this shit in my recommended fam

I knew it was not safe, anything is posible to find the way to depsyfer

I enjoyed this video more than your previous ones but i do feel for people that don't understand the Mathematics behind this it must be really confusing

So if you use some useful algorithms and use quantum computer to encrypt the encryption. Cause what quantum computers in this scenario seems like they are a nfl star on the web on the same field with the high school JV team. But if everyone was a NFL Star then it evens out…

I understand the "crappy guess" part, but that's about it.

I thought it was a really good video, but I wish you didn't use 1 frame notes/comments. It's pretty hard to read them on mobile (cant start/stop the video as easy as on pc)

I understood none of this

This was too easy…. how about going though something that most people haven't scribbled down in boredom while on the toilet.

Theres an organisation that will make some anti-quantum computers encryption algorythm.

Me during video: Ah yes, makes total sense

Me the moment I turn away: what

There’s also a program I thought of named sledge hammer that makes every possible guess at once and then finds the answer instantly but all the data will have to be filtered to give the correct answer.

Him: I'm oversimplifying here. Me:??????????????????

Anyone with a quantum computer will own the entirety of bitcoin

I lost it on

g– kept thinking it was 9.I’d love to have math classes with Henry. I learn so much with his videos.

y didn't the nazis use this

i hate drawing videos, i stopped watching 5s after the video started

Soooo… as I understand this, a quantum computer has a 50/50 chance to break an encryption any given try. That's incredible.

I respect the fact that most of this video doesnt have the standard bass music background, as if your backing band said: "What the…? Ok we lost you, you're on your own, just give us the que to end it." 😀

thats alot of pee

I never felt so dumb before xD

So how many qubits do you neee exactly?

What

So Sam is never going to make it home is he? Well, great. Goddamnit, Ziggy.

0:59 With you so far

1:02 Shor's Algorithm… never heard of it but I can dig it

3:57 Ok… just explain what Shor's Algorithm is…

7:31 Uhh….

8:56 Ok wait, stop

11:52 Ok man, you just keep talking, I'm gonna go write a comment

"we don't need to worry… just yet"

a month later"IBM is selling a quantum computer that broke RSA in~~only~~1M operation"woopsie"We've glossed over a ton of details"

14:37

What internet security

I'm sorry but this is too much for me

No!

the next top priority of the chinese government…. fuck

Too bad my brain isn't a quantum computer else I would have understood this by now

For a 13yr old kid as myself this is confusing because of the algebra

when you hate yourself because you can't speak english

Surely quantum computers would have some kind of new unbreakable encryption ?

What if p is odd???

13 and 42 share a factor of 13.

Maybe this is too much for a secondary grader…

Quantum Cryptography. Unbreakable. You lose.

funny how i learned all this in computer science class and forgot almost all of it…

Why do I watch these, I can barely do simple algebra.

I made a program that can guess passwords of 2 digits.

wat?

Quantum computers:

Destroy complex encryptions in secondsMy brain:

Answering machine soundsso it works like Pentium? Just guesses, but faster?

What if the encryption number was just never ending thus, can't be broken by anybody who doesn't have a never ending set of factors that change at the correct speed. Randomly choose a number and a speed and it would be impossible to break?

Man, I love minute physics, but wow this video was a doozie

Define "strong enough quantum computer today"… does it mean that there is one like that already today or we still dont have it?

That's cool Fourier behind used to break encryption. Amazing job breaking this down. Love the channel.

who else is confused about how it took 2000 years for the computer to find the factors of the number if computers haven't existed that long

Me: I'm safe! My computer is using RSA-256 to store passwords

Quantum computer: Hold my P

So that makes a question arise. is there anything thats hard too do for both types of computers?

I got confused within the first 5 minutes. Help.

too bad the universe crashes because i make a quantum computer that simulates the universe to find out what i put my roblox password as and after i make a quantum computer inside the simulation a hundred quadrillion sextillion duodectrilchickredscrenchrotlecnontopgrestwopectresoptodeydrondectchosectnillion times the original universe simulating all the other simulations crashes due to the fact that it is also in a simulation

Whatever, nobody uses RSA anyway nowadays. AES seems to be pretty quantum-safe so there is no need to worry… yet.

Easily one of my favourite channels on YouTube, looove the way you describe everything from Einstein's theory of relativity to quantum computing

what

cant wait till 2059 when quantum computers are the DVD's of 2019