Factoring and cryptography
Almost all modern cryptography relies on the fact that multiplying two large prime numbers is easy, but reversing that process, finding the original primes from their product, is computationally infeasible for even the most powerful classical computers. The public key in encryption is that large product; the private key is one of the primes, which lets its holder recover the other simply by dividing. This is why attackers cannot crack passwords mathematically and must instead trick users into revealing them directly.
- Grover's algorithm, developed by Lov Grover at Bell Labs in 1996, is mentioned as the second foundational quantum algorithm alongside Shor's, and is described as optimal.
Transcript
This chapter, from the episode video's captions · 278 words
1:53:14spends these days creating that he establishes a way to find prime factors of large products of primes. Why is that important? Because almost all of cryptography is dependent on large products of primes not being able to get factored efficiently even by a supercomput. >> Okay? If you take a giant prime number and you take a giant prime number, >> you get a even bigger number. >> And if you give that to somebody, they could not tell you what two prime numbers make up that product. Okay?
1:53:54Unless you give him one of them. You give him one of them, then you can just divide and I can get the other one. Right? This is how public key and private key encryption works. Public key is the giant big number. Private key is your own special prime number that you can figure out what the other one is based on just dividing and then you can you know this is how passwords work. Email passwords, your Instagram password. This is why like hackers need to like fool you by telling you that like you know your your grandma's in the hospital or something. Yeah. And they actually literally need you to type in your pass. They can't just like do it. >> Yeah. >> Right. >> This becomes a huge huge deal. >> Okay. Um in parallel I just want to also
1:54:34mention um in 1996 law of Grover who's actually he's an Indian um he develops Grover algorithm also at Bell Labs and this is another foundational quantum algorithm. It's the second big foundational quantum algorithm that people are excited about. Um it's optimal
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.