ToKCast cover image

Ep 194: David Deutsch’s ”The Fabric of Reality” Chapter 9 ”Quantum Computers” Part 4: Shor’s Algorithm

ToKCast

CHAPTER

How to Find Prime Factors of a Number

The problem of decomposing a number into its prime factors can be difficult. Even if you give this job to a computer it faces a similar challenge The same challenge, in fact It's much harder to search For the prime factors of some big number Than it is to multiply out numbers To get a bigger number. This fundamental fact of reality That finding factors is hard And exponentially harder For every single digit you add So 4 digits is exponentially a harder problem And finding the factors of a 3 digit number Is exponentially harder than 4 digits and so on and so forth Means the problem becomes Intractable In the technical sense that we've talked about in this chapter before.

00:00
Transcript
Play full episode

Remember Everything You Learn from Podcasts

Save insights instantly, chat with episodes, and build lasting knowledge - all powered by AI.
App store bannerPlay store banner