# How Shor’s Algorithm Factors 314191

As a followup to the main video about how
quantum computers 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. 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 dunno, 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! 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, 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, who are sponsoring this video. Dashlane has legitimately improved my online
life – 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 info on websites 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 for up to 50 passwords for
as long as you like, so you should 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 get 10% off Dashlane premium by
going to dashlane.com/minutephysics and using promo code minutephysics – Dashlane premium
gets you the VPN, unlimited storage and syncing of passwords, remote account access, and more. Again, that’s dashlane.com/minutephysics
with promo code minutephysics to simplify and secure your online life.

## 95 thoughts to “How Shor’s Algorithm Factors 314191”

1. KazoWAR says:

uh… what?

2. dankexe says:

I have one question

What?

3. Gopi nath Kaki says:

just buy another pie….

4. Ralph Ocava says:

This does not freaking help…

5. DostLP says:

So is there any guarantuee to find a working solution faster than O(n)? Otherwise there can be situations where the intermediate results are always not divisible by 2 until you've made n guesses.

6. Xzila says:

This should be on numberphil3

7. Galvin Midnight says:

0:00 here from thumbnail hmm
1:00 OK that sounds interesting so far
2:00 duh let's go to comments section which would be more realistic😂

8. pi20 sf3 says:

Just saw algorithm word so came but now regretting… 😂😂 Understood nothing other than factor to the factor something

9. Andrey Andreev says:

The cake is a lie!

10. Tepax Gamer says:

omg i didnt understand nothing but i see this videos lol

11. Mikey Mike says:

Yeah I'm still going to go with……………………what?

12. Bei Zhang says:

And you still didn't explain QFT 😂

13. MoSK Thinks says:

Why not just start with 2 as a guess, and then 3, 5, 7, etc…?

14. HappyViking888 says:

Use Digi-ID instead. Much better then dash!

15. RonBest says:

Hey! I need help with a math problem, and this seem to be the right place to ask.
Here it goes:

If i have 25 slots, and each slot has a 1/165 chance to roll a "win", and each slot can only roll once then it has used it's charges, and all slots will have a roll, no ones is left un-rolled in the end. So what formula do i use to find out the chance to roll 1 win out of the 25 slots, and 2 wins, and 3 wins etc?
So far i have only figured out how to find the chance to roll 0 wins, 1 win and 25 wins. (or i am pretty sure i have)
0 wins: (164/165)^25 = ~0,859 (~85,9%)
25 wins: (1/165)^25 = ~3,655e-56 (~0%)
i also think i might have figured out a far fetched way to find out the chance for just 1 win out of 25 slots:
25x(164^24)/165^25 = ~0,1309 (~13,1%)
and the combined chance to get any amount of wins between 1-25 should be 1-(chance for 0 wins) = ~0,1409 (~14,1%)
But on the rest im stuck, all formulas i try result in too high %, so when i add up the % for 0 wins, 1 wins and 2 wins it already end up at over 100% combined chance which is impossible so that means my calcs are wrong, and i belive my calcs are right for 0 and 1 wins so i figure it's the calcs for the 2 wins and upwards where i mess up.

Any math experts here that can help me with this? This is for a game i play online btw, where a situation with these odds occur. Thanks in advance 🙂

16. Ashwin Rajasekar says:

Couldn’t you use a perfect square as your “crappy guess” so that even if p is odd, g^(p/2) is still an integer?

17. Zain Majumder says:

Nice follow up to the previous video. Much clearer now.

18. Xatnu Rowan says:

Great video, directly answered all the questions I had from last video 🙂

19. liveunderwater says:

I remember learning this in 1st grade.

20. Piyush M says:

A serious suggestion
If you follow
It's physics not rap

21. B appo says:

How about making the sound of oxygen like you made the sound of hydrogen for like a 7 year special?

22. Mr. J_Krr_ says:

the last two videos were…

scrambled over my head

23. Niranjan SD says:

Great Explanation… just checked whether 829 and 379 are primes or not. They are primes

24. Sandeep Banik says:

Yes, I believe you.

25. PP says:

I understood nothing!
One reason its just too fast, there is no time to think for one second what i just heared.
Really, its way too fast for such an complicated (at least for me) topic.

