Cracking open secure messages would be easy if only you knew how to factor huge numbers.

In this episode, we'll show you how with a twist.

6 00:00:18,850 --> 00:00:21,610 One of the main methods of cryptography, the encoding and decoding secure communications, uses really big prime numbers.

For a detailed description, check out some of the great videos we've linked to in the description, but for now, here's the distilled version.

It's pretty easy for a computer to find big prime numbers and multiply them together, but it's really hard for a computer to do the opposite-- find the prime factors of a really big number.

The prime factors of a number are all the prime numbers that evenly divide it.

Normally, RSA cryptography uses these prime factors like keys to decrypt messages.

So if you want to eavesdrop, you'll need to find one of these keys to hack in-- that is, you'll need to find the prime factors of a big number, and we're talking really big, as in hundreds of digits long.

Let's try a small example.

What are the prime factors of 35?

Well, they're 5 and 7.

How did you figure that out?

Probably just by looking at it, but even if you had forgotten that fact, you could have just checked all the prime numbers smaller than 35.

Does two divide it?

No.

Does 3?

No.

Does 5?

Yes.

And so on.

How boring.

And more importantly for a computer, how time consuming.

We'll need to do something more strategic to factor really big numbers.

Enter one of the great math heroes, Euler.

Along with many, many other things Euler thought a lot about prime numbers, relatively prime numbers, and modular arithmetic, which is basically all the math underlying RSA cryptography.

So it makes sense that we'd use similar math to break the algorithm.

Modular arithmetic is what happens when you count in a circle.

Counting modulo 5, or mod 5 for short, goes 0, 1, 2, 3 4, 0, 1, 2, 3 4, 0, 1, 2, and so on.

We just use the numbers less than 5 on repeat.

We tell time mod 12 or mod 24 depending on your convention.

This cyclical counting extends to the arithmetic operations.

So 1 plus 2 mod 5 is still just 3, but 2 plus 3 mod 5 is 0, and 2 times 3 is 1 mod 5.

Another way to think about modular asthmatic is in terms of the remainder when dividing numbers.

So here's a slightly more formal definition.

a is congruent to x mod n means that when we divide a by n the remainder is x.

So 2 times 3 is 6, but when we divide 6 by 5, the remainder is 1.

So 2 times 3 mod 5 is 1.

Euler noticed something about modular arithmetic and exponentiation.

Let's look at the powers of 3-- 3, 9, 27, 81, 243, and so on.

And let's look at them all mod 10.

It's easy to figure out what things are mod 10 because it's just the remainder when you divide by 10, which is the ones digit.

So mod 10 our sequence is 3, 9, 7, 1, 3, 9,7, 1, and so on.

Let's repeat the same experiment, but instead of looking at the powers of 3 mod 10, let's look at the powers of 2 mod 7.

The powers of 2 are 2, 4, 8, 16, 32, 64, and so on.

And mod 7 we get 2, 4, 1, 2, 4, 1, and so on.

What do you observe?

The sequence of powers just gets bigger and bigger, but the modular versions of the sequence cycle.

They repeat the same pattern over and over again, and the last digit of that pattern is always 1.

As long as x and n are relatively prime, meaning they share no prime factors, the sequence x mod N, x squared mod N, x cubed mod N, x to the fourth mod N, and so on will always have this property.

We call the length of the repeating pattern the period.

So the period of 3 mod 10 is 4, and the period of 2 mod 7 is 3.

Here's why the period is important.

If the period of x mod N is some number r, then r is the smallest number such that x to the r is congruent to 1 mod n. For example, 3 to the fourth is congruent to 1 mod 10, but 3 for the first, 3 squared, and 3 cubed are not 1 mod 10, but let's get back to our original goal.

What does all this stuff about modular arithmetic, exponentiation, and periods have to do with factoring large numbers?

Let's say I give you a number n. I tell you n equals p times q for two prime numbers p and q, but I don't tell you anything about those primes.

Your job is to find them.

Here's how you'll do it.

Step one-- pick any number smaller than n. Let's call the number you selected a.

Check to make sure that a and n are relatively prime by computing the greatest common divisor of a and n. The greatest common divisor of two numbers is the biggest integer that divides them both, so it's 1 if the two numbers are relatively prime.

The Euclidean algorithm is a quick and standard way to find the GCD of two numbers.

If they have a divisor in common, that's a factor of n, which is what you've been looking for, and you've saved yourself the rest of the steps.

Step two-- compute the period of a mod N. Let's call it r. For the sake of example, let's say you're trying to find the factors of 35.

So n equals 35, and you pick a equals 8 since it's relatively prime to 35.

Then with a little computation we can see that r equals 4.

To make all the arithmetic work out, we're going to need to divide r by 2.

So we need to know that r is even.

Later on, we'll also need to know that a to the r over 2 plus 1 is not congruent to 0 mod N. If either of these things fail, we need to pick a different a in step one.

Luckily, there's at least a 50% chance you'll pick a good value for a.

So on average, you won't have to try too many times.

For step three, we'll have to do some algebra.

Let's start with the fact we know.

a to the r is congruent to 1 mod N, which, subtracting 1, gives the a to the r minus 1 is congruent to 0 mod N. Saying that something is 0 mod N is the same as saying that it's a multiple of N. So there must exist some integer k such that a to the r minus 1 equals k times N. Since we assumed r is an even number, we can rewrite it as a to the r over 2 minus 1 times a to the r over 2 plus 1 equals kN.

And since N equals pq, we'll replace it with pq.

OK, that was kind of a lot of algebra.

I often find it easier to work through computations like that on my own instead of watching someone else do it.

You're welcome to pause here and check the steps.

Here's what happens with the example where we are trying to find the factors of 35.

Since the period of 8 mod 35 is 4, we have 8 to the fourth is congruent to 1 mod 35.

So 8 to the fourth minus 1 is congruent to 0 mod 35.

Actually, 8 to the fourth minus 1 is 4,095, but we only care about its value mod 35.

We could rewrite this as 8 to the fourth minus 1 equals k times 35 for some integer k. Again, we could solve for k in this case, but it's irrelevant, so I'll leave it as a variable.

Rewrite this as 8 squared minus 1 times 8 squared plus 1 equals k times p times q where p and q are the prime factors of 35 that we're searching for.

Step four is the grand finale.

I claim that the greatest common divisor of a to the r over 2 minus 1 and N is one of the prime factors.

Let's call it p, and the greatest common divisor of a to the r over 2 plus 1 and N is the other prime factor.

Let's call it q.

Why?

The equation a to the r over 2 minus 1 times a to the r over 2 plus 1 equals kpq means that p must divide one of the factors on the left and q must divide one of the factors on the left, but they cannot divide the same factor since that factor would be divisible by N. Why is neither factor divisible by N?

For one, we assumed a to the r over 2 plus 1 is not congruent to 0 mod N. For the other, we know r is the minimum value of x such that a to the x is congruent to 1 mod N. So a to the r over 2 minus 1 is not congruent to 0 mod N. Since p and q divide separate factors on the left side of the equation, we can assume p divides a to the r of 2 minus 1 and q divides a to the r over 2 plus 1.

So our formulas work.

Again, that part contains some weird algebra arguments.

Go ahead and pause to think about it or rewatch it.

So in our example, p is the greatest common divisor of 63 and 35, which is 7.

And q is the greatest common divisor of 65 and 35, which is 5, which fortunately is correct.

In summary, here's our steps.

Step one-- pick a less than N. Step two-- find the period of a mod N. Step three-- well, we don't need to do all of the algebra of step three every time since we know it works.

So instead, we'll use step three to check that r is even and a to the r over 2 plus 1 is not congruent to 0 mod N. If either of these things fail, we need to go back to step one and pick a new value of a.

Finally, step four-- let p equal the GCD of a to the r over 2 minus 1 and N. And let q equal the GCD of a to the r over 2 plus 1 and N. And you're done.

You've destroyed information security.

OK, but obviously there's a catch since RSA cryptography still works.

Here it is.

Step two, finding the period, takes a long time-- in fact, an exponentially long time.

That might make it seem like we haven't done a lot by constructing these four steps, but actually we did.

All the steps besides two are pretty fast.

Instead of looking for a needle in a haystack, we reduced the hard part to one step-- finding the period.

And-- here's the big twist-- period finding is precisely the kind of thing a quantum computer is good at, and on the next episode, we're going to dive into that.

The four steps we just reviewed are the outline of Shor's algorithm, and next time we'll finish up by learning how to use a quantum computer to dramatically speed up step two.

Then RSA cryptography and your bank statements will really be in trouble.

See you next time on "Infinite Series."

Hello, I want to address some of the comments on our episode about exchanging the digits of e and pi.

First, Joel David Hamkins, one of the mathematicians whose work is featured in the original episode, asked a follow up question.

He asked, what if we do not insist that the digits being swapped come from the same digit place?

So you can swap a digit from anywhere in e with a digit from anywhere in pi.

Well, in this case, you can make a rational number, and he proves that in a blog post, which is linked to in the comments.

All right, lots and lots of folks asked about combining the digits of e and pi algebraically instead of literally swapping their digits.

So can you add, subtract, multiply, divide the number e and the number pi to get a rational number?

There's a couple cool famous examples like e to the pi i plus 1 is equal to 0.

That's Euler's identity, and there's some really silly examples, like e times pi divided by e times pi is equal to 1, but there's also a lot of things we don't know about when you multiply and divide e and pi whether you get rational or irrational numbers.

Some of my favorite examples are these funny almost integers.

So for example, pi to the ninth divided by e to the eighth is really, really, really close to 10, but it's not.

It's not the number 10.

It just kind of looks like that if you do the computation out by hand.

Also, e to the sixth minus pi to the fifth minus pi to the fourth is really close to 0, but it's not 0.

It just kind of looks like it.

Finally, Reddles won the challenge t-shirt for a very complete answer to the question.

If e and pi differ at infinitely many digits, why is the list of numbers produced by swapping infinitely many of their digits uncountably long.

Here's the answer.

For each digit that is different between e and pi, you can either swap it or don't.

Therefore, we can label a given permutation by listing whether or not we swapped each digit.

If we use 0 to represent doing nothing and 1 to represent swapping the digit, then each one of these corresponds to a list and zeros and ones.

Now, they mentioned two proofs that this list of zeros and ones is uncountable.

The first is that it's in bijection with the interval 0, 1 written in binary, and the second is that you can use Cantor's diagonalization argument directly on it.

Great answer.

There were also a lot of other great answers-- way too many for me to acknowledge.

So thanks, guys.

They were fantastic.

See you next week.