0:00

[MUSIC]

Here is an ancient saying, it is easier to destroy than to create.

Through mathematical instances of this too like multiplying

as compared to antimultiplying.

What is antimultiplying?

Normal people wouldn't talk about antimultiplying.

They'd talk about factoring.

Here's an example.

Suppose somebody gives you a number like 247 to antimultiply that number,

which is just my crazy way of saying factoring this number.

Means I want to write this as something times something else.

And yeah, you can sort of play around with this and try diving

this by various numbers, and you'll eventually hit on 247 being 13 times 19.

Well, that seemed to have come out of nowhere.

How did I figure that out?

Well, basically I just have to keep trying to divide, right?

So to figure this out, maybe I'd first see is 247 divisible by 3?

Well, 3 goes into 247 82 times, but there's a remainder of 1.

So 82 time three isn't 247, I've got that pesky remainder.

Maybe I'll try five, does five go into 247?

Well clearly not, because the last digit's not a zero or a five, right?

How many times does five go into this thing?

I guess 49 times, and I get 245 and that gives me a remainder of 2.

Does seven go into 247?

That's a lot harder to see if 7 divides this number.

7 goes into this thing 35 times but

35 times 7 is 245 so again there's a remainder of 2.

Does 11 go into this thing?

Does 11 go into 247?

It goes in there 22 times, but 22 times 11 is 242.

Which again leaves me with a remainder, in this case a remainder of 5.

And finally, I get to 13.

Does 13 go into 247?

Yes, 13 goes into this thing 19 times, right?

And that's exactly what I'm looking for.

But the easy way here to antimultiply, or

to factor, is just to try a bunch of stuff.

And hopefully,

you'll land on a product of numbers that multiplies to your given number.

Why is factoring so difficult?

Yeah, so what we just saw is that it was hard to factor 247.

It's hard to write this number as a product of two other numbers.

But if somebody comes up to you and asks you to check that 19 x 13 is equal to 247,

well that's super easy, right?

I can do this multiplication problem, right?

9 times 3 is 27, 3 times 1 plus 2,

1 times 19, right, and I add.

And yeah, I mean, I get 247, right?

So it's easy to verify if I'm told the answer that these numbers multiply to 247.

But it took some guessing, really, to figure out that 247 factored in this way.

Well this is an example where undoing an operation is much harder than just

performing that operation.

All right, here's a piece of paper.

It's very easy for me to rip the piece of paper.

It's harder for me to unrip the piece of paper.

And honestly, 247's not even that bad.

Take a look at this number, 311,512,699.

It turns out right that this number is the product of two other whole numbers.

It turns out this is 17,551 times 17,749,

but how would you ever have known that?

It would have been a real pain to do a bunch of tests

to see which numbers divide this number.

And since these two numbers are prime,

there's no other smaller numbers that go into this number evenly.

So it would have been a ton of work.

And yet, if somebody tells you, do these two numbers multiplied to this,

that is easy to verify, because you can just multiply these two numbers and

check that they really give you this number.

But undoing that multiplication, starting with this number and

trying to find these two numbers, would really be a pain.

Now, in that situation, a computer could just search for the factorization.

But what if I gave you a number that was much, much bigger?

Well, here's a 240 digit number that I've cooked up.

I got this number by taking two prime numbers and multiplying them together.

Probably I'm the only person on Earth who knows the factorization of that number.

I got that number by taking two big prime numbers and

multiplying them together, but nobody else but me knows what those prime numbers are.

For someone else to come along and

find those two factors would be really difficult.

The cool consequence is that if I were to reveal to you the factorization

of that large number, well that would be evidence that I'm really who I say I am.

Because who else in the world knows the factorization of that enormous number.