26. Neil Gupta says:

3:11 What's that program?

27. Freedom says:

You can, example 2^2*1.5=8=4^1.5

28. Steak Saignant says:

When I go through a hard time with my thesis and think I am dumb and worthless, I look for videos like this to read the comment section. Seeing people saying that they don't understand makes me feel clever for a few minutes…

29. Mario Gonzalez says:

I feel proud of myself for being recommended these kind of videos even though I don’t understand shit

30. Heena Trevadia says:

This video for me is just seeing random stick figures and getting acoustic inputs

31. Mo_dimi says:

Please can someone help?

(4 pts) A 30.0 kg child sits on one end of a long uniform beam having a mass of 20.0 kg, and a 40.0 kg child sits on the other end. The beam balances when a fulcrum is placed below the beam a distance 1.10 m from the 30.0 kg child. How long is the beam?

A)2.20 m B)1.98 m C)1.93 m D) 2.07 m E)2.12 m

32. Calvin Terkildsen says:

Lol what?

33. Calvin Terkildsen says:

Whatch at 0.25x for better experience

34. Bavo Coomans says:

Remember when this channel used to explain to us you should run when it's raining so you get less wet?

35. Frederic Conrotte says:

worse minutephysics video for me 🙁 didn't understood a thing. Previous videos were clearer !

36. nikhil nair says:

could have just went to the nearby bakery

37. Dubey says:

I liked your video and left because I can't understand what's happening.

38. SaberTooth2251 says:

This is a really great follow up to the previous video. Really helps to illustrate just how powerful this algorithm is.

39. FlyingHazel says:

Now I‘m as smart as before but hungry for pie.

40. turbotoblast4 says:

This is truly amazing :O

41. Mark Molenaar says:

I know your channel is called minutephysics for a fact, but is it really necessary to talk this fast?

42. saikiran reddy says:

My understanding is super positioned between nothing and everything

43. Malcolm Gillis says:

Whenever I think I'm smart or get full of myself, I watch any of these videos and I am instantly humbled to my low IQ.

44. P Square says:

When you said 'we still don't know P', I thought 'we don't know many things along with P'.

I don't see why it is necessary to go up to N. One of a pair of factors has to be smaller than sqrt(N).

46. Michael Lin says:

Easier summary: Basically, make a guess, start finding powers of that guess, convert those into a simplified version of a wave (basically, decompose a wave into frequencies), and collapse the superposition of all of those computations. Because the collapsed superposition is random, you need to get a few samples before you find the factor.
Factoring numbers is hard, but finding the common factor of two numbers is easy (it's called Euclid's algorithm). It's not good for breaking giant numbers composed of two primes because the chances of you finding two numbers sharing the same prime is incredibly small. Shor's algorithm improves those chances and gets you better probabilities, so you can actually find a common factor that isn't one.

47. Paulo Bardes says:

Can you make a video about QFT?

48. ProjectNightingaleForResponsibleMedicine says:

huh

49. Jonathan Cox says:

cake is a lie and so is the pie

50. Daniel Astillero says:

LastPass is better than dashlane

51. Gaurav Singh says:

Thanks

52. Sagami says:

S I M P L E

53. bluefroggy says:

“A real live number” wow i have never seen one

54. Clay Baxter says:

Would you explain how you use Euclid's algorithm for determining GCD(314191,127^8694) please. I am quite sure Euclid's Euclid's algorithm would never work and do not understand how the improvements made to the algorithm (to deal with such ridiculously large numbers) work.

55. PaulBunkey says:

Installed DashLane! Does it support Firefox? No. Uninstalled DashLane!

56. Tux Mux says:

"314191" "pie"
I hope you step on a Lego

57. TheOtherSteel says:

I used more calories trying to understand this more than superficially than I would have received from eating the entire pie.

58. Conan Tan says:

"As a refresher, here's a rough overview of how Shor's algorithm factors large numbers quickly"

Me: "Ah shit, here we go again."

59. The World Of Panda says:

listen i build computer calculators in excel that can do this just fine but i dont have a fkn clue what your saying past “p p p p p p p” and im feeling childish hearing you say p every few seconds

i just tell it what to do not how to do it based on the head banging i do on the number keys

60. shashwat Sen says:

you speak so fast

61. Meltoss says:

Everyone: How does any of this work?!
Me, having taken a class in modern physics: laughs in Quantum Mechanics

62. GD Illuminati65 says:

I almost understood it.

63. AstCeriskos says:

My brain segfaulted

64. Finley Xavier says:

I didn't even understand this a little

65. aysseralwan says:

Am I the only one who got here because Shor is a main deity in The elder scrolls series?

66. jojojorisjhjosef says:

at some point I wonder who's to blame for the fact that I don't understand the video: me, Henry or the topic.

67. Neventual says:

My new goal is to comprehend this video. I project 100% comprehension by 2062.

68. Morgana - The Fallen says:

314191 X 1

69. BeBaNaNa says:

Me at the start of the video: hmm… sounds like a cool video

Me at the end of the video: Tf? Is he speaking English?

70. Vvardenfell Fella says:

by Shor, what is this treachery FOR SKYRIM

71. Hello_ World_ says:

Math are awesome

72. Scootland Braunskies says:

my brain just fell outta my nose 🧠👃

73. 일반인간 says:

379 X 829 = 314191

74. EdP IV says:

Cool I am lost

75. Jay Paans says:

Uhhmmm,,, I have no idea what you just said. Didn't follow it by a long shot. Nope. You lost me. Sorry.

76. Киара Мс says:

I Came With a Huge LIKE!
There's no worry about.
Pixsture and Globyous
We need to abliviant our struggle for #WorldWithoutWar<3

77. Satendr Singh says:

What is thissssssssssssssssssssss.

78. andrewxc1335 says:

There is someone I know of who has allegedly created a quantum computer simulator, which runs in approximately similar computer time to the theoretical quantum time. Not sure how much of that is accurate, but if it is…
She was dragging her feet about working with the professor on this project, and was going to sign over rights to either him or some corporation. My colleagues and I referred her to good patent attorneys.

79. raglanheuser says:

yea ok no. that was like walking into a room in the middle of a lecture for a class that's not in your major

80. Lucas Tsui says:

Haha, pi/pie.

81. ung ket says:

I just hear rap god song

82. dora Liu says:

1 X 314191 = 314191 Solved!!!!!

83. QuintaFeira12 says:

"This is where we use me quantum computer…"

And this is where I got lost.

84. Akash Khansili says:

how did you get 127^8694? I am getting infinity on my laptop (MATLAB) also on my phone lol

85. Noman Sohail says:

Please make a video on Quadratic Sieve Algorithm with an example. Please…

86. Ali Raza says:

Confusing stuff 😬

87. Geoff Vane says:

How does the computer know it found the right password? It doesn’t know what the decrypted data looks like.

88. Izzy Stradlin says:

I WAS WITH YA, RIGHT UP TO THE POINT WHEN YOU SAID, I'LL SHOW YOU HOW TO FACTOR LARGE NUMBERS~🍿🍿🍿🍿🍿

89. David Terr says:

We've finally got a piece of the pie!

90. Sarainia Angelsong says:

I was not able to understand what this video was about or the maths lols? Any easier explanation than all this rambling that's way over my head lols haha wow tbh why numbers for encryption anyways? Capitals, Lowercase, Symbols, Numbers, etc. Is a good mix at 30 length times windows 64 bits I dunno but that seems like thousands to millions of bits long for a password so honestly I'm sticking to my super long passwords and soon windows 10 will be 128 bit system then 256 so tbh if we keep doubling every 2 years I think we astronomically out pace quantum anyday also I could double password to 60 length of random stuff if needed 😉

91. sodapopinski says:

problem is it will be like 20 years before we can generate enough q-bits to factor the 1000+ bit numbers. every bit added adds more noise too. it could be a long time before quantum computers are factoring crypto size numbers

92. fuzzy buzzy says:

314191=3,14191•(10•10•10•10•10)

93. Drvosjek Opasni says:

Am i too high for this video?

94. peti345 says:

| 0.978 LIKE > + | 0.022 DISLIKE >

95. selforganisation says:

This channel is like CGP Grey only math and physics and less history and political theory.

96. TheJoaveck says:

I need to… P