Here is an ancient saying. It is easier to destroy than to create.
Through mathematical instances of this too, like multiplying as compared to
antimuliplying. What is antimultiplying?
Okay. Normal people wouldn't talk about
antimultiplying. Right?
They talk about factoring. Here's an example.
So, suppose that 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, I mean, you know, you sort of play around with this and you can try
dividing 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, you just have to keep trying to divide, right?
So, to figure this out maybe I'd first see is 247 divisible by 3?
Well, our 3 goes into 247, 82 times, but there's a remainder of 1.
So, 82 times 3 isn't 247, I've got that pesky remainder.
Maybe I'll try 5. Does 5 go into 247?
Well, clearly not because the last digit's not a zero or a 5, right?
How many times does 5 go into this thing? I guess, 49 times and I get 245, and that
gives me a remainder of 2. Does 7 go into 247?
It'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 is a
remainder of 2. Does 11 go into this thing?
Does 11 go into 247? It goes into 22 times, but 22 times 11 is
242, which again leaves me with a remainder, in this case remainder of 5,
and then 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 anti-multiply 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 anti-multiply, I mean, factoring,
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 ask you to check that 19 times 13 is equal to
247, well that's super easy. Right?
I can do this multiplication problem. Like 9 times 3 is 27.
3 times 1, plus 2. 1 times 19, right, then 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, I mean 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.
You know, take a look at this number, 311,512,699.
I mean, it turns out, right, that this number is the product of two other whole
numbers, right? 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, you know, which numbers divide this number.
And since these 2 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, you know, do these two numbers multiply 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.
In that situation, a computer could just search for the factorization.
But, what if I gave you 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,
right, that I'm really who I say I am, right?
Because who else in the world knows the factorization of that enormous number?