# Why Factoring Keeps Secrets: RSA Encryption

> Public-key cryptography rests on one lopsided fact: multiplying two large primes is instant, and taking the product apart again is not. This lecture builds RSA from that single asymmetry, for someone who can code but has never studied number theory. It opens on the pair it is walking toward — a public key and a private key — and then sets up modular arithmetic on a clock face, counts the numbers that share no factor with a modulus, and generates a real key pair from the primes sixty-one and fifty-three, with every number computed on screen: the modulus, the totient, the public exponent and the private exponent that undoes it. We encrypt the letter A by repeated squaring, decrypt it back, and then use Euler's theorem to show why the round trip has to return the original message. It closes on the security argument: the exact chain of dependencies an attacker faces, and how fast the cost of factoring runs away from anything a computer can do.

- Canonical watch page: [Why Factoring Keeps Secrets: RSA Encryption](https://academa.ai/lectures/rsa-factoring-encryption)
- Publisher: [Academa, Inc.](https://academa.ai)
- Subject: Mathematics
- Published: 2026-08-29T00:14:13.000Z
- Updated: 2026-08-29T00:14:13.000Z
- Duration: PT1076S (17 minutes 56 seconds)
- Chapters: 5
- Views: 0
- Language: en-US
- Access: Free
- Video stream: [HLS content](https://academa.ai/media/l/01M14TZEN8QZS78ZF9Q1DA2ECP/1/dark/master.m3u8)
- Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TZEN8QZS78ZF9Q1DA2ECP/1/semantic.json)
- Thumbnail: [Image](https://academa.ai/media/l/01M14TZEN8QZS78ZF9Q1DA2ECP/1/dark/poster.jpg)

## Description

Build RSA from scratch: modular arithmetic, key generation from two primes, and one message encrypted and decrypted by hand.

## Chapters

- [00:00–03:24.302 · A One-Way Street](https://academa.ai/lectures/rsa-factoring-encryption?t=0)
- [03:24.302–05:50.356 · Arithmetic That Wraps Around](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333)
- [05:50.356–09:36.521 · Building the Keys](https://academa.ai/lectures/rsa-factoring-encryption?t=350.35556249999996)
- [09:36.521–13:40.995 · Encrypting One Message](https://academa.ai/lectures/rsa-factoring-encryption?t=576.5207083333333)
- [13:40.995–17:56 · Why It Works, and Why It's Safe](https://academa.ai/lectures/rsa-factoring-encryption?t=820.9947500000001)

## Transcript

### [00:00 · A One-Way Street](https://academa.ai/lectures/rsa-factoring-encryption?t=0)

Here is a fact about arithmetic that almost nothing else in mathematics shares. Some calculations are easy to run forwards and brutally hard to run backwards. Very nearly all of the security on the internet is built on that one lopsided fact. Before we build anything, let me show you where we are going. By the end of this lecture you will have made these two things, and they are only numbers. This one you publish. You put it in a certificate, you hand it to strangers, you print it on a poster. And this one you never show anybody, ever. Anyone who learns it can read everything that was ever sent to you. So the whole lecture is really one question: how do you hand out the first number without giving away the second? So here is where the first of those numbers comes from. Two primes, sixty one and fifty three. Multiply them together and out comes the number you just saw. You can do that by hand in twenty seconds, and your processor does it in a single instruction. Now let me hand you the answer and take the question away. Here is that same number, and I am not telling you what I multiplied. Which two primes were they? You know for certain that they exist, and there is no formula anywhere that will hand them to you. The only honest method is to go looking. Try two: does it divide? No. Try three. No. Try five. No. And on up the small numbers, asking every one of them the same question. And you do not have to search forever. If a number has two factors, one of them is no bigger than its square root, and for this one that is a shade under fifty seven. So the search is bounded. Fifty odd questions, worst case. So let us run it. Two, three, five, seven, and onward, and there it stops, at fifty three. That divides our number exactly, and the partner is sixty one. We found it, but notice how we found it: by exhaustion, not by insight. Fifty odd questions is nothing at all. But watch what happens to that search when this number gets bigger, because that gap is the entire trick. Here is the comparison that matters. Down the left, how many digits the number has. In the middle, what it costs to multiply the two primes together. And on the right, what it costs to go looking for them. Four digits, which is our case: multiplying is instant, and the search is about sixty steps. Twenty digits: multiplying is still instant, and the search is ten billion steps, which is a couple of seconds on a laptop. Six hundred and seventeen digits, which is the size your bank actually uses. Multiplying two three hundred digit primes is still instant, a millisecond. The search is ten to the three hundred and eight steps. There are only about ten to the eighty atoms in the observable universe. You could give every atom in it its own computer, run them all since the big bang, and you would not be anywhere near finished. That gap is the whole of RSA. Everything else we do today is machinery for turning one lopsided piece of arithmetic into a lock. But before we can build the lock we need a second kind of arithmetic: the kind that wraps around.

### [03:24.302 · Arithmetic That Wraps Around](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333)

You already know this arithmetic. It is the percent operator in whatever language you happen to write in. But let me set it up properly, on a clock face, because it is the ground that everything else today stands on. Twelve positions, and after eleven you do not get twelve, you get zero all over again. The numbers wrap. So start at zero, at the top, and count seventeen steps forward. One, two, three, on round past eleven, back through zero, and keep going. Where do you finish? At five. And that is what congruence modulo twelve means. Two whole numbers are congruent when they leave the same remainder. Seventeen and five leave the same one here, so as far as this clock is concerned they are the same number. We write it with a three bar equals sign. Now here is the property that makes all of this practical. You may take the remainder whenever you like. Nineteen times seven. I do not need the product at all, because nineteen is already seven on this clock. So it is seven times seven, forty nine, which is one. Reduce early and reduce often, and the numbers never grow. That single habit is what lets a computer raise a six hundred digit number to a six hundred digit power without ever holding anything bigger than six hundred digits. Now let us raise something to a power on one of these clocks. Take three, and keep multiplying it by itself, on a clock with seven positions. Three to the one is three. Three squared is nine, which is two. Three cubed is twenty seven, which is six. Then eighty one, which is four. Then two hundred and forty three, which is five. Then seven hundred and twenty nine, which is one, and after that the whole thing repeats forever. Now look down that last column. Three, two, six, four, five, one. That is a scramble. There is no pattern you can eyeball, and here is the point: if I tell you the answer is five, and ask which power of three produced it, you are back to guessing. That problem has a name, the discrete logarithm, and nobody has a fast method for it either. So there are our two one way streets. Multiplying primes is easy and factoring is hard. Raising to a power on a clock is cheap and coming back is not.

### [05:50.356 · Building the Keys](https://academa.ai/lectures/rsa-factoring-encryption?t=350.35556249999996)

Right. Let us build an actual key. There is exactly one piece of number theory you need first, and it is a counting question. So let me do the counting on a number small enough to see all of at once: fifteen, which is three times five. Here is every whole number below it. Now cross out the ones that share a factor with fifteen. The multiples of three: three, six, nine, twelve. And the multiples of five: five, and ten. What is left? One, two, four, seven, eight, eleven, thirteen and fourteen. Eight numbers survive. Eight is two times four. And two is three minus one, four is five minus one. That is not a coincidence. For any product of two primes, the count comes out as p minus one, times q minus one. This count has a name and a symbol. It is Euler's totient function, written phi of n. Hold on to it, because it is the only genuinely new symbol in this lecture. Now the real thing. I pick two primes: sixty one and fifty three. Real RSA picks primes with about three hundred digits each, by generating random odd numbers and testing them, which is fast. The arithmetic is identical. I just want numbers you can check by hand. Multiply them. That is n, and it is the modulus: the size of the clock that everything from here on happens on. You have seen it twice already today. Now compute phi of n from the two primes. Sixty times fifty two, which is this number here. And notice that you could only do that because you know p and q. From n on its own, computing phi is exactly as hard as factoring. Last, pick a public exponent, e. The one requirement is that it shares no factor with phi of n. Seventeen will do nicely: it is prime, and it does not divide the totient. In production, e is almost always one particular number, two to the sixteen plus one. Nothing deep is going on there. That exponent is simply quick to raise things to. And that is the public key: the pair n and e. You publish it. You put it in your certificate, you hand it to strangers, you print it on a poster. It is exactly the pair I showed you in the first minute. The private key is one more number, d, and it is fixed by a single condition: e times d has to be congruent to one, modulo phi of n. Unpack that. It says seventeen d is one more than some whole multiple of phi of n. So go and look for the multiple. Take k equals one. That gives three thousand one hundred and twenty one, and seventeen does not divide it. Bump k to two: six thousand two hundred and forty one, and again no. Bump it once more, and still no. Keep going, and at k equals fifteen you get this one. And that is seventeen times two thousand seven hundred and fifty three, exactly. So there is d. You would never do it that way in code. The extended Euclidean algorithm produces d in a few dozen steps, for numbers of any size at all. But that is what d is: the number that undoes seventeen, on a clock of size phi of n. So there is the pair. The public key is n and e, and anybody may have it. The private key is d, and every step that produced it leaned on this number here, which came from the two primes. They are the whole secret.

### [09:36.521 · Encrypting One Message](https://academa.ai/lectures/rsa-factoring-encryption?t=576.5207083333333)

All right. Your public key is out in the world, and I want to send you a message. The message is the letter A. My computer stores A as the number sixty five, so my message, as a number, is sixty five. Encryption is one line of arithmetic. The ciphertext c is the message raised to the public exponent e, modulo n. That is the entire operation. There is exactly one rule about the message: as a number it has to be smaller than n. Sixty five is comfortably smaller than our modulus, so we are fine. A real message gets chopped into blocks that each fit. So here is our case: sixty five, to the seventeenth, on a clock of that size. Now that power is a thirty one digit number. We are never going to write it down, and we do not have to, because of the habit from earlier: reduce at every step. Watch. Square sixty five: four thousand two hundred and twenty five, which on our clock is nine hundred and ninety two. Square that, reduce it again, and you get one thousand two hundred and thirty two, which is sixty five to the fourth. Square again and you have the eighth power: one thousand five hundred and forty seven. Once more and you have the sixteenth: seven hundred and eighty nine. Four squarings so far, and we have climbed all the way to sixteen. And seventeen is sixteen plus one. So one final multiplication by sixty five. Seven hundred and eighty nine times sixty five is fifty one thousand two hundred and eighty five, and on our clock that lands here. Four squarings and one multiplication. Not seventeen multiplications. And for a real two thousand bit exponent it is about three thousand steps. That is why your browser does this without you ever noticing. Let me lay out the whole range, from zero up to n. Here is the message, down at sixty five. And here is the ciphertext, way over there. Now look at the neighbours. Sixty four encrypts to fifteen seventy seven. Sixty six encrypts to five hundred and twenty four. Three consecutive messages, three ciphertexts flung all over the range. There is nothing to read off and nothing to interpolate between. That scatter is the point. Encryption here is not a shuffle or a substitution you could work backwards from by staring at it. It is one modular power, and it throws the message somewhere unpredictable inside the range. Now your side of it. The ciphertext is twenty-seven ninety, the private exponent is twenty-seven fifty-three, and the number we want back is sixty-five. Those are the numbers in front of us. Now write the relationship. The message m is c to the d, modulo n. For our ciphertext and private exponent, that is twenty-seven ninety to the twenty-seven fifty-three, modulo thirty-two thirty-three. In principle that is astronomically large, and again we never build it. Same trick. Two thousand seven hundred and fifty three is a sum of five powers of two: two thousand and forty eight, plus five hundred and twelve, plus one hundred and twenty eight, plus sixty four, plus one. So it is eleven squarings and four multiplications, and that is the whole cost. Do it, and out comes sixty five. The letter A. Exactly the message I sent, not close to it: exactly it, every single time. And there is the loop. Raise to e to lock it, raise to d to unlock it. The only thing separating you from everybody else watching the wire is that you know d. Which leaves the two questions we have been circling all lecture. Why does the message come back at all? And why can nobody else bring it back?

### [13:40.995 · Why It Works, and Why It's Safe](https://academa.ai/lectures/rsa-factoring-encryption?t=820.9947500000001)

So why did the message come back? Raise the ciphertext to d, and out drops exactly the number I started with. Not close to it. That is not luck, and it is not a property of the numbers I happened to pick. It is one theorem. Euler's theorem. If m shares no factor with n, then m raised to phi of n is one, modulo n. Not nearly one. Exactly one. Raise almost anything to that one particular power, on that one particular clock, and you land on one. Now watch what decryption actually is. c to the d is m to the e, all raised to the d, which is simply m to the e times d. So what is e times d? Seventeen times two thousand seven hundred and fifty three, which is this number. But we chose d precisely so that this product would be one more than a multiple of phi of n. And there it is: fifteen lots of the totient, plus one. So m to the e d is m to the fifteen times the totient, times one more m. Which I can regroup: m to the totient, all raised to the fifteenth, times m. And that bracket is Euler's theorem staring back at us. It is one. One to the fifteenth is one. So the whole expression collapses to m, every time, for every message under the sun. Decryption is not a lucky inverse. It is a theorem. Right. Now the other half. Why can nobody else do that? Put yourself on the outside: you have n, you have e, and you have the ciphertext going past on the wire. That is everything. What do you actually need? You need d. That is the only exponent that undoes seventeen on this particular clock, and without it the ciphertext is just a number. To compute d you need phi of n, because d was defined by that congruence: e d is one, modulo phi of n. No phi, no d. To compute phi of n you need p and q, because phi of n is p minus one times q minus one. There is no other route to it. Knowing n is not enough. And to get p and q out of n, you have to factor n. That is the last link, and every link in the chain is forced. There is no way in from the side. So how hard is factoring, really? Here is trial division again, plotted against the number of digits. Four digits, about a hundred steps. Eight digits, ten thousand. Twelve digits, a million, and the curve has already left the top of the board. Now imagine putting six hundred and seventeen digits on that axis. This curve was off the board at twelve. Out there, trial division needs the number we met in the first minute, the one bigger than the atoms in the universe. The best method anybody knows does enormously better, and it is still nowhere near enough. And notice the flip side of all this. My key is a toy. Its modulus has a factor under sixty, and you could break it on paper over a cup of coffee. That is not a flaw in RSA. It is the entire reason the real numbers have to be enormous. So that is RSA, complete. Encrypt by raising the message to e. Decrypt by raising the ciphertext to d. Both modulo n, and both cheap. The public key hands out n, and n is the product of two primes that it will not give up. One honest footnote before you go and implement this, because you should not implement this. What I have shown you is textbook RSA. Every real library pads the message with structured randomness before encrypting, because raw RSA has an obvious hole: the same message always produces the same ciphertext. The mathematics is exactly what you have just watched. The padding is what makes it safe to hand to strangers. And the wall the whole thing leans on has not changed since the first minute of this lecture. Multiplying is easy. Going the other way is not.

## About Academa, Inc.

Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need.

## Complete audiovisual record

Immutable source: [semantic.json](https://academa.ai/media/l/01M14TZEN8QZS78ZF9Q1DA2ECP/1/semantic.json)

Record version: 1. Render attempt: 1.

### How to read this timeline

Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video.

### Scene 1: [A One-Way Street](https://academa.ai/lectures/rsa-factoring-encryption?t=0)

Span: 00:00–03:24.302 (0s–204.3022708333333s).

#### Objects

- bound: a Line \[green\] labelled "sqrt(3233)" drawn in line (start=(56.86, -0.25), end=(56.86, 0.25))
- card: a Title that says "Cryptography for Programmers — Why Factoring Keeps Secrets: RSA Encryption"
- divisor: a VariableNumber (initial\_value=2.0, format\_spec='.0f')
- fact: a Math \[text\] that says "$3233 = p times q$"
- heading: a Heading that says "Easy One Way, Hard the Other"
- heading0: a Heading that says "The Two Numbers We Are Going to Build"
- heading2: a Heading that says "What Happens When the Number Grows"
- line: a NumberLine labelled "d" (x\_range=(0, 60), include\_numbers=True, ticks\_every=10)
- mult: a Math \[text\] that says "$61 times 53 = 3233$"
- private\_key: a Math \[text\] that says "$d = 2753$"
- private\_label: a Tex \[text\] that says "The private key"
- private\_note: a Text \[text\] that says "Nobody may."
- probe: a Point \[yellow\] labelled "2" drawn in line (location=(\<VariableNumber divisor = 53.0\>, 0.0))
- public\_key: a Math \[text\] that says "$(n, e) = (3233, 17)$"
- public\_label: a Tex \[text\] that says "The public key"
- public\_note: a Text \[text\] that says "Anyone may have it."
- punch: a Tex \[text\] that says "There are about $10^(80)$ atoms in the observable universe."
- scale: a Table \[text\] that says "Digits in $n$ Cost to multiply Cost to search for a factor 4 instant about 60 steps 20 instant about $10^(10)$ steps 617 instant about $10^(308)$ steps" (rows=(('Digits in $n$', 'Cost to multiply', 'Cost to search for a fa…, header=True)

#### Beats

##### [00:00](https://academa.ai/lectures/rsa-factoring-encryption?t=0)

Narration: Here is a fact about arithmetic that almost nothing else in mathematics shares. Some calculations are easy to run forwards and brutally hard to run backwards. Very nearly all of the security on the internet is built on that one lopsided fact.

Board: Empty.

Actions:
- [00:00](https://academa.ai/lectures/rsa-factoring-encryption?t=0): card is shown on the screen, written out.
- [00:1.5](https://academa.ai/lectures/rsa-factoring-encryption?t=1.5): card: enter:write-left-to-right.
- [00:14.896](https://academa.ai/lectures/rsa-factoring-encryption?t=14.8955): card is hidden from the screen — left the board.

##### [00:16.096](https://academa.ai/lectures/rsa-factoring-encryption?t=16.0955)

Narration: Before we build anything, let me show you where we are going. By the end of this lecture you will have made these two things, and they are only numbers. This one you publish. You put it in a certificate, you hand it to strangers, you print it on a poster.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [00:16.096](https://academa.ai/lectures/rsa-factoring-encryption?t=16.0955): heading0 is shown on the screen, written out.
- [00:18.998](https://academa.ai/lectures/rsa-factoring-encryption?t=18.997999999999998): public\_label is shown on the screen, written out.
- [00:20.217](https://academa.ai/lectures/rsa-factoring-encryption?t=20.217): public\_key is shown on the screen, written out.
- [00:25.244](https://academa.ai/lectures/rsa-factoring-encryption?t=25.244): public\_key is emphasized.
- [00:28.193](https://academa.ai/lectures/rsa-factoring-encryption?t=28.192999999999998): public\_note is shown on the screen, written out.

##### [00:30.761](https://academa.ai/lectures/rsa-factoring-encryption?t=30.7605)

Narration: And this one you never show anybody, ever. Anyone who learns it can read everything that was ever sent to you. So the whole lecture is really one question: how do you hand out the first number without giving away the second?

Board: public\_label — a Tex \[text\] that says "The public key"; public\_key — a Math \[text\] that says "$(n, e) = (3233, 17)$"; public\_note — a Text \[text\] that says "Anyone may have it."; heading0 — a Heading that says "The Two Numbers We Are Going to Build"

Actions:
- [00:30.761](https://academa.ai/lectures/rsa-factoring-encryption?t=30.7605): private\_label is shown on the screen, written out.
- [00:30.761](https://academa.ai/lectures/rsa-factoring-encryption?t=30.7605): public\_key is no longer emphasized.
- [00:31.126](https://academa.ai/lectures/rsa-factoring-encryption?t=31.126): private\_key is shown on the screen, written out.
- [00:31.695](https://academa.ai/lectures/rsa-factoring-encryption?t=31.695): private\_key is emphasized.
- [00:32.845](https://academa.ai/lectures/rsa-factoring-encryption?t=32.845): private\_note is shown on the screen, written out.
- [00:38.975](https://academa.ai/lectures/rsa-factoring-encryption?t=38.974999999999994): private\_key is no longer emphasized.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): heading0 is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): private\_key is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): private\_label is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): private\_note is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): public\_key is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): public\_label is hidden from the screen — left the board.
- [00:43.804](https://academa.ai/lectures/rsa-factoring-encryption?t=43.804): public\_note is hidden from the screen — left the board.

##### [00:45.004](https://academa.ai/lectures/rsa-factoring-encryption?t=45.004)

Narration: So here is where the first of those numbers comes from. Two primes, sixty one and fifty three. Multiply them together and out comes the number you just saw. You can do that by hand in twenty seconds, and your processor does it in a single instruction.

Board: Empty.

Actions:
- [00:45.004](https://academa.ai/lectures/rsa-factoring-encryption?t=45.004): heading is shown on the screen, written out.
- [00:52.179](https://academa.ai/lectures/rsa-factoring-encryption?t=52.179): mult is shown on the screen, written out.
- [00:54.617](https://academa.ai/lectures/rsa-factoring-encryption?t=54.617): mult (the "3233" part) is emphasized.

##### [01:1.3](https://academa.ai/lectures/rsa-factoring-encryption?t=61.3005)

Narration: Now let me hand you the answer and take the question away. Here is that same number, and I am not telling you what I multiplied. Which two primes were they? You know for certain that they exist, and there is no formula anywhere that will hand them to you.

Board: mult — a Math \[text\] that says "$61 times 53 = 3233$"; heading — a Heading that says "Easy One Way, Hard the Other"

Actions:
- [01:1.3](https://academa.ai/lectures/rsa-factoring-encryption?t=61.3005): mult (the "3233" part) is no longer emphasized.
- [01:4.888](https://academa.ai/lectures/rsa-factoring-encryption?t=64.888): fact is shown on the screen, written out.
- [01:9.799](https://academa.ai/lectures/rsa-factoring-encryption?t=69.799): fact (the "p times q" part) is emphasized.

##### [01:17.481](https://academa.ai/lectures/rsa-factoring-encryption?t=77.4815)

Narration: The only honest method is to go looking. Try two: does it divide? No. Try three. No. Try five. No. And on up the small numbers, asking every one of them the same question.

Board: mult — a Math \[text\] that says "$61 times 53 = 3233$"; fact — a Math \[text\] that says "$3233 = p times q$"; heading — a Heading that says "Easy One Way, Hard the Other"

Actions:
- [01:17.481](https://academa.ai/lectures/rsa-factoring-encryption?t=77.4815): line is shown on the screen, written out.
- [01:17.481](https://academa.ai/lectures/rsa-factoring-encryption?t=77.4815): fact (the "p times q" part) is no longer emphasized.
- [01:20.442](https://academa.ai/lectures/rsa-factoring-encryption?t=80.44200000000001): probe is shown on the screen, written out.
- [01:24.064](https://academa.ai/lectures/rsa-factoring-encryption?t=84.06400000000001): probe is redrawn as the numbers it depends on change.
- [01:24.064](https://academa.ai/lectures/rsa-factoring-encryption?t=84.06400000000001): divisor ticks to 3.0.
- [01:26.7](https://academa.ai/lectures/rsa-factoring-encryption?t=86.7): probe is redrawn as the numbers it depends on change.
- [01:26.7](https://academa.ai/lectures/rsa-factoring-encryption?t=86.7): divisor ticks to 5.0.

##### [01:33.935](https://academa.ai/lectures/rsa-factoring-encryption?t=93.935)

Narration: And you do not have to search forever. If a number has two factors, one of them is no bigger than its square root, and for this one that is a shade under fifty seven. So the search is bounded. Fifty odd questions, worst case.

Board: mult — a Math \[text\] that says "$61 times 53 = 3233$"; fact — a Math \[text\] that says "$3233 = p times q$"; line — a NumberLine labelled "d" (x\_range=(0, 60), include\_numbers=True, ticks\_every=10); heading — a Heading that says "Easy One Way, Hard the Other"; probe — a Point \[yellow\] labelled "2" drawn in line (location=(\<VariableNumber divisor = 53.0\>, 0.0))

Actions:
- [01:39.583](https://academa.ai/lectures/rsa-factoring-encryption?t=99.583): bound is shown on the screen, written out.
- [01:43.902](https://academa.ai/lectures/rsa-factoring-encryption?t=103.902): The segment (0.0, 0.0) to (56.86, 0.0) in line is lit up.

##### [01:47.689](https://academa.ai/lectures/rsa-factoring-encryption?t=107.6885)

Narration: So let us run it. Two, three, five, seven, and onward, and there it stops, at fifty three. That divides our number exactly, and the partner is sixty one. We found it, but notice how we found it: by exhaustion, not by insight.

Board: mult — a Math \[text\] that says "$61 times 53 = 3233$"; fact — a Math \[text\] that says "$3233 = p times q$"; line — a NumberLine labelled "d" (x\_range=(0, 60), include\_numbers=True, ticks\_every=10); heading — a Heading that says "Easy One Way, Hard the Other"; probe — a Point \[yellow\] labelled "2" drawn in line (location=(\<VariableNumber divisor = 53.0\>, 0.0)); bound — a Line \[green\] labelled "sqrt(3233)" drawn in line (start=(56.86, -0.25), end=(56.86, 0.25))

Actions:
- [01:48.345](https://academa.ai/lectures/rsa-factoring-encryption?t=108.345): probe is redrawn as the numbers it depends on change.
- [01:48.345](https://academa.ai/lectures/rsa-factoring-encryption?t=108.345): divisor ticks to 53.0.
- [01:55.125](https://academa.ai/lectures/rsa-factoring-encryption?t=115.125): line: retire a lit segment (unemphasize\_line).
- [01:57.099](https://academa.ai/lectures/rsa-factoring-encryption?t=117.099): fact becomes "$3233 = 53 times 61$".
- [01:59.514](https://academa.ai/lectures/rsa-factoring-encryption?t=119.51400000000001): fact (the "53 times 61" part) is emphasized.
- [02:3.054](https://academa.ai/lectures/rsa-factoring-encryption?t=123.054): fact (the "53 times 61" part) is no longer emphasized.

##### [02:4.699](https://academa.ai/lectures/rsa-factoring-encryption?t=124.69900000000001)

Narration: Fifty odd questions is nothing at all. But watch what happens to that search when this number gets bigger, because that gap is the entire trick.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:10.26](https://academa.ai/lectures/rsa-factoring-encryption?t=130.26000000000002): mult (the "3233" part) is emphasized.
- [02:12.977](https://academa.ai/lectures/rsa-factoring-encryption?t=132.97700000000003): mult (the "3233" part) is no longer emphasized.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): fact is hidden from the screen — left the board.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): heading is hidden from the screen — left the board.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): line is hidden from the screen — left the board.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): probe is hidden from the screen — line left the board.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): bound is hidden from the screen — line left the board.
- [02:13.848](https://academa.ai/lectures/rsa-factoring-encryption?t=133.84750000000003): mult is hidden from the screen — left the board.

##### [02:15.048](https://academa.ai/lectures/rsa-factoring-encryption?t=135.0475)

Narration: Here is the comparison that matters. Down the left, how many digits the number has. In the middle, what it costs to multiply the two primes together. And on the right, what it costs to go looking for them.

Board: Empty.

Actions:
- [02:15.048](https://academa.ai/lectures/rsa-factoring-encryption?t=135.0475): heading2 is shown on the screen, written out.
- [02:15.976](https://academa.ai/lectures/rsa-factoring-encryption?t=135.97600000000003): scale is shown on the screen, written out.
- [02:18.252](https://academa.ai/lectures/rsa-factoring-encryption?t=138.252): scale (the "Digits in $n$" part) is emphasized.
- [02:21.468](https://academa.ai/lectures/rsa-factoring-encryption?t=141.46800000000002): scale (the "Cost to multiply" part) is emphasized.
- [02:21.468](https://academa.ai/lectures/rsa-factoring-encryption?t=141.46800000000002): scale (the "Digits in $n$" part) is no longer emphasized.
- [02:25.554](https://academa.ai/lectures/rsa-factoring-encryption?t=145.554): scale (the "Cost to multiply" part) is no longer emphasized.
- [02:25.554](https://academa.ai/lectures/rsa-factoring-encryption?t=145.554): scale (the "Cost to search for a factor" part) is emphasized.

##### [02:29.011](https://academa.ai/lectures/rsa-factoring-encryption?t=149.0105)

Narration: Four digits, which is our case: multiplying is instant, and the search is about sixty steps. Twenty digits: multiplying is still instant, and the search is ten billion steps, which is a couple of seconds on a laptop.

Board: heading2 — a Heading that says "What Happens When the Number Grows"

Actions:
- [02:29.011](https://academa.ai/lectures/rsa-factoring-encryption?t=149.0105): scale (the "Cost to search for a factor" part) is no longer emphasized.
- [02:29.568](https://academa.ai/lectures/rsa-factoring-encryption?t=149.568): scale is shown on the screen, written out.
- [02:34.641](https://academa.ai/lectures/rsa-factoring-encryption?t=154.641): scale (the "about 60 steps" part) is emphasized.
- [02:36.557](https://academa.ai/lectures/rsa-factoring-encryption?t=156.557): scale is shown on the screen, written out.
- [02:40.713](https://academa.ai/lectures/rsa-factoring-encryption?t=160.713): scale (the "about $10^(10)$ steps" part) is emphasized.
- [02:40.713](https://academa.ai/lectures/rsa-factoring-encryption?t=160.713): scale (the "about 60 steps" part) is no longer emphasized.

##### [02:44.424](https://academa.ai/lectures/rsa-factoring-encryption?t=164.4245)

Narration: Six hundred and seventeen digits, which is the size your bank actually uses. Multiplying two three hundred digit primes is still instant, a millisecond. The search is ten to the three hundred and eight steps.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:44.773](https://academa.ai/lectures/rsa-factoring-encryption?t=164.773): scale is shown on the screen, written out.
- [02:56.418](https://academa.ai/lectures/rsa-factoring-encryption?t=176.41799999999998): scale (the "about $10^(10)$ steps" part) is no longer emphasized.
- [02:56.418](https://academa.ai/lectures/rsa-factoring-encryption?t=176.41799999999998): scale (the "about $10^(308)$ steps" part) is emphasized.

##### [02:57.854](https://academa.ai/lectures/rsa-factoring-encryption?t=177.85399999999998)

Narration: There are only about ten to the eighty atoms in the observable universe. You could give every atom in it its own computer, run them all since the big bang, and you would not be anywhere near finished.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:0.095](https://academa.ai/lectures/rsa-factoring-encryption?t=180.09499999999994): punch is shown on the screen, written out.
- [03:8.35](https://academa.ai/lectures/rsa-factoring-encryption?t=188.34999999999997): scale (the "about $10^(308)$ steps" part) is no longer emphasized.

##### [03:9.808](https://academa.ai/lectures/rsa-factoring-encryption?t=189.80849999999998)

Narration: That gap is the whole of RSA. Everything else we do today is machinery for turning one lopsided piece of arithmetic into a lock. But before we can build the lock we need a second kind of arithmetic: the kind that wraps around.

Board: punch — a Tex \[text\] that says "There are about $10^(80)$ atoms in the observable universe."; heading2 — a Heading that says "What Happens When the Number Grows"

Actions:
- [03:15.207](https://academa.ai/lectures/rsa-factoring-encryption?t=195.207): scale (the "617" part) is indicated — a transient flash.
- [03:23.261](https://academa.ai/lectures/rsa-factoring-encryption?t=203.26060416666664): heading2 is hidden from the screen — left the board.
- [03:23.261](https://academa.ai/lectures/rsa-factoring-encryption?t=203.26060416666664): punch is hidden from the screen — left the board.
- [03:23.261](https://academa.ai/lectures/rsa-factoring-encryption?t=203.26060416666664): scale is hidden from the screen — left the board.

### Scene 2: [Arithmetic That Wraps Around](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333)

Span: 03:24.302–05:50.356 (204.3022708333333s–350.35556249999996s).

#### Objects

- ang: a VariableNumber (initial\_value=90.0)
- backward: a Tex \[text\] that says "Backwards: given the remainder, get $k$. Nobody knows how."
- clockface: a Figure (x\_range=(-1.7, 1.7), y\_range=(-1.7, 1.7), aspect=(1, 1))
- defn: a Panel that says "Two whole numbers are congruent modulo $n$ when they leave the same remainder on division by $n$. Everything from here on happens on a clock with $n$ positions."
- dial: a Circle \[gray\] drawn in clockface (radius=1.2)
- forward: a Tex \[text\] that says "Forwards: given $k$, get the remainder. Easy."
- heading: a Heading that says "Arithmetic That Wraps Around"
- heading2: a Heading that says "Powers on a Clock"
- hours: a Point \[text\] labelled "0" drawn in clockface (location=(7.347880794884119e-17, 1.2))
- hours\_10: a Point \[text\] labelled "9" drawn in clockface (location=(-1.2, -1.4695761589768238e-16))
- hours\_11: a Point \[text\] labelled "10" drawn in clockface (location=(-1.0392304845413263, 0.6000000000000001))
- hours\_12: a Point \[text\] labelled "11" drawn in clockface (location=(-0.6000000000000005, 1.039230484541326))
- hours\_2: a Point \[text\] labelled "1" drawn in clockface (location=(0.6000000000000001, 1.0392304845413263))
- hours\_3: a Point \[text\] labelled "2" drawn in clockface (location=(1.0392304845413265, 0.5999999999999999))
- hours\_4: a Point \[text\] labelled "3" drawn in clockface (location=(1.2, 0.0))
- hours\_5: a Point \[text\] labelled "4" drawn in clockface (location=(1.0392304845413265, -0.5999999999999999))
- hours\_6: a Point \[text\] labelled "5" drawn in clockface (location=(0.6000000000000001, -1.0392304845413263))
- hours\_7: a Point \[text\] labelled "6" drawn in clockface (location=(7.347880794884119e-17, -1.2))
- hours\_8: a Point \[text\] labelled "7" drawn in clockface (location=(-0.5999999999999998, -1.0392304845413265))
- hours\_9: a Point \[text\] labelled "8" drawn in clockface (location=(-1.0392304845413265, -0.5999999999999999))
- powers: a Table \[text\] that says "$k$ $3^k$ remainder mod 7 1 3 3 2 9 2 3 27 6 4 81 4 5 243 5 6 729 1" (rows=(('$k$', '$3^k$', 'remainder mod 7'), ('1', '3', '3'), ('2', '9…, header=True)
- reduce\_rule: a Math \[text\] that says "$19 times 7 equiv 7 times 7 equiv 49 equiv 1 quad (upright("mod") 12)$"
- walker: a Point \[red\] drawn in clockface (location=((0.0 + (1.2 \* cos((ang \* 0.017453292519943295)))), (0.0 + (1.2…, marker\_radius=0.1)
- wrap: a Math \[text\] that says "$17 equiv 5 quad (upright("mod") 12)$"

#### Beats

##### [03:24.302](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333)

Narration: You already know this arithmetic. It is the percent operator in whatever language you happen to write in. But let me set it up properly, on a clock face, because it is the ground that everything else today stands on.

Board: Empty.

Actions:
- [03:24.302](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333): heading is shown on the screen, written out.
- [03:24.302](https://academa.ai/lectures/rsa-factoring-encryption?t=204.3022708333333): clockface is shown on the screen, written out.
- [03:31.883](https://academa.ai/lectures/rsa-factoring-encryption?t=211.88327083333328): dial is shown on the screen, written out.

##### [03:36.733](https://academa.ai/lectures/rsa-factoring-encryption?t=216.7327708333333)

Narration: Twelve positions, and after eleven you do not get twelve, you get zero all over again. The numbers wrap.

Board: clockface — a Figure (x\_range=(-1.7, 1.7), y\_range=(-1.7, 1.7), aspect=(1, 1)); heading — a Heading that says "Arithmetic That Wraps Around"; dial — a Circle \[gray\] drawn in clockface (radius=1.2)

Actions:
- [03:37.417](https://academa.ai/lectures/rsa-factoring-encryption?t=217.4172708333333): hours is shown on the screen, written out.
- [03:37.487](https://academa.ai/lectures/rsa-factoring-encryption?t=217.4872708333333): hours\_2 is shown on the screen, written out.
- [03:37.557](https://academa.ai/lectures/rsa-factoring-encryption?t=217.5572708333333): hours\_3 is shown on the screen, written out.
- [03:37.627](https://academa.ai/lectures/rsa-factoring-encryption?t=217.62727083333328): hours\_4 is shown on the screen, written out.
- [03:37.697](https://academa.ai/lectures/rsa-factoring-encryption?t=217.6972708333333): hours\_5 is shown on the screen, written out.
- [03:37.767](https://academa.ai/lectures/rsa-factoring-encryption?t=217.7672708333333): hours\_6 is shown on the screen, written out.
- [03:37.837](https://academa.ai/lectures/rsa-factoring-encryption?t=217.8372708333333): hours\_7 is shown on the screen, written out.
- [03:37.907](https://academa.ai/lectures/rsa-factoring-encryption?t=217.90727083333329): hours\_8 is shown on the screen, written out.
- [03:37.977](https://academa.ai/lectures/rsa-factoring-encryption?t=217.9772708333333): hours\_9 is shown on the screen, written out.
- [03:38.047](https://academa.ai/lectures/rsa-factoring-encryption?t=218.0472708333333): hours\_10 is shown on the screen, written out.
- [03:38.117](https://academa.ai/lectures/rsa-factoring-encryption?t=218.1172708333333): hours\_11 is shown on the screen, written out.
- [03:38.187](https://academa.ai/lectures/rsa-factoring-encryption?t=218.1872708333333): hours\_12 is shown on the screen, written out.
- [03:42.944](https://academa.ai/lectures/rsa-factoring-encryption?t=222.9442708333333): walker is shown on the screen, written out.

##### [03:44.148](https://academa.ai/lectures/rsa-factoring-encryption?t=224.1477708333333)

Narration: So start at zero, at the top, and count seventeen steps forward. One, two, three, on round past eleven, back through zero, and keep going. Where do you finish? At five.

Board: clockface — a Figure (x\_range=(-1.7, 1.7), y\_range=(-1.7, 1.7), aspect=(1, 1)); heading — a Heading that says "Arithmetic That Wraps Around"; dial — a Circle \[gray\] drawn in clockface (radius=1.2); hours — a Point \[text\] labelled "0" drawn in clockface (location=(7.347880794884119e-17, 1.2)); hours\_2 — a Point \[text\] labelled "1" drawn in clockface (location=(0.6000000000000001, 1.0392304845413263)); hours\_3 — a Point \[text\] labelled "2" drawn in clockface (location=(1.0392304845413265, 0.5999999999999999)); hours\_4 — a Point \[text\] labelled "3" drawn in clockface (location=(1.2, 0.0)); hours\_5 — a Point \[text\] labelled "4" drawn in clockface (location=(1.0392304845413265, -0.5999999999999999)); hours\_6 — a Point \[text\] labelled "5" drawn in clockface (location=(0.6000000000000001, -1.0392304845413263)); hours\_7 — a Point \[text\] labelled "6" drawn in clockface (location=(7.347880794884119e-17, -1.2)); hours\_8 — a Point \[text\] labelled "7" drawn in clockface (location=(-0.5999999999999998, -1.0392304845413265)); hours\_9 — a Point \[text\] labelled "8" drawn in clockface (location=(-1.0392304845413265, -0.5999999999999999)); hours\_10 — a Point \[text\] labelled "9" drawn in clockface (location=(-1.2, -1.4695761589768238e-16)); hours\_11 — a Point \[text\] labelled "10" drawn in clockface (location=(-1.0392304845413263, 0.6000000000000001)); hours\_12 — a Point \[text\] labelled "11" drawn in clockface (location=(-0.6000000000000005, 1.039230484541326)); walker — a Point \[red\] drawn in clockface (location=((0.0 + (1.2 \* cos((ang \* 0.017453292519943295)))), (0.0 + (1.2…, marker\_radius=0.1)

Actions:
- [03:46.62](https://academa.ai/lectures/rsa-factoring-encryption?t=226.6202708333333): walker is redrawn as the numbers it depends on change.
- [03:46.62](https://academa.ai/lectures/rsa-factoring-encryption?t=226.6202708333333): ang ticks to -420.0.

##### [03:58.342](https://academa.ai/lectures/rsa-factoring-encryption?t=238.3422708333333)

Narration: And that is what congruence modulo twelve means. Two whole numbers are congruent when they leave the same remainder. Seventeen and five leave the same one here, so as far as this clock is concerned they are the same number. We write it with a three bar equals sign.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:59.433](https://academa.ai/lectures/rsa-factoring-encryption?t=239.4332708333333): clockface moves to a new place on the board.
- [03:59.433](https://academa.ai/lectures/rsa-factoring-encryption?t=239.4332708333333): defn is shown on the screen, written out.
- [04:6.875](https://academa.ai/lectures/rsa-factoring-encryption?t=246.87527083333327): hours\_6 is emphasized.
- [04:12.715](https://academa.ai/lectures/rsa-factoring-encryption?t=252.7152708333333): wrap is shown on the screen, written out.

##### [04:15.684](https://academa.ai/lectures/rsa-factoring-encryption?t=255.6837708333333)

Narration: Now here is the property that makes all of this practical. You may take the remainder whenever you like. Nineteen times seven. I do not need the product at all, because nineteen is already seven on this clock. So it is seven times seven, forty nine, which is one.

Board: defn — a Panel that says "Two whole numbers are congruent modulo $n$ when they leave the same remainder on division by $n$. Everything from here on happens on a clock with $n$ positions."; wrap — a Math \[text\] that says "$17 equiv 5 quad (upright("mod") 12)$"; clockface — a Figure (x\_range=(-1.7, 1.7), y\_range=(-1.7, 1.7), aspect=(1, 1)); heading — a Heading that says "Arithmetic That Wraps Around"; dial — a Circle \[gray\] drawn in clockface (radius=1.2); hours — a Point \[text\] labelled "0" drawn in clockface (location=(7.347880794884119e-17, 1.2)); hours\_2 — a Point \[text\] labelled "1" drawn in clockface (location=(0.6000000000000001, 1.0392304845413263)); hours\_3 — a Point \[text\] labelled "2" drawn in clockface (location=(1.0392304845413265, 0.5999999999999999)); hours\_4 — a Point \[text\] labelled "3" drawn in clockface (location=(1.2, 0.0)); hours\_5 — a Point \[text\] labelled "4" drawn in clockface (location=(1.0392304845413265, -0.5999999999999999)); hours\_6 — a Point \[text\] labelled "5" drawn in clockface (location=(0.6000000000000001, -1.0392304845413263)); hours\_7 — a Point \[text\] labelled "6" drawn in clockface (location=(7.347880794884119e-17, -1.2)); hours\_8 — a Point \[text\] labelled "7" drawn in clockface (location=(-0.5999999999999998, -1.0392304845413265)); hours\_9 — a Point \[text\] labelled "8" drawn in clockface (location=(-1.0392304845413265, -0.5999999999999999)); hours\_10 — a Point \[text\] labelled "9" drawn in clockface (location=(-1.2, -1.4695761589768238e-16)); hours\_11 — a Point \[text\] labelled "10" drawn in clockface (location=(-1.0392304845413263, 0.6000000000000001)); hours\_12 — a Point \[text\] labelled "11" drawn in clockface (location=(-0.6000000000000005, 1.039230484541326)); walker — a Point \[red\] drawn in clockface (location=((0.0 + (1.2 \* cos((ang \* 0.017453292519943295)))), (0.0 + (1.2…, marker\_radius=0.1)

Actions:
- [04:15.684](https://academa.ai/lectures/rsa-factoring-encryption?t=255.6837708333333): hours\_6 is no longer emphasized.
- [04:21.999](https://academa.ai/lectures/rsa-factoring-encryption?t=261.9992708333333): reduce\_rule is shown on the screen, written out.
- [04:21.999](https://academa.ai/lectures/rsa-factoring-encryption?t=261.9992708333333): reduce\_rule (the "19 times 7" part) is emphasized.
- [04:26.771](https://academa.ai/lectures/rsa-factoring-encryption?t=266.7712708333333): walker is redrawn as the numbers it depends on change.
- [04:26.771](https://academa.ai/lectures/rsa-factoring-encryption?t=266.7712708333333): ang ticks to -480.0.
- [04:28.535](https://academa.ai/lectures/rsa-factoring-encryption?t=268.5352708333333): reduce\_rule (the "19 times 7" part) is no longer emphasized.
- [04:28.535](https://academa.ai/lectures/rsa-factoring-encryption?t=268.5352708333333): reduce\_rule (the "7 times 7" part) is emphasized.
- [04:30.021](https://academa.ai/lectures/rsa-factoring-encryption?t=270.0212708333333): walker is redrawn as the numbers it depends on change.
- [04:30.021](https://academa.ai/lectures/rsa-factoring-encryption?t=270.0212708333333): ang ticks to -660.0.
- [04:31.206](https://academa.ai/lectures/rsa-factoring-encryption?t=271.2062708333333): reduce\_rule (the "7 times 7" part) is no longer emphasized.
- [04:31.206](https://academa.ai/lectures/rsa-factoring-encryption?t=271.2062708333333): reduce\_rule (the "equiv 1" part) is emphasized.

##### [04:32.358](https://academa.ai/lectures/rsa-factoring-encryption?t=272.3577708333333)

Narration: Reduce early and reduce often, and the numbers never grow. That single habit is what lets a computer raise a six hundred digit number to a six hundred digit power without ever holding anything bigger than six hundred digits.

Board: defn — a Panel that says "Two whole numbers are congruent modulo $n$ when they leave the same remainder on division by $n$. Everything from here on happens on a clock with $n$ positions."; wrap — a Math \[text\] that says "$17 equiv 5 quad (upright("mod") 12)$"; reduce\_rule — a Math \[text\] that says "$19 times 7 equiv 7 times 7 equiv 49 equiv 1 quad (upright("mod") 12)$"; clockface — a Figure (x\_range=(-1.7, 1.7), y\_range=(-1.7, 1.7), aspect=(1, 1)); heading — a Heading that says "Arithmetic That Wraps Around"; dial — a Circle \[gray\] drawn in clockface (radius=1.2); hours — a Point \[text\] labelled "0" drawn in clockface (location=(7.347880794884119e-17, 1.2)); hours\_2 — a Point \[text\] labelled "1" drawn in clockface (location=(0.6000000000000001, 1.0392304845413263)); hours\_3 — a Point \[text\] labelled "2" drawn in clockface (location=(1.0392304845413265, 0.5999999999999999)); hours\_4 — a Point \[text\] labelled "3" drawn in clockface (location=(1.2, 0.0)); hours\_5 — a Point \[text\] labelled "4" drawn in clockface (location=(1.0392304845413265, -0.5999999999999999)); hours\_6 — a Point \[text\] labelled "5" drawn in clockface (location=(0.6000000000000001, -1.0392304845413263)); hours\_7 — a Point \[text\] labelled "6" drawn in clockface (location=(7.347880794884119e-17, -1.2)); hours\_8 — a Point \[text\] labelled "7" drawn in clockface (location=(-0.5999999999999998, -1.0392304845413265)); hours\_9 — a Point \[text\] labelled "8" drawn in clockface (location=(-1.0392304845413265, -0.5999999999999999)); hours\_10 — a Point \[text\] labelled "9" drawn in clockface (location=(-1.2, -1.4695761589768238e-16)); hours\_11 — a Point \[text\] labelled "10" drawn in clockface (location=(-1.0392304845413263, 0.6000000000000001)); hours\_12 — a Point \[text\] labelled "11" drawn in clockface (location=(-0.6000000000000005, 1.039230484541326)); walker — a Point \[red\] drawn in clockface (location=((0.0 + (1.2 \* cos((ang \* 0.017453292519943295)))), (0.0 + (1.2…, marker\_radius=0.1)

Actions:
- [04:35.474](https://academa.ai/lectures/rsa-factoring-encryption?t=275.4742708333333): reduce\_rule (the "equiv 1" part) is no longer emphasized.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): clockface is hidden from the screen — left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): dial is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_2 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_3 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_4 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_5 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_6 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_7 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_8 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_9 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_10 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_11 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): hours\_12 is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): walker is hidden from the screen — clockface left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): defn is hidden from the screen — left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): heading is hidden from the screen — left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): reduce\_rule is hidden from the screen — left the board.
- [04:45.308](https://academa.ai/lectures/rsa-factoring-encryption?t=285.3077708333333): wrap is hidden from the screen — left the board.

##### [04:46.508](https://academa.ai/lectures/rsa-factoring-encryption?t=286.5077708333333)

Narration: Now let us raise something to a power on one of these clocks. Take three, and keep multiplying it by itself, on a clock with seven positions.

Board: Empty.

Actions:
- [04:46.508](https://academa.ai/lectures/rsa-factoring-encryption?t=286.5077708333333): heading2 is shown on the screen, written out.
- [04:48.249](https://academa.ai/lectures/rsa-factoring-encryption?t=288.2492708333333): powers is shown on the screen, written out.
- [04:54.624](https://academa.ai/lectures/rsa-factoring-encryption?t=294.6242708333333): powers (the "remainder mod 7" part) is emphasized.

##### [04:56.327](https://academa.ai/lectures/rsa-factoring-encryption?t=296.3267708333333)

Narration: Three to the one is three. Three squared is nine, which is two. Three cubed is twenty seven, which is six.

Board: heading2 — a Heading that says "Powers on a Clock"

Actions:
- [04:56.327](https://academa.ai/lectures/rsa-factoring-encryption?t=296.3267708333333): forward is shown on the screen, written out.
- [04:56.327](https://academa.ai/lectures/rsa-factoring-encryption?t=296.3267708333333): powers (the "remainder mod 7" part) is no longer emphasized.
- [04:57.279](https://academa.ai/lectures/rsa-factoring-encryption?t=297.27927083333327): powers is shown on the screen, written out.
- [04:59.148](https://academa.ai/lectures/rsa-factoring-encryption?t=299.1482708333333): powers is shown on the screen, written out.
- [05:1.853](https://academa.ai/lectures/rsa-factoring-encryption?t=301.8532708333333): powers is shown on the screen, written out.

##### [05:4.81](https://academa.ai/lectures/rsa-factoring-encryption?t=304.8097708333333)

Narration: Then eighty one, which is four. Then two hundred and forty three, which is five. Then seven hundred and twenty nine, which is one, and after that the whole thing repeats forever.

Board: forward — a Tex \[text\] that says "Forwards: given $k$, get the remainder. Easy."; heading2 — a Heading that says "Powers on a Clock"

Actions:
- [05:5.53](https://academa.ai/lectures/rsa-factoring-encryption?t=305.5302708333333): powers is shown on the screen, written out.
- [05:8.362](https://academa.ai/lectures/rsa-factoring-encryption?t=308.3622708333333): powers is shown on the screen, written out.
- [05:11.393](https://academa.ai/lectures/rsa-factoring-encryption?t=311.3932708333333): powers is shown on the screen, written out.

##### [05:17.333](https://academa.ai/lectures/rsa-factoring-encryption?t=317.3332708333333)

Narration: Now look down that last column. Three, two, six, four, five, one. That is a scramble. There is no pattern you can eyeball, and here is the point: if I tell you the answer is five, and ask which power of three produced it, you are back to guessing.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [05:18.645](https://academa.ai/lectures/rsa-factoring-encryption?t=318.6452708333333): powers (the "remainder mod 7" part) is emphasized.
- [05:32.228](https://academa.ai/lectures/rsa-factoring-encryption?t=332.2282708333333): backward is shown on the screen, written out.

##### [05:33.467](https://academa.ai/lectures/rsa-factoring-encryption?t=333.46677083333327)

Narration: That problem has a name, the discrete logarithm, and nobody has a fast method for it either. So there are our two one way streets. Multiplying primes is easy and factoring is hard. Raising to a power on a clock is cheap and coming back is not.

Board: forward — a Tex \[text\] that says "Forwards: given $k$, get the remainder. Easy."; backward — a Tex \[text\] that says "Backwards: given the remainder, get $k$. Nobody knows how."; heading2 — a Heading that says "Powers on a Clock"

Actions:
- [05:41.106](https://academa.ai/lectures/rsa-factoring-encryption?t=341.10627083333327): powers (the "remainder mod 7" part) is no longer emphasized.
- [05:43.254](https://academa.ai/lectures/rsa-factoring-encryption?t=343.2542708333333): forward is indicated — a transient flash.
- [05:44.473](https://academa.ai/lectures/rsa-factoring-encryption?t=344.4732708333333): backward is indicated — a transient flash.
- [05:49.314](https://academa.ai/lectures/rsa-factoring-encryption?t=349.3138958333333): backward is hidden from the screen — left the board.
- [05:49.314](https://academa.ai/lectures/rsa-factoring-encryption?t=349.3138958333333): forward is hidden from the screen — left the board.
- [05:49.314](https://academa.ai/lectures/rsa-factoring-encryption?t=349.3138958333333): heading2 is hidden from the screen — left the board.
- [05:49.314](https://academa.ai/lectures/rsa-factoring-encryption?t=349.3138958333333): powers is hidden from the screen — left the board.

### Scene 3: [Building the Keys](https://academa.ai/lectures/rsa-factoring-encryption?t=350.35556249999996)

Span: 05:50.356–09:36.521 (350.35556249999996s–576.5207083333333s).

#### Objects

- count: a Math \[text\] that says "$phi(15) = 8 = (3 - 1)(5 - 1)$"
- d1: a Math \[text\] that says "$17 d equiv 1 quad (op("mod") 3120)$"
- d2: a Math \[text\] that says "$17 d = 1 + k times 3120$"
- d3: a Math \[text\] that says "$d = 2753$"
- e\_prod: a Math \[text\] that says "$upright("in production:") quad e = 2^16 + 1 = 65537$"
- factor15: a Math \[text\] that says "$15 = 3 times 5$"
- g1: a Math \[text\] that says "$p = 61, quad q = 53$"
- g2: a Math \[text\] that says "$n = p q = 3233$"
- g3: a Math \[text\] that says "$phi(n) = 60 times 52 = 3120$"
- g4: a Math \[text\] that says "$e = 17$"
- general: a Math \[text\] that says "$phi(p q) = (p - 1)(q - 1)$"
- heading1: a Heading that says "Counting What Shares No Factor"
- heading2: a Heading that says "Making a Key Pair"
- heading3: a Heading that says "Finding the Private Exponent"
- hunt: a Table \[text\] that says "$k$ $1 + 3120 k$ divisible by 17? 1 3121 no 2 6241 no 3 9361 no $dots$ $dots$ $dots$ 15 46801 yes" (rows=(('$k$', '$1 + 3120 k$', 'divisible by 17?'), ('1', '3121', 'no…, header=True)
- keys: a Block \[text\] that says "Public: $(3233, 17)$. Hand it to anybody. Private: $d = 2753$. Tell nobody, ever."
- nums: a Math \[text\] that says "$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14$"
- pub: a Tex \[text\] that says "Public key: $(n, e) = (3233, 17)$"
- totient: a Panel that says "$phi(n)$ counts the whole numbers from 1 up to $n - 1$ that share no factor with $n$."

#### Beats

##### [05:50.356](https://academa.ai/lectures/rsa-factoring-encryption?t=350.35556249999996)

Narration: Right. Let us build an actual key. There is exactly one piece of number theory you need first, and it is a counting question. So let me do the counting on a number small enough to see all of at once: fifteen, which is three times five.

Board: Empty.

Actions:
- [05:50.356](https://academa.ai/lectures/rsa-factoring-encryption?t=350.35556249999996): heading1 is shown on the screen, written out.
- [06:2.709](https://academa.ai/lectures/rsa-factoring-encryption?t=362.70856249999997): factor15 is shown on the screen, written out.

##### [06:6.119](https://academa.ai/lectures/rsa-factoring-encryption?t=366.11856249999994)

Narration: Here is every whole number below it. Now cross out the ones that share a factor with fifteen. The multiples of three: three, six, nine, twelve.

Board: factor15 — a Math \[text\] that says "$15 = 3 times 5$"; heading1 — a Heading that says "Counting What Shares No Factor"

Actions:
- [06:6.467](https://academa.ai/lectures/rsa-factoring-encryption?t=366.46656249999995): nums is shown on the screen, written out.
- [06:12.795](https://academa.ai/lectures/rsa-factoring-encryption?t=372.7945625): nums (the "12" part) is slashed through — it cancels.
- [06:12.795](https://academa.ai/lectures/rsa-factoring-encryption?t=372.7945625): nums (the "3" part) is slashed through — it cancels.
- [06:12.795](https://academa.ai/lectures/rsa-factoring-encryption?t=372.7945625): nums (the "6" part) is slashed through — it cancels.
- [06:12.795](https://academa.ai/lectures/rsa-factoring-encryption?t=372.7945625): nums (the "9" part) is slashed through — it cancels.

##### [06:17.411](https://academa.ai/lectures/rsa-factoring-encryption?t=377.41106249999996)

Narration: And the multiples of five: five, and ten. What is left? One, two, four, seven, eight, eleven, thirteen and fourteen. Eight numbers survive.

Board: factor15 — a Math \[text\] that says "$15 = 3 times 5$"; nums — a Math \[text\] that says "$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14$"; heading1 — a Heading that says "Counting What Shares No Factor"

Actions:
- [06:18.689](https://academa.ai/lectures/rsa-factoring-encryption?t=378.6885625): nums (the "10" part) is slashed through — it cancels.
- [06:18.689](https://academa.ai/lectures/rsa-factoring-encryption?t=378.6885625): nums (the "5" part) is slashed through — it cancels.
- [06:28.429](https://academa.ai/lectures/rsa-factoring-encryption?t=388.4285625): count is shown on the screen, written out.

##### [06:30.074](https://academa.ai/lectures/rsa-factoring-encryption?t=390.07406249999997)

Narration: Eight is two times four. And two is three minus one, four is five minus one. That is not a coincidence. For any product of two primes, the count comes out as p minus one, times q minus one.

Board: factor15 — a Math \[text\] that says "$15 = 3 times 5$"; nums — a Math \[text\] that says "$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14$"; count — a Math \[text\] that says "$phi(15) = 8 = (3 - 1)(5 - 1)$"; heading1 — a Heading that says "Counting What Shares No Factor"

Actions:
- [06:33.116](https://academa.ai/lectures/rsa-factoring-encryption?t=393.11556249999995): count (the "3 - 1" part) is emphasized.
- [06:34.753](https://academa.ai/lectures/rsa-factoring-encryption?t=394.75256249999995): count (the "3 - 1" part) is no longer emphasized.
- [06:34.753](https://academa.ai/lectures/rsa-factoring-encryption?t=394.75256249999995): count (the "5 - 1" part) is emphasized.
- [06:38.352](https://academa.ai/lectures/rsa-factoring-encryption?t=398.3515625): general is shown on the screen, written out.
- [06:38.352](https://academa.ai/lectures/rsa-factoring-encryption?t=398.3515625): count (the "5 - 1" part) is no longer emphasized.

##### [06:44.06](https://academa.ai/lectures/rsa-factoring-encryption?t=404.05956249999997)

Narration: This count has a name and a symbol. It is Euler's totient function, written phi of n. Hold on to it, because it is the only genuinely new symbol in this lecture.

Board: factor15 — a Math \[text\] that says "$15 = 3 times 5$"; nums — a Math \[text\] that says "$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14$"; count — a Math \[text\] that says "$phi(15) = 8 = (3 - 1)(5 - 1)$"; general — a Math \[text\] that says "$phi(p q) = (p - 1)(q - 1)$"; heading1 — a Heading that says "Counting What Shares No Factor"

Actions:
- [06:47.868](https://academa.ai/lectures/rsa-factoring-encryption?t=407.86756249999996): totient is shown on the screen, written out.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): count is hidden from the screen — left the board.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): factor15 is hidden from the screen — left the board.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): general is hidden from the screen — left the board.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): heading1 is hidden from the screen — left the board.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): nums is hidden from the screen — left the board.
- [06:55.112](https://academa.ai/lectures/rsa-factoring-encryption?t=415.1120625): totient is hidden from the screen — left the board.

##### [06:56.312](https://academa.ai/lectures/rsa-factoring-encryption?t=416.31206249999997)

Narration: Now the real thing. I pick two primes: sixty one and fifty three. Real RSA picks primes with about three hundred digits each, by generating random odd numbers and testing them, which is fast. The arithmetic is identical. I just want numbers you can check by hand.

Board: Empty.

Actions:
- [06:56.312](https://academa.ai/lectures/rsa-factoring-encryption?t=416.31206249999997): heading2 is shown on the screen, written out.
- [06:58.716](https://academa.ai/lectures/rsa-factoring-encryption?t=418.7155625): g1 is shown on the screen, written out.

##### [07:14.1](https://academa.ai/lectures/rsa-factoring-encryption?t=434.1000625)

Narration: Multiply them. That is n, and it is the modulus: the size of the clock that everything from here on happens on. You have seen it twice already today.

Board: g1 — a Math \[text\] that says "$p = 61, quad q = 53$"; heading2 — a Heading that says "Making a Key Pair"

Actions:
- [07:14.292](https://academa.ai/lectures/rsa-factoring-encryption?t=434.29156249999994): g2 is shown on the screen, written out.
- [07:17.334](https://academa.ai/lectures/rsa-factoring-encryption?t=437.33356249999997): g2 (the "3233" part) is emphasized.

##### [07:24.679](https://academa.ai/lectures/rsa-factoring-encryption?t=444.6790625)

Narration: Now compute phi of n from the two primes. Sixty times fifty two, which is this number here. And notice that you could only do that because you know p and q. From n on its own, computing phi is exactly as hard as factoring.

Board: g1 — a Math \[text\] that says "$p = 61, quad q = 53$"; g2 — a Math \[text\] that says "$n = p q = 3233$"; heading2 — a Heading that says "Making a Key Pair"

Actions:
- [07:24.679](https://academa.ai/lectures/rsa-factoring-encryption?t=444.6790625): g2 (the "3233" part) is no longer emphasized.
- [07:25.225](https://academa.ai/lectures/rsa-factoring-encryption?t=445.22456249999993): g3 is shown on the screen, written out.
- [07:30.31](https://academa.ai/lectures/rsa-factoring-encryption?t=450.30956249999997): g3 (the "3120" part) is emphasized.
- [07:33.608](https://academa.ai/lectures/rsa-factoring-encryption?t=453.6075625): g1 is emphasized.
- [07:39.099](https://academa.ai/lectures/rsa-factoring-encryption?t=459.09856249999996): g1 is no longer emphasized.

##### [07:40.697](https://academa.ai/lectures/rsa-factoring-encryption?t=460.69706249999996)

Narration: Last, pick a public exponent, e. The one requirement is that it shares no factor with phi of n. Seventeen will do nicely: it is prime, and it does not divide the totient.

Board: g1 — a Math \[text\] that says "$p = 61, quad q = 53$"; g2 — a Math \[text\] that says "$n = p q = 3233$"; g3 — a Math \[text\] that says "$phi(n) = 60 times 52 = 3120$"; heading2 — a Heading that says "Making a Key Pair"

Actions:
- [07:48.72](https://academa.ai/lectures/rsa-factoring-encryption?t=468.71956249999994): g4 is shown on the screen, written out.

##### [07:54.243](https://academa.ai/lectures/rsa-factoring-encryption?t=474.24256249999996)

Narration: In production, e is almost always one particular number, two to the sixteen plus one. Nothing deep is going on there. That exponent is simply quick to raise things to.

Board: g1 — a Math \[text\] that says "$p = 61, quad q = 53$"; g2 — a Math \[text\] that says "$n = p q = 3233$"; g3 — a Math \[text\] that says "$phi(n) = 60 times 52 = 3120$"; g4 — a Math \[text\] that says "$e = 17$"; heading2 — a Heading that says "Making a Key Pair"

Actions:
- [07:54.243](https://academa.ai/lectures/rsa-factoring-encryption?t=474.24256249999996): g3 (the "3120" part) is no longer emphasized.
- [07:57.169](https://academa.ai/lectures/rsa-factoring-encryption?t=477.16856249999995): e\_prod is shown on the screen, written out.
- [08:3.74](https://academa.ai/lectures/rsa-factoring-encryption?t=483.7395625): e\_prod is emphasized.

##### [08:5.809](https://academa.ai/lectures/rsa-factoring-encryption?t=485.8085625)

Narration: And that is the public key: the pair n and e. You publish it. You put it in your certificate, you hand it to strangers, you print it on a poster. It is exactly the pair I showed you in the first minute.

Board: g1 — a Math \[text\] that says "$p = 61, quad q = 53$"; g2 — a Math \[text\] that says "$n = p q = 3233$"; g3 — a Math \[text\] that says "$phi(n) = 60 times 52 = 3120$"; g4 — a Math \[text\] that says "$e = 17$"; e\_prod — a Math \[text\] that says "$upright("in production:") quad e = 2^16 + 1 = 65537$"; heading2 — a Heading that says "Making a Key Pair"

Actions:
- [08:5.809](https://academa.ai/lectures/rsa-factoring-encryption?t=485.8085625): e\_prod is hidden from the screen.
- [08:5.809](https://academa.ai/lectures/rsa-factoring-encryption?t=485.8085625): e\_prod is no longer emphasized.
- [08:6.616](https://academa.ai/lectures/rsa-factoring-encryption?t=486.61556249999995): pub is shown on the screen, written out.
- [08:14.313](https://academa.ai/lectures/rsa-factoring-encryption?t=494.31256249999996): pub is indicated — a transient flash.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): g1 is hidden from the screen — left the board.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): g2 is hidden from the screen — left the board.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): g3 is hidden from the screen — left the board.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): g4 is hidden from the screen — left the board.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): heading2 is hidden from the screen — left the board.
- [08:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=498.80606249999994): pub is hidden from the screen — left the board.

##### [08:20.006](https://academa.ai/lectures/rsa-factoring-encryption?t=500.0060625)

Narration: The private key is one more number, d, and it is fixed by a single condition: e times d has to be congruent to one, modulo phi of n.

Board: Empty.

Actions:
- [08:20.006](https://academa.ai/lectures/rsa-factoring-encryption?t=500.0060625): heading3 is shown on the screen, written out.
- [08:24.511](https://academa.ai/lectures/rsa-factoring-encryption?t=504.51056249999993): d1 is shown on the screen, written out.

##### [08:30.654](https://academa.ai/lectures/rsa-factoring-encryption?t=510.65406249999995)

Narration: Unpack that. It says seventeen d is one more than some whole multiple of phi of n. So go and look for the multiple.

Board: d1 — a Math \[text\] that says "$17 d equiv 1 quad (op("mod") 3120)$"; heading3 — a Heading that says "Finding the Private Exponent"

Actions:
- [08:30.846](https://academa.ai/lectures/rsa-factoring-encryption?t=510.8455624999999): d2 is shown on the screen, written out.
- [08:35.014](https://academa.ai/lectures/rsa-factoring-encryption?t=515.0135624999999): d2 (the "k times 3120" part) is emphasized.

##### [08:39.683](https://academa.ai/lectures/rsa-factoring-encryption?t=519.6825624999999)

Narration: Take k equals one. That gives three thousand one hundred and twenty one, and seventeen does not divide it. Bump k to two: six thousand two hundred and forty one, and again no. Bump it once more, and still no.

Board: d1 — a Math \[text\] that says "$17 d equiv 1 quad (op("mod") 3120)$"; d2 — a Math \[text\] that says "$17 d = 1 + k times 3120$"; heading3 — a Heading that says "Finding the Private Exponent"

Actions:
- [08:39.683](https://academa.ai/lectures/rsa-factoring-encryption?t=519.6825624999999): d2 (the "k times 3120" part) is no longer emphasized.
- [08:39.77](https://academa.ai/lectures/rsa-factoring-encryption?t=519.7695624999999): hunt is shown on the screen, written out.
- [08:41.756](https://academa.ai/lectures/rsa-factoring-encryption?t=521.7555625): hunt is shown on the screen, written out.
- [08:41.756](https://academa.ai/lectures/rsa-factoring-encryption?t=521.7555625): hunt (the "3121" part) is emphasized.
- [08:46.574](https://academa.ai/lectures/rsa-factoring-encryption?t=526.5735625): hunt is shown on the screen, written out.
- [08:47.979](https://academa.ai/lectures/rsa-factoring-encryption?t=527.9785625): hunt (the "3121" part) is no longer emphasized.
- [08:47.979](https://academa.ai/lectures/rsa-factoring-encryption?t=527.9785625): hunt (the "6241" part) is emphasized.
- [08:52.018](https://academa.ai/lectures/rsa-factoring-encryption?t=532.0175624999999): hunt is shown on the screen, written out.

##### [08:54.476](https://academa.ai/lectures/rsa-factoring-encryption?t=534.4755625)

Narration: Keep going, and at k equals fifteen you get this one. And that is seventeen times two thousand seven hundred and fifty three, exactly. So there is d.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [08:55.08](https://academa.ai/lectures/rsa-factoring-encryption?t=535.0795625): hunt is shown on the screen, written out.
- [08:56.821](https://academa.ai/lectures/rsa-factoring-encryption?t=536.8205624999999): hunt is shown on the screen, written out.
- [08:57.924](https://academa.ai/lectures/rsa-factoring-encryption?t=537.9235624999999): hunt (the "46801" part) is emphasized.
- [08:57.924](https://academa.ai/lectures/rsa-factoring-encryption?t=537.9235624999999): hunt (the "6241" part) is no longer emphasized.
- [09:2.081](https://academa.ai/lectures/rsa-factoring-encryption?t=542.0805624999999): d3 is shown on the screen, written out.
- [09:3.439](https://academa.ai/lectures/rsa-factoring-encryption?t=543.4385625): A box is drawn around d3.

##### [09:4.932](https://academa.ai/lectures/rsa-factoring-encryption?t=544.9320625)

Narration: You would never do it that way in code. The extended Euclidean algorithm produces d in a few dozen steps, for numbers of any size at all. But that is what d is: the number that undoes seventeen, on a clock of size phi of n.

Board: d1 — a Math \[text\] that says "$17 d equiv 1 quad (op("mod") 3120)$"; d2 — a Math \[text\] that says "$17 d = 1 + k times 3120$"; d3 — a Math \[text\] that says "$d = 2753$"; heading3 — a Heading that says "Finding the Private Exponent"

Actions:
- [09:4.932](https://academa.ai/lectures/rsa-factoring-encryption?t=544.9320625): hunt (the "46801" part) is no longer emphasized.
- [09:6.106](https://academa.ai/lectures/rsa-factoring-encryption?t=546.1055624999999): hunt is indicated — a transient flash.
- [09:16.322](https://academa.ai/lectures/rsa-factoring-encryption?t=556.3215625): d1 (the "17 d" part) is emphasized.

##### [09:20.904](https://academa.ai/lectures/rsa-factoring-encryption?t=560.9040625)

Narration: So there is the pair. The public key is n and e, and anybody may have it. The private key is d, and every step that produced it leaned on this number here, which came from the two primes. They are the whole secret.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [09:20.904](https://academa.ai/lectures/rsa-factoring-encryption?t=560.9040625): d1 (the "17 d" part) is no longer emphasized.
- [09:21.938](https://academa.ai/lectures/rsa-factoring-encryption?t=561.9375625): keys is shown on the screen, written out.
- [09:27.267](https://academa.ai/lectures/rsa-factoring-encryption?t=567.2665625): d3 is indicated — a transient flash.
- [09:31.133](https://academa.ai/lectures/rsa-factoring-encryption?t=571.1325625): d1 (the "3120" part) is emphasized.
- [09:34.535](https://academa.ai/lectures/rsa-factoring-encryption?t=574.5345625): d1 (the "3120" part) is no longer emphasized.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): d1 is hidden from the screen — left the board.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): d2 is hidden from the screen — left the board.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): d3 is hidden from the screen — left the board.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): heading3 is hidden from the screen — left the board.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): hunt is hidden from the screen — left the board.
- [09:35.479](https://academa.ai/lectures/rsa-factoring-encryption?t=575.4790416666667): keys is hidden from the screen — left the board.

### Scene 4: [Encrypting One Message](https://academa.ai/lectures/rsa-factoring-encryption?t=576.5207083333333)

Span: 09:36.521–13:40.995 (576.5207083333333s–820.9947500000001s).

#### Objects

- back: a Math \[text\] that says "$m = 65$"
- bits: a Math \[text\] that says "$2753 = 2048 + 512 + 128 + 64 + 1$"
- c64: a Point \[yellow\] labelled "1577" drawn in spread (location=(1577, 0.0))
- c66: a Point \[yellow\] labelled "524" drawn in spread (location=(524, 0.0))
- c\_mark: a Point \[red\] labelled "c = 2790" drawn in spread (location=(2790, 0.0))
- cipher: a Math \[text\] that says "$c = 2790$"
- conc: a Math \[text\] that says "$c equiv 65^17 quad (upright("mod") 3233)$"
- dconc: a Math \[text\] that says "$m equiv 2790^2753 quad (upright("mod") 3233)$"
- down: a CurvedArrow \[green\] labelled "(dot.op)^2753" drawn in loop (start=(8.9, 2.6), end=(3.0, 2.6))
- fit: a Math \[text\] that says "$0 lt.eq m lt n$"
- ladder: a Derivation \[text\] that says "$65^2 &equiv 4225 equiv 992 \\ 65^4 &equiv 992^2 equiv 1232 \\ 65^8 &equiv 1232^2 equiv 1547 \\ 65^16 &equiv 1547^2 equiv 789 \\ 65^17 &equiv 789 times 65 equiv 2790$"
- lbl\_c: a Math \[text\] that says "$c = 2790$" drawn in loop
- lbl\_m: a Math \[text\] that says "$m = 65$" drawn in loop
- loop: a Figure (x\_range=(0, 12), y\_range=(0, 6), aspect=(12, 6))
- m\_mark: a Point \[green\] labelled "m = 65" drawn in spread (location=(65, 0.0))
- prob2: a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."
- problem: a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."
- rule\_dec: a Math \[text\] that says "$m equiv c^d quad (upright("mod") n)$"
- rule\_enc: a Math \[text\] that says "$c equiv m^e quad (upright("mod") n)$"
- scatter\_caption: a Tex \[text\] that says "Three consecutive messages, three unrelated ciphertexts."
- scatter\_heading: a Heading that says "Where the Ciphertext Lands"
- spread: a NumberLine labelled "c" (x\_range=(0, 3233), include\_numbers=True, ticks\_every=500)
- up: a CurvedArrow \[red\] labelled "(dot.op)^17" drawn in loop (start=(3.0, 3.4), end=(8.9, 3.4))

#### Beats

##### [09:36.521](https://academa.ai/lectures/rsa-factoring-encryption?t=576.5207083333333)

Narration: All right. Your public key is out in the world, and I want to send you a message. The message is the letter A. My computer stores A as the number sixty five, so my message, as a number, is sixty five.

Board: Empty.

Actions:
- [09:36.521](https://academa.ai/lectures/rsa-factoring-encryption?t=576.5207083333333): problem is shown on the screen, written out.
- [09:44.845](https://academa.ai/lectures/rsa-factoring-encryption?t=584.8447083333333): problem (the "ASCII 65" part) is emphasized.

##### [09:51.436](https://academa.ai/lectures/rsa-factoring-encryption?t=591.4357083333333)

Narration: Encryption is one line of arithmetic. The ciphertext c is the message raised to the public exponent e, modulo n. That is the entire operation.

Board: problem — a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."

Actions:
- [09:51.436](https://academa.ai/lectures/rsa-factoring-encryption?t=591.4357083333333): problem (the "ASCII 65" part) is no longer emphasized.
- [09:54.814](https://academa.ai/lectures/rsa-factoring-encryption?t=594.8137083333334): rule\_enc is shown on the screen, written out.

##### [10:3.384](https://academa.ai/lectures/rsa-factoring-encryption?t=603.3842083333334)

Narration: There is exactly one rule about the message: as a number it has to be smaller than n. Sixty five is comfortably smaller than our modulus, so we are fine. A real message gets chopped into blocks that each fit.

Board: rule\_enc — a Math \[text\] that says "$c equiv m^e quad (upright("mod") n)$"; problem — a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."

Actions:
- [10:4.772](https://academa.ai/lectures/rsa-factoring-encryption?t=604.7717083333333): fit is shown on the screen, written out.
- [10:7.489](https://academa.ai/lectures/rsa-factoring-encryption?t=607.4887083333333): fit (the "m lt n" part) is emphasized.

##### [10:17.876](https://academa.ai/lectures/rsa-factoring-encryption?t=617.8762083333334)

Narration: So here is our case: sixty five, to the seventeenth, on a clock of that size. Now that power is a thirty one digit number. We are never going to write it down, and we do not have to, because of the habit from earlier: reduce at every step.

Board: rule\_enc — a Math \[text\] that says "$c equiv m^e quad (upright("mod") n)$"; fit — a Math \[text\] that says "$0 lt.eq m lt n$"; problem — a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."

Actions:
- [10:17.876](https://academa.ai/lectures/rsa-factoring-encryption?t=617.8762083333334): fit (the "m lt n" part) is no longer emphasized.
- [10:19.281](https://academa.ai/lectures/rsa-factoring-encryption?t=619.2807083333333): conc is shown on the screen, written out.
- [10:24.97](https://academa.ai/lectures/rsa-factoring-encryption?t=624.9697083333333): conc (the "65^17" part) is emphasized.
- [10:32.365](https://academa.ai/lectures/rsa-factoring-encryption?t=632.3647083333334): conc (the "65^17" part) is no longer emphasized.

##### [10:34.962](https://academa.ai/lectures/rsa-factoring-encryption?t=634.9617083333334)

Narration: Watch. Square sixty five: four thousand two hundred and twenty five, which on our clock is nine hundred and ninety two. Square that, reduce it again, and you get one thousand two hundred and thirty two, which is sixty five to the fourth.

Board: rule\_enc — a Math \[text\] that says "$c equiv m^e quad (upright("mod") n)$"; fit — a Math \[text\] that says "$0 lt.eq m lt n$"; conc — a Math \[text\] that says "$c equiv 65^17 quad (upright("mod") 3233)$"; problem — a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."

Actions:
- [10:36.297](https://academa.ai/lectures/rsa-factoring-encryption?t=636.2967083333333): ladder is shown on the screen, written out.
- [10:43.751](https://academa.ai/lectures/rsa-factoring-encryption?t=643.7507083333334): ladder is shown on the screen, written out.

##### [10:50.737](https://academa.ai/lectures/rsa-factoring-encryption?t=650.7367083333334)

Narration: Square again and you have the eighth power: one thousand five hundred and forty seven. Once more and you have the sixteenth: seven hundred and eighty nine. Four squarings so far, and we have climbed all the way to sixteen.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [10:52.664](https://academa.ai/lectures/rsa-factoring-encryption?t=652.6637083333334): ladder is shown on the screen, written out.
- [10:57.842](https://academa.ai/lectures/rsa-factoring-encryption?t=657.8417083333334): ladder is shown on the screen, written out.

##### [11:5.768](https://academa.ai/lectures/rsa-factoring-encryption?t=665.7677083333333)

Narration: And seventeen is sixteen plus one. So one final multiplication by sixty five. Seven hundred and eighty nine times sixty five is fifty one thousand two hundred and eighty five, and on our clock that lands here.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [11:9.867](https://academa.ai/lectures/rsa-factoring-encryption?t=669.8667083333333): ladder is shown on the screen, written out.
- [11:18.806](https://academa.ai/lectures/rsa-factoring-encryption?t=678.8057083333333): cipher is shown on the screen, written out.

##### [11:20.521](https://academa.ai/lectures/rsa-factoring-encryption?t=680.5207083333333)

Narration: Four squarings and one multiplication. Not seventeen multiplications. And for a real two thousand bit exponent it is about three thousand steps. That is why your browser does this without you ever noticing.

Board: rule\_enc — a Math \[text\] that says "$c equiv m^e quad (upright("mod") n)$"; fit — a Math \[text\] that says "$0 lt.eq m lt n$"; conc — a Math \[text\] that says "$c equiv 65^17 quad (upright("mod") 3233)$"; cipher — a Math \[text\] that says "$c = 2790$"; problem — a Tex \[text\] that says "Send the letter A (ASCII 65) to the holder of $(3233, 17)$."

Actions:
- [11:20.997](https://academa.ai/lectures/rsa-factoring-encryption?t=680.9967083333333): A box is drawn around cipher.
- [11:21.299](https://academa.ai/lectures/rsa-factoring-encryption?t=681.2987083333334): ladder is emphasized.
- [11:21.449](https://academa.ai/lectures/rsa-factoring-encryption?t=681.4487083333333): ladder is emphasized.
- [11:21.599](https://academa.ai/lectures/rsa-factoring-encryption?t=681.5987083333334): ladder is emphasized.
- [11:21.749](https://academa.ai/lectures/rsa-factoring-encryption?t=681.7487083333334): ladder is emphasized.
- [11:31.608](https://academa.ai/lectures/rsa-factoring-encryption?t=691.6077083333333): ladder is no longer emphasized.
- [11:31.608](https://academa.ai/lectures/rsa-factoring-encryption?t=691.6077083333333): ladder is no longer emphasized.
- [11:31.608](https://academa.ai/lectures/rsa-factoring-encryption?t=691.6077083333333): ladder is no longer emphasized.
- [11:31.608](https://academa.ai/lectures/rsa-factoring-encryption?t=691.6077083333333): ladder is no longer emphasized.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): cipher is hidden from the screen — left the board.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): conc is hidden from the screen — left the board.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): fit is hidden from the screen — left the board.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): ladder is hidden from the screen — left the board.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): problem is hidden from the screen — left the board.
- [11:34.197](https://academa.ai/lectures/rsa-factoring-encryption?t=694.1972083333334): rule\_enc is hidden from the screen — left the board.

##### [11:35.397](https://academa.ai/lectures/rsa-factoring-encryption?t=695.3972083333333)

Narration: Let me lay out the whole range, from zero up to n. Here is the message, down at sixty five. And here is the ciphertext, way over there.

Board: Empty.

Actions:
- [11:35.397](https://academa.ai/lectures/rsa-factoring-encryption?t=695.3972083333333): scatter\_heading is shown on the screen, written out.
- [11:36.872](https://academa.ai/lectures/rsa-factoring-encryption?t=696.8717083333333): spread is shown on the screen, written out.
- [11:39.832](https://academa.ai/lectures/rsa-factoring-encryption?t=699.8317083333334): m\_mark is shown on the screen, written out.
- [11:44.499](https://academa.ai/lectures/rsa-factoring-encryption?t=704.4987083333334): c\_mark is shown on the screen, written out.

##### [11:46.109](https://academa.ai/lectures/rsa-factoring-encryption?t=706.1087083333334)

Narration: Now look at the neighbours. Sixty four encrypts to fifteen seventy seven. Sixty six encrypts to five hundred and twenty four. Three consecutive messages, three ciphertexts flung all over the range. There is nothing to read off and nothing to interpolate between.

Board: spread — a NumberLine labelled "c" (x\_range=(0, 3233), include\_numbers=True, ticks\_every=500); scatter\_heading — a Heading that says "Where the Ciphertext Lands"; m\_mark — a Point \[green\] labelled "m = 65" drawn in spread (location=(65, 0.0)); c\_mark — a Point \[red\] labelled "c = 2790" drawn in spread (location=(2790, 0.0))

Actions:
- [11:49.941](https://academa.ai/lectures/rsa-factoring-encryption?t=709.9407083333333): c64 is shown on the screen, written out.
- [11:54.225](https://academa.ai/lectures/rsa-factoring-encryption?t=714.2247083333334): c66 is shown on the screen, written out.

##### [12:4.392](https://academa.ai/lectures/rsa-factoring-encryption?t=724.3917083333333)

Narration: That scatter is the point. Encryption here is not a shuffle or a substitution you could work backwards from by staring at it. It is one modular power, and it throws the message somewhere unpredictable inside the range.

Board: spread — a NumberLine labelled "c" (x\_range=(0, 3233), include\_numbers=True, ticks\_every=500); scatter\_heading — a Heading that says "Where the Ciphertext Lands"; m\_mark — a Point \[green\] labelled "m = 65" drawn in spread (location=(65, 0.0)); c\_mark — a Point \[red\] labelled "c = 2790" drawn in spread (location=(2790, 0.0)); c64 — a Point \[yellow\] labelled "1577" drawn in spread (location=(1577, 0.0)); c66 — a Point \[yellow\] labelled "524" drawn in spread (location=(524, 0.0))

Actions:
- [12:4.914](https://academa.ai/lectures/rsa-factoring-encryption?t=724.9137083333334): scatter\_caption is shown on the screen, written out.
- [12:13.866](https://academa.ai/lectures/rsa-factoring-encryption?t=733.8657083333334): c\_mark is indicated — a transient flash.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): scatter\_caption is hidden from the screen — left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): scatter\_heading is hidden from the screen — left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): spread is hidden from the screen — left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): m\_mark is hidden from the screen — spread left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): c\_mark is hidden from the screen — spread left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): c64 is hidden from the screen — spread left the board.
- [12:17.244](https://academa.ai/lectures/rsa-factoring-encryption?t=737.2442083333334): c66 is hidden from the screen — spread left the board.

##### [12:18.444](https://academa.ai/lectures/rsa-factoring-encryption?t=738.4442083333333)

Narration: Now your side of it. The ciphertext is twenty-seven ninety, the private exponent is twenty-seven fifty-three, and the number we want back is sixty-five. Those are the numbers in front of us.

Board: Empty.

Actions:
- [12:18.444](https://academa.ai/lectures/rsa-factoring-encryption?t=738.4442083333333): prob2 is shown on the screen, written out.

##### [12:31.061](https://academa.ai/lectures/rsa-factoring-encryption?t=751.0607083333334)

Narration: Now write the relationship. The message m is c to the d, modulo n. For our ciphertext and private exponent, that is twenty-seven ninety to the twenty-seven fifty-three, modulo thirty-two thirty-three. In principle that is astronomically large, and again we never build it.

Board: prob2 — a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."

Actions:
- [12:32.083](https://academa.ai/lectures/rsa-factoring-encryption?t=752.0827083333334): rule\_dec is shown on the screen, written out.
- [12:38.004](https://academa.ai/lectures/rsa-factoring-encryption?t=758.0037083333334): dconc is shown on the screen, written out.
- [12:41.894](https://academa.ai/lectures/rsa-factoring-encryption?t=761.8937083333334): dconc (the "2790" part) is emphasized.
- [12:43.089](https://academa.ai/lectures/rsa-factoring-encryption?t=763.0887083333334): dconc (the "2753" part) is emphasized.
- [12:43.089](https://academa.ai/lectures/rsa-factoring-encryption?t=763.0887083333334): dconc (the "2790" part) is no longer emphasized.

##### [12:51.666](https://academa.ai/lectures/rsa-factoring-encryption?t=771.6657083333334)

Narration: Same trick. Two thousand seven hundred and fifty three is a sum of five powers of two: two thousand and forty eight, plus five hundred and twelve, plus one hundred and twenty eight, plus sixty four, plus one.

Board: rule\_dec — a Math \[text\] that says "$m equiv c^d quad (upright("mod") n)$"; dconc — a Math \[text\] that says "$m equiv 2790^2753 quad (upright("mod") 3233)$"; prob2 — a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."

Actions:
- [12:51.666](https://academa.ai/lectures/rsa-factoring-encryption?t=771.6657083333334): dconc (the "2753" part) is no longer emphasized.
- [12:55.799](https://academa.ai/lectures/rsa-factoring-encryption?t=775.7987083333334): bits is shown on the screen, written out.
- [12:58.841](https://academa.ai/lectures/rsa-factoring-encryption?t=778.8407083333334): bits (the "2048" part) is emphasized.
- [13:0.64](https://academa.ai/lectures/rsa-factoring-encryption?t=780.6397083333334): bits (the "2048" part) is no longer emphasized.
- [13:0.64](https://academa.ai/lectures/rsa-factoring-encryption?t=780.6397083333334): bits (the "512" part) is emphasized.
- [13:2.289](https://academa.ai/lectures/rsa-factoring-encryption?t=782.2887083333334): bits (the "128" part) is emphasized.
- [13:2.289](https://academa.ai/lectures/rsa-factoring-encryption?t=782.2887083333334): bits (the "512" part) is no longer emphasized.
- [13:3.369](https://academa.ai/lectures/rsa-factoring-encryption?t=783.3687083333334): bits (the "128" part) is no longer emphasized.
- [13:3.369](https://academa.ai/lectures/rsa-factoring-encryption?t=783.3687083333334): bits (the "64" part) is emphasized.

##### [13:5.954](https://academa.ai/lectures/rsa-factoring-encryption?t=785.9537083333335)

Narration: So it is eleven squarings and four multiplications, and that is the whole cost. Do it, and out comes sixty five. The letter A. Exactly the message I sent, not close to it: exactly it, every single time.

Board: rule\_dec — a Math \[text\] that says "$m equiv c^d quad (upright("mod") n)$"; dconc — a Math \[text\] that says "$m equiv 2790^2753 quad (upright("mod") 3233)$"; bits — a Math \[text\] that says "$2753 = 2048 + 512 + 128 + 64 + 1$"; prob2 — a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."

Actions:
- [13:5.954](https://academa.ai/lectures/rsa-factoring-encryption?t=785.9537083333335): bits (the "64" part) is no longer emphasized.
- [13:12.479](https://academa.ai/lectures/rsa-factoring-encryption?t=792.4787083333333): back is shown on the screen, written out.
- [13:14.476](https://academa.ai/lectures/rsa-factoring-encryption?t=794.4757083333334): back is indicated — a transient flash.
- [13:15.475](https://academa.ai/lectures/rsa-factoring-encryption?t=795.4747083333334): A box is drawn around back.

##### [13:21.044](https://academa.ai/lectures/rsa-factoring-encryption?t=801.0437083333334)

Narration: And there is the loop. Raise to e to lock it, raise to d to unlock it. The only thing separating you from everybody else watching the wire is that you know d.

Board: rule\_dec — a Math \[text\] that says "$m equiv c^d quad (upright("mod") n)$"; dconc — a Math \[text\] that says "$m equiv 2790^2753 quad (upright("mod") 3233)$"; bits — a Math \[text\] that says "$2753 = 2048 + 512 + 128 + 64 + 1$"; back — a Math \[text\] that says "$m = 65$"; prob2 — a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."

Actions:
- [13:21.044](https://academa.ai/lectures/rsa-factoring-encryption?t=801.0437083333334): loop is shown on the screen, written out.
- [13:21.044](https://academa.ai/lectures/rsa-factoring-encryption?t=801.0437083333334): lbl\_m is shown on the screen, written out.
- [13:21.044](https://academa.ai/lectures/rsa-factoring-encryption?t=801.0437083333334): lbl\_c is shown on the screen, written out.
- [13:23.679](https://academa.ai/lectures/rsa-factoring-encryption?t=803.6787083333334): up is shown on the screen, written out.
- [13:25.34](https://academa.ai/lectures/rsa-factoring-encryption?t=805.3397083333334): down is shown on the screen, written out.

##### [13:31.988](https://academa.ai/lectures/rsa-factoring-encryption?t=811.9882083333334)

Narration: Which leaves the two questions we have been circling all lecture. Why does the message come back at all? And why can nobody else bring it back?

Board: rule\_dec — a Math \[text\] that says "$m equiv c^d quad (upright("mod") n)$"; dconc — a Math \[text\] that says "$m equiv 2790^2753 quad (upright("mod") 3233)$"; bits — a Math \[text\] that says "$2753 = 2048 + 512 + 128 + 64 + 1$"; back — a Math \[text\] that says "$m = 65$"; loop — a Figure (x\_range=(0, 12), y\_range=(0, 6), aspect=(12, 6)); prob2 — a Tex \[text\] that says "Decrypt $c = 2790$ with $d = 2753$, and recover $m = 65$."; lbl\_m — a Math \[text\] that says "$m = 65$" drawn in loop; lbl\_c — a Math \[text\] that says "$c = 2790$" drawn in loop; up — a CurvedArrow \[red\] labelled "(dot.op)^17" drawn in loop (start=(3.0, 3.4), end=(8.9, 3.4)); down — a CurvedArrow \[green\] labelled "(dot.op)^2753" drawn in loop (start=(8.9, 2.6), end=(3.0, 2.6))

Actions:
- [13:36.679](https://academa.ai/lectures/rsa-factoring-encryption?t=816.6787083333334): down is indicated — a transient flash.
- [13:38.235](https://academa.ai/lectures/rsa-factoring-encryption?t=818.2347083333334): up is indicated — a transient flash.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): back is hidden from the screen — left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): bits is hidden from the screen — left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): dconc is hidden from the screen — left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): loop is hidden from the screen — left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): lbl\_m is hidden from the screen — loop left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): lbl\_c is hidden from the screen — loop left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): up is hidden from the screen — loop left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): down is hidden from the screen — loop left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): prob2 is hidden from the screen — left the board.
- [13:39.953](https://academa.ai/lectures/rsa-factoring-encryption?t=819.9530833333334): rule\_dec is hidden from the screen — left the board.

### Scene 5: [Why It Works, and Why It's Safe](https://academa.ai/lectures/rsa-factoring-encryption?t=820.9947500000001)

Span: 13:40.995–17:56.104 (820.9947500000001s–1076.1035625000002s).

#### Objects

- caveat: a Text \[text\] that says "Everything here is textbook RSA. Real implementations pad the message with structured randomness first, because raw RSA sends the same message to the same ciphertext every time."
- core: a Math \[text\] that says "$c equiv m^e, quad m equiv c^d quad (upright("mod") n)$"
- cost: an Axes (x\_range=(0, 13), y\_range=(0, 1000000), x\_ticks\_every=2)
- curve: a FunctionPlot \[red\] drawn in cost (function=\<function\>, x\_range=(0, 12))
- euler: a Panel that says "If $m$ shares no factor with $n$, then $m^(phi(n)) equiv 1$ modulo $n$. Not nearly one. Exactly one."
- heading1: a Heading that says "Why the Message Comes Back"
- heading2: a Heading that says "Why Nobody Else Can"
- heading3: a Heading that says "The Whole of RSA"
- held: a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."
- p4: a PlotPoint \[yellow\] labelled "10^2" drawn in cost (target='curve', x=4)
- p8: a PlotPoint \[yellow\] labelled "10^4" drawn in cost (target='curve', x=8)
- proof: a Derivation \[text\] that says "$c^d &equiv (m^e)^d = m^(e d) \\ e d &= 17 times 2753 = 46801 = 15 times 3120 + 1 \\ m^(e d) &= (m^3120)^15 times m \\ &equiv 1^15 times m = m$"
- small: a PlotPoint \[green\] labelled "upright("our key")" drawn in cost (target='curve', x=4)
- step1: a Tex \[text\] that says "To read the message you need $d$."
- step2: a Tex \[text\] that says "To get $d$ you need $phi(n)$."
- step3: a Tex \[text\] that says "To get $phi(n)$ you need $p$ and $q$."
- step4: a Tex \[text\] that says "To get $p$ and $q$ you must factor $n$."
- top: a PlotPoint \[yellow\] labelled "10^6" drawn in cost (target='curve', x=12)

#### Beats

##### [13:40.995](https://academa.ai/lectures/rsa-factoring-encryption?t=820.9947500000001)

Narration: So why did the message come back? Raise the ciphertext to d, and out drops exactly the number I started with. Not close to it. That is not luck, and it is not a property of the numbers I happened to pick. It is one theorem.

Board: Empty.

Actions:
- [13:40.995](https://academa.ai/lectures/rsa-factoring-encryption?t=820.9947500000001): heading1 is shown on the screen, written out.
- [13:54.753](https://academa.ai/lectures/rsa-factoring-encryption?t=834.7527500000001): euler is shown on the screen, written out.

##### [13:56.189](https://academa.ai/lectures/rsa-factoring-encryption?t=836.18925)

Narration: Euler's theorem. If m shares no factor with n, then m raised to phi of n is one, modulo n. Not nearly one. Exactly one. Raise almost anything to that one particular power, on that one particular clock, and you land on one.

Board: euler — a Panel that says "If $m$ shares no factor with $n$, then $m^(phi(n)) equiv 1$ modulo $n$. Not nearly one. Exactly one."; heading1 — a Heading that says "Why the Message Comes Back"

Actions:
- [14:1.1](https://academa.ai/lectures/rsa-factoring-encryption?t=841.0997500000001): euler (the "$m^(phi(n)) equiv 1$" part) is emphasized.
- [14:5.86](https://academa.ai/lectures/rsa-factoring-encryption?t=845.8597500000001): euler (the "$m^(phi(n)) equiv 1$" part) is no longer emphasized.
- [14:5.86](https://academa.ai/lectures/rsa-factoring-encryption?t=845.8597500000001): euler (the "Exactly one" part) is emphasized.

##### [14:14.494](https://academa.ai/lectures/rsa-factoring-encryption?t=854.4942500000001)

Narration: Now watch what decryption actually is. c to the d is m to the e, all raised to the d, which is simply m to the e times d.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [14:14.494](https://academa.ai/lectures/rsa-factoring-encryption?t=854.4942500000001): euler (the "Exactly one" part) is no longer emphasized.
- [14:15.109](https://academa.ai/lectures/rsa-factoring-encryption?t=855.1087500000001): proof is shown on the screen, written out.

##### [14:24.173](https://academa.ai/lectures/rsa-factoring-encryption?t=864.1727500000001)

Narration: So what is e times d? Seventeen times two thousand seven hundred and fifty three, which is this number. But we chose d precisely so that this product would be one more than a multiple of phi of n. And there it is: fifteen lots of the totient, plus one.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [14:26.437](https://academa.ai/lectures/rsa-factoring-encryption?t=866.4367500000001): proof is shown on the screen, written out.
- [14:26.437](https://academa.ai/lectures/rsa-factoring-encryption?t=866.4367500000001): proof (the "17 times 2753" part) is emphasized.
- [14:30.094](https://academa.ai/lectures/rsa-factoring-encryption?t=870.0937500000001): proof (the "17 times 2753" part) is no longer emphasized.
- [14:30.094](https://academa.ai/lectures/rsa-factoring-encryption?t=870.0937500000001): proof (the "46801" part) is emphasized.
- [14:38.105](https://academa.ai/lectures/rsa-factoring-encryption?t=878.1047500000001): proof (the "15 times 3120 + 1" part) is emphasized.
- [14:38.105](https://academa.ai/lectures/rsa-factoring-encryption?t=878.1047500000001): proof (the "46801" part) is no longer emphasized.

##### [14:41.206](https://academa.ai/lectures/rsa-factoring-encryption?t=881.2062500000001)

Narration: So m to the e d is m to the fifteen times the totient, times one more m. Which I can regroup: m to the totient, all raised to the fifteenth, times m.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [14:41.206](https://academa.ai/lectures/rsa-factoring-encryption?t=881.2062500000001): proof (the "15 times 3120 + 1" part) is no longer emphasized.
- [14:47.841](https://academa.ai/lectures/rsa-factoring-encryption?t=887.8407500000001): proof is shown on the screen, written out.

##### [14:52.957](https://academa.ai/lectures/rsa-factoring-encryption?t=892.95725)

Narration: And that bracket is Euler's theorem staring back at us. It is one. One to the fifteenth is one. So the whole expression collapses to m, every time, for every message under the sun. Decryption is not a lucky inverse. It is a theorem.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [14:53.701](https://academa.ai/lectures/rsa-factoring-encryption?t=893.7007500000001): proof (the "(m^3120)^15" part) is emphasized.
- [15:0.435](https://academa.ai/lectures/rsa-factoring-encryption?t=900.4347500000001): proof is shown on the screen, written out.
- [15:6.414](https://academa.ai/lectures/rsa-factoring-encryption?t=906.41375): A box is drawn around proof.
- [15:7.622](https://academa.ai/lectures/rsa-factoring-encryption?t=907.62175): proof (the "(m^3120)^15" part) is no longer emphasized.
- [15:8.446](https://academa.ai/lectures/rsa-factoring-encryption?t=908.4457500000001): euler is hidden from the screen — left the board.
- [15:8.446](https://academa.ai/lectures/rsa-factoring-encryption?t=908.4457500000001): heading1 is hidden from the screen — left the board.
- [15:8.446](https://academa.ai/lectures/rsa-factoring-encryption?t=908.4457500000001): proof is hidden from the screen — left the board.

##### [15:9.646](https://academa.ai/lectures/rsa-factoring-encryption?t=909.6457500000001)

Narration: Right. Now the other half. Why can nobody else do that? Put yourself on the outside: you have n, you have e, and you have the ciphertext going past on the wire. That is everything. What do you actually need?

Board: Empty.

Actions:
- [15:9.646](https://academa.ai/lectures/rsa-factoring-encryption?t=909.6457500000001): heading2 is shown on the screen, written out.
- [15:15.195](https://academa.ai/lectures/rsa-factoring-encryption?t=915.1947500000001): held is shown on the screen, written out.

##### [15:25.06](https://academa.ai/lectures/rsa-factoring-encryption?t=925.0597500000001)

Narration: You need d. That is the only exponent that undoes seventeen on this particular clock, and without it the ciphertext is just a number.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; heading2 — a Heading that says "Why Nobody Else Can"

Actions:
- [15:25.617](https://academa.ai/lectures/rsa-factoring-encryption?t=925.61675): step1 is shown on the screen, written out.

##### [15:33.961](https://academa.ai/lectures/rsa-factoring-encryption?t=933.9607500000001)

Narration: To compute d you need phi of n, because d was defined by that congruence: e d is one, modulo phi of n. No phi, no d.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; step1 — a Tex \[text\] that says "To read the message you need $d$."; heading2 — a Heading that says "Why Nobody Else Can"

Actions:
- [15:34.437](https://academa.ai/lectures/rsa-factoring-encryption?t=934.4367500000001): step2 is shown on the screen, written out.

##### [15:44.377](https://academa.ai/lectures/rsa-factoring-encryption?t=944.3767500000001)

Narration: To compute phi of n you need p and q, because phi of n is p minus one times q minus one. There is no other route to it. Knowing n is not enough.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; step1 — a Tex \[text\] that says "To read the message you need $d$."; step2 — a Tex \[text\] that says "To get $d$ you need $phi(n)$."; heading2 — a Heading that says "Why Nobody Else Can"

Actions:
- [15:44.766](https://academa.ai/lectures/rsa-factoring-encryption?t=944.76575): step3 is shown on the screen, written out.

##### [15:56.61](https://academa.ai/lectures/rsa-factoring-encryption?t=956.6102500000001)

Narration: And to get p and q out of n, you have to factor n. That is the last link, and every link in the chain is forced. There is no way in from the side.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; step1 — a Tex \[text\] that says "To read the message you need $d$."; step2 — a Tex \[text\] that says "To get $d$ you need $phi(n)$."; step3 — a Tex \[text\] that says "To get $phi(n)$ you need $p$ and $q$."; heading2 — a Heading that says "Why Nobody Else Can"

Actions:
- [15:59.205](https://academa.ai/lectures/rsa-factoring-encryption?t=959.2047500000001): step4 is shown on the screen, written out.

##### [16:6.725](https://academa.ai/lectures/rsa-factoring-encryption?t=966.7247500000001)

Narration: So how hard is factoring, really? Here is trial division again, plotted against the number of digits. Four digits, about a hundred steps. Eight digits, ten thousand. Twelve digits, a million, and the curve has already left the top of the board.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; step1 — a Tex \[text\] that says "To read the message you need $d$."; step2 — a Tex \[text\] that says "To get $d$ you need $phi(n)$."; step3 — a Tex \[text\] that says "To get $phi(n)$ you need $p$ and $q$."; step4 — a Tex \[text\] that says "To get $p$ and $q$ you must factor $n$."; heading2 — a Heading that says "Why Nobody Else Can"

Actions:
- [16:9.395](https://academa.ai/lectures/rsa-factoring-encryption?t=969.39475): cost is shown on the screen, written out.
- [16:11.253](https://academa.ai/lectures/rsa-factoring-encryption?t=971.2527500000001): curve is shown on the screen, drawn.
- [16:13.737](https://academa.ai/lectures/rsa-factoring-encryption?t=973.73675): p4 is shown on the screen, written out.
- [16:16.512](https://academa.ai/lectures/rsa-factoring-encryption?t=976.5117500000001): p8 is shown on the screen, written out.
- [16:20.285](https://academa.ai/lectures/rsa-factoring-encryption?t=980.28475): top is shown on the screen, written out.

##### [16:24.379](https://academa.ai/lectures/rsa-factoring-encryption?t=984.3792500000001)

Narration: Now imagine putting six hundred and seventeen digits on that axis. This curve was off the board at twelve. Out there, trial division needs the number we met in the first minute, the one bigger than the atoms in the universe. The best method anybody knows does enormously better, and it is still nowhere near enough.

Board: held — a Tex \[text\] that says "You have $n$, $e$, and the ciphertext."; step1 — a Tex \[text\] that says "To read the message you need $d$."; step2 — a Tex \[text\] that says "To get $d$ you need $phi(n)$."; step3 — a Tex \[text\] that says "To get $phi(n)$ you need $p$ and $q$."; step4 — a Tex \[text\] that says "To get $p$ and $q$ you must factor $n$."; cost — an Axes (x\_range=(0, 13), y\_range=(0, 1000000), x\_ticks\_every=2); heading2 — a Heading that says "Why Nobody Else Can"; curve — a FunctionPlot \[red\] drawn in cost (function=\<function\>, x\_range=(0, 12)); p4 — a PlotPoint \[yellow\] labelled "10^2" drawn in cost (target='curve', x=4); p8 — a PlotPoint \[yellow\] labelled "10^4" drawn in cost (target='curve', x=8); top — a PlotPoint \[yellow\] labelled "10^6" drawn in cost (target='curve', x=12)

Actions:
- [16:27.7](https://academa.ai/lectures/rsa-factoring-encryption?t=987.6997500000001): The x axis of cost is lit up.
- [16:30.231](https://academa.ai/lectures/rsa-factoring-encryption?t=990.2307500000001): top is indicated — a transient flash.

##### [16:44.066](https://academa.ai/lectures/rsa-factoring-encryption?t=1004.0662500000001)

Narration: And notice the flip side of all this. My key is a toy. Its modulus has a factor under sixty, and you could break it on paper over a cup of coffee. That is not a flaw in RSA. It is the entire reason the real numbers have to be enormous.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [16:44.066](https://academa.ai/lectures/rsa-factoring-encryption?t=1004.0662500000001): p4 is hidden from the screen.
- [16:44.066](https://academa.ai/lectures/rsa-factoring-encryption?t=1004.0662500000001): p8 is hidden from the screen.
- [16:48.037](https://academa.ai/lectures/rsa-factoring-encryption?t=1008.0367500000001): small is shown on the screen, written out.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): cost is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): curve is hidden from the screen — cost left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): top is hidden from the screen — cost left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): small is hidden from the screen — cost left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): heading2 is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): held is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): step1 is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): step2 is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): step3 is hidden from the screen — left the board.
- [17:0.122](https://academa.ai/lectures/rsa-factoring-encryption?t=1020.1222500000001): step4 is hidden from the screen — left the board.

##### [17:1.322](https://academa.ai/lectures/rsa-factoring-encryption?t=1021.32225)

Narration: So that is RSA, complete. Encrypt by raising the message to e. Decrypt by raising the ciphertext to d. Both modulo n, and both cheap. The public key hands out n, and n is the product of two primes that it will not give up.

Board: Empty.

Actions:
- [17:1.322](https://academa.ai/lectures/rsa-factoring-encryption?t=1021.32225): heading3 is shown on the screen, written out.
- [17:2.902](https://academa.ai/lectures/rsa-factoring-encryption?t=1022.9017500000001): core is shown on the screen, written out.
- [17:3.935](https://academa.ai/lectures/rsa-factoring-encryption?t=1023.9347500000001): core (the "m^e" part) is emphasized.
- [17:7.035](https://academa.ai/lectures/rsa-factoring-encryption?t=1027.03475): core (the "c^d" part) is emphasized.
- [17:7.035](https://academa.ai/lectures/rsa-factoring-encryption?t=1027.03475): core (the "m^e" part) is no longer emphasized.
- [17:12.585](https://academa.ai/lectures/rsa-factoring-encryption?t=1032.58475): core (the "c^d" part) is no longer emphasized.

##### [17:19.837](https://academa.ai/lectures/rsa-factoring-encryption?t=1039.83725)

Narration: One honest footnote before you go and implement this, because you should not implement this. What I have shown you is textbook RSA. Every real library pads the message with structured randomness before encrypting, because raw RSA has an obvious hole: the same message always produces the same ciphertext.

Board: core — a Math \[text\] that says "$c equiv m^e, quad m equiv c^d quad (upright("mod") n)$"; heading3 — a Heading that says "The Whole of RSA"

Actions:
- [17:20.824](https://academa.ai/lectures/rsa-factoring-encryption?t=1040.82375): caveat is shown on the screen, written out.

##### [17:39.768](https://academa.ai/lectures/rsa-factoring-encryption?t=1059.76825)

Narration: The mathematics is exactly what you have just watched. The padding is what makes it safe to hand to strangers. And the wall the whole thing leans on has not changed since the first minute of this lecture. Multiplying is easy. Going the other way is not.

Board: core — a Math \[text\] that says "$c equiv m^e, quad m equiv c^d quad (upright("mod") n)$"; caveat — a Text \[text\] that says "Everything here is textbook RSA. Real implementations pad the message with structured randomness first, because raw RSA sends the same message to the same ciphertext every time."; heading3 — a Heading that says "The Whole of RSA"

Actions:
- [17:40.198](https://academa.ai/lectures/rsa-factoring-encryption?t=1060.19775): A box is drawn around core.
- [17:55.062](https://academa.ai/lectures/rsa-factoring-encryption?t=1075.0618958333334): caveat is hidden from the screen — left the board.
- [17:55.062](https://academa.ai/lectures/rsa-factoring-encryption?t=1075.0618958333334): core is hidden from the screen — left the board.
- [17:55.062](https://academa.ai/lectures/rsa-factoring-encryption?t=1075.0618958333334): heading3 is hidden from the screen — left the board.