[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.53,0:00:03.12,Default,,0000,0000,0000,,In the previous segment, we talked about modulo inversion,
Dialogue: 0,0:00:03.12,0:00:04.93,Default,,0000,0000,0000,,and we said that Euclid's algorithm gives us
Dialogue: 0,0:00:04.93,0:00:08.90,Default,,0000,0000,0000,,an efficient method to find the inverse of an element modulo m.
Dialogue: 0,0:00:08.90,0:00:11.27,Default,,0000,0000,0000,,In this segment we are going to forward through time
Dialogue: 0,0:00:11.27,0:00:15.06,Default,,0000,0000,0000,,and we're going to move to the 17th and 18th century
Dialogue: 0,0:00:15.06,0:00:16.35,Default,,0000,0000,0000,,and we're going to talk about Fermat's and Euler's contributions.
Dialogue: 0,0:00:16.35,0:00:20.86,Default,,0000,0000,0000,,Before that, let's do a quick review of what we discussed in the previous segment.
Dialogue: 0,0:00:20.86,0:00:23.82,Default,,0000,0000,0000,,So as usual, we're going to let N denote a positive integer,
Dialogue: 0,0:00:23.82,0:00:27.08,Default,,0000,0000,0000,,and let's just say that N happens to be a n-bit integer.
Dialogue: 0,0:00:27.16,0:00:30.22,Default,,0000,0000,0000,,In other words, it's between 2^n and 2^(n+1).
Dialogue: 0,0:00:30.22,0:00:32.84,Default,,0000,0000,0000,,As usual we are going to let p denote a prime.
Dialogue: 0,0:00:32.84,0:00:37.52,Default,,0000,0000,0000,,Now we said that Z sub n is the set of integers from 0 to N - 1.
Dialogue: 0,0:00:37.52,0:00:41.07,Default,,0000,0000,0000,,And we said that we can add and multiply elements in the set modulo N.
Dialogue: 0,0:00:41.07,0:00:45.68,Default,,0000,0000,0000,,We also said the Z_N* is basically the set of invertible elements
Dialogue: 0,0:00:45.68,0:00:50.04,Default,,0000,0000,0000,,in Z_N and we proved the simple lemma to say that x is invertible
Dialogue: 0,0:00:50.04,0:00:52.93,Default,,0000,0000,0000,,if and only if x is relatively prime to n.
Dialogue: 0,0:00:52.93,0:00:57.40,Default,,0000,0000,0000,,And not only did we completely understand which elements are invertible
Dialogue: 0,0:00:57.40,0:00:58.42,Default,,0000,0000,0000,,and which aren't,
Dialogue: 0,0:00:58.42,0:01:02.11,Default,,0000,0000,0000,,we also showed a very efficient algorithm, based on Euclid's extended algorithm,
Dialogue: 0,0:01:02.11,0:01:05.36,Default,,0000,0000,0000,,to find the inverse of an element x in Z_N.
Dialogue: 0,0:01:05.36,0:01:09.69,Default,,0000,0000,0000,,And we said that the running time of this algorithm is basically of order n-squared
Dialogue: 0,0:01:09.69,0:01:13.46,Default,,0000,0000,0000,,where again n is the number of bits of the number capital N.
Dialogue: 0,0:01:14.46,0:01:18.52,Default,,0000,0000,0000,,So as I said, now we're gonna move from Greek times all the way to
Dialogue: 0,0:01:18.52,0:01:21.08,Default,,0000,0000,0000,,the 17th century and talk about Fermat.
Dialogue: 0,0:01:21.08,0:01:23.96,Default,,0000,0000,0000,,So Fermat stated a number of important theorems.
Dialogue: 0,0:01:23.96,0:01:26.64,Default,,0000,0000,0000,,The one that I want to show you here is the following:
Dialogue: 0,0:01:26.64,0:01:28.99,Default,,0000,0000,0000,,So suppose I give you a prime "p".
Dialogue: 0,0:01:28.99,0:01:33.12,Default,,0000,0000,0000,,Then in fact, for any element x in in Z_p*, it so happens
Dialogue: 0,0:01:33.12,0:01:36.85,Default,,0000,0000,0000,,that if I look at x and raise it to the power p-1,
Dialogue: 0,0:01:36.85,0:01:38.95,Default,,0000,0000,0000,,I'm gonna get 1 in Z_p.
Dialogue: 0,0:01:38.95,0:01:41.83,Default,,0000,0000,0000,,So let's look at a quick example.
Dialogue: 0,0:01:41.83,0:01:44.11,Default,,0000,0000,0000,,Suppose I set the number p to be 5
Dialogue: 0,0:01:44.11,0:01:50.24,Default,,0000,0000,0000,,and I look at 3 to the power of p-1 - in other words 3 to the power of 4 -
Dialogue: 0,0:01:50.24,0:01:53.62,Default,,0000,0000,0000,,3^4 is 81, which in fact is 1 modulo 5.
Dialogue: 0,0:01:53.62,0:01:56.79,Default,,0000,0000,0000,,The example satisfies Fermat's theorem.
Dialogue: 0,0:01:56.79,0:02:00.05,Default,,0000,0000,0000,,Interestingly Fermat actually didn't prove this theorem himself.
Dialogue: 0,0:02:00.05,0:02:04.76,Default,,0000,0000,0000,,The proof actually waited until Euler, who proved it almost a 100 years later
Dialogue: 0,0:02:04.76,0:02:07.38,Default,,0000,0000,0000,,and in fact he proved a much more general version of this theorem.
Dialogue: 0,0:02:08.69,0:02:10.84,Default,,0000,0000,0000,,So lets look at a simple application of Fermat's theorem.
Dialogue: 0,0:02:11.25,0:02:14.31,Default,,0000,0000,0000,,Suppose I look at an element x in Z_p*,
Dialogue: 0,0:02:14.31,0:02:17.50,Default,,0000,0000,0000,,and I want to remind you here that p must be a prime.
Dialogue: 0,0:02:17.50,0:02:21.85,Default,,0000,0000,0000,,Well, then what do we know? We know that x^(p-1) = 1.
Dialogue: 0,0:02:21.91,0:02:27.90,Default,,0000,0000,0000,,Well, we can write x^(p-1) as x*x^(p-2).
Dialogue: 0,0:02:27.90,0:02:32.90,Default,,0000,0000,0000,,Well, so now we know that x*x^(p-2) happens to be equal to 1,
Dialogue: 0,0:02:32.90,0:02:37.15,Default,,0000,0000,0000,,and what that says is that really the inverse of x modulo p
Dialogue: 0,0:02:37.15,0:02:39.44,Default,,0000,0000,0000,,is simply x^(p-2).
Dialogue: 0,0:02:39.44,0:02:43.92,Default,,0000,0000,0000,,So this gives us another algorithm for finding the inverse of x modulo a prime:
Dialogue: 0,0:02:43.92,0:02:46.86,Default,,0000,0000,0000,,simply raise x the power of p-2
Dialogue: 0,0:02:46.86,0:02:48.90,Default,,0000,0000,0000,,and that will give us the inverse of x.
Dialogue: 0,0:02:48.90,0:02:53.35,Default,,0000,0000,0000,,It turns out actually this is a fine way to compute inverses modulo a prime,
Dialogue: 0,0:02:53.35,0:02:57.05,Default,,0000,0000,0000,,but it has 2 deficiencies compared to Euclid's algorithm.
Dialogue: 0,0:02:57.05,0:02:59.51,Default,,0000,0000,0000,,First of all, it only works modulo primes,
Dialogue: 0,0:02:59.51,0:03:02.72,Default,,0000,0000,0000,,whereas Euclid's algorithm worked modulo composites as well,
Dialogue: 0,0:03:02.72,0:03:06.24,Default,,0000,0000,0000,,and second of all it turns out this algorithm is actually less efficient.
Dialogue: 0,0:03:06.24,0:03:09.25,Default,,0000,0000,0000,,When we talk about how to do modular exponentiation
Dialogue: 0,0:03:09.25,0:03:11.50,Default,,0000,0000,0000,,- we're gonna do that in the last segment in this module -
Dialogue: 0,0:03:11.50,0:03:14.83,Default,,0000,0000,0000,,you'll see that the running time to compute this exponentiation
Dialogue: 0,0:03:14.83,0:03:18.12,Default,,0000,0000,0000,,is actually cubic in the size of p,
Dialogue: 0,0:03:18.12,0:03:20.54,Default,,0000,0000,0000,,so this will take roughly log^3(p),
Dialogue: 0,0:03:20.54,0:03:22.86,Default,,0000,0000,0000,,whereas, if you remember, Euclid's algorithm was able
Dialogue: 0,0:03:22.86,0:03:25.23,Default,,0000,0000,0000,,to compute the inverse in quadratic time
Dialogue: 0,0:03:25.23,0:03:27.17,Default,,0000,0000,0000,,in the representation of p.
Dialogue: 0,0:03:28.69,0:03:32.01,Default,,0000,0000,0000,,So not only is this algorithm less general
Dialogue: 0,0:03:32.01,0:03:33.59,Default,,0000,0000,0000,,- it only works for primes -
Dialogue: 0,0:03:33.59,0:03:36.62,Default,,0000,0000,0000,,it's also less efficient.
Dialogue: 0,0:03:36.62,0:03:38.26,Default,,0000,0000,0000,,So score one for Euclid,
Dialogue: 0,0:03:38.26,0:03:42.56,Default,,0000,0000,0000,,but nevertheless, this fact about primes is extremely important
Dialogue: 0,0:03:42.56,0:03:44.56,Default,,0000,0000,0000,,and we're going to be making extensive use of it
Dialogue: 0,0:03:44.56,0:03:47.77,Default,,0000,0000,0000,,in the next couple of weeks.
Dialogue: 0,0:03:47.77,0:03:51.34,Default,,0000,0000,0000,,So let me show you a quick and simple application of Fermat's theorem.
Dialogue: 0,0:03:51.34,0:03:53.61,Default,,0000,0000,0000,,Suppose we wanted to generate a large random prime.
Dialogue: 0,0:03:53.61,0:03:57.86,Default,,0000,0000,0000,,Say our prime needed to be 1000 bits or so.
Dialogue: 0,0:03:57.86,0:04:02.59,Default,,0000,0000,0000,,So the prime we're looking for is on the order of 2^1024, say.
Dialogue: 0,0:04:02.59,0:04:05.08,Default,,0000,0000,0000,,So here is a very simple probabilistic algorithm:
Dialogue: 0,0:04:05.08,0:04:07.81,Default,,0000,0000,0000,,What we would do is, we would choose a random integer
Dialogue: 0,0:04:07.81,0:04:10.54,Default,,0000,0000,0000,,in the interval that was specified,
Dialogue: 0,0:04:10.54,0:04:15.44,Default,,0000,0000,0000,,and then we would test whether this integer satisfies Fermat's theorem.
Dialogue: 0,0:04:15.44,0:04:16.61,Default,,0000,0000,0000,,In other words, we would test -
Dialogue: 0,0:04:16.61,0:04:18.37,Default,,0000,0000,0000,,for example, using the base 2,
Dialogue: 0,0:04:18.37,0:04:22.93,Default,,0000,0000,0000,,we would test whether 2^(p-1) equals 1 in Z_p.
Dialogue: 0,0:04:22.93,0:04:26.10,Default,,0000,0000,0000,,If the answer is no, if this equality doesn't hold,
Dialogue: 0,0:04:26.10,0:04:30.62,Default,,0000,0000,0000,,then we know for sure that the number p that we chose is not a prime.
Dialogue: 0,0:04:30.62,0:04:34.80,Default,,0000,0000,0000,,And if that happens, all we do is we go back to step 1
Dialogue: 0,0:04:34.80,0:04:36.21,Default,,0000,0000,0000,,and we try another prime.
Dialogue: 0,0:04:36.21,0:04:37.75,Default,,0000,0000,0000,,We do this again and again and again,
Dialogue: 0,0:04:37.75,0:04:41.86,Default,,0000,0000,0000,,until finally we find an integer that satisfies this condition.
Dialogue: 0,0:04:41.86,0:04:43.91,Default,,0000,0000,0000,,And once we find an integer that satisfies this condition,
Dialogue: 0,0:04:43.91,0:04:48.03,Default,,0000,0000,0000,,we simply output it and stop.
Dialogue: 0,0:04:48.03,0:04:49.32,Default,,0000,0000,0000,,Now it turns out
Dialogue: 0,0:04:49.32,0:04:51.30,Default,,0000,0000,0000,,- this is actually a fairly difficult statement to prove -
Dialogue: 0,0:04:51.30,0:04:54.84,Default,,0000,0000,0000,,but it turns out, if a random number passes this test,
Dialogue: 0,0:04:54.84,0:04:57.09,Default,,0000,0000,0000,,then it's extremely likely to be a prime.
Dialogue: 0,0:04:57.09,0:04:59.62,Default,,0000,0000,0000,,In particular, the probability that p is not a prime
Dialogue: 0,0:04:59.62,0:05:01.08,Default,,0000,0000,0000,,is very small.
Dialogue: 0,0:05:01.08,0:05:05.54,Default,,0000,0000,0000,,It's, like, less than 2^-60 for the range of 1024-bit numbers.
Dialogue: 0,0:05:05.54,0:05:08.08,Default,,0000,0000,0000,,As the number gets bigger and bigger,
Dialogue: 0,0:05:08.08,0:05:09.61,Default,,0000,0000,0000,,the probability that it passes this test here,
Dialogue: 0,0:05:09.61,0:05:16.01,Default,,0000,0000,0000,,but is not a prime, drops to zero very quickly.
Dialogue: 0,0:05:16.01,0:05:17.10,Default,,0000,0000,0000,,So this is actually quite an interesting algorithm.
Dialogue: 0,0:05:17.10,0:05:21.14,Default,,0000,0000,0000,,You realize: we're not guaranteed that the output is in fact a prime.
Dialogue: 0,0:05:21.14,0:05:24.01,Default,,0000,0000,0000,,All we know is that it's very very likely to be a prime.
Dialogue: 0,0:05:24.01,0:05:26.18,Default,,0000,0000,0000,,In other words: the only way that it's not a prime
Dialogue: 0,0:05:26.18,0:05:28.27,Default,,0000,0000,0000,,is that we got extremely unlucky.
Dialogue: 0,0:05:28.27,0:05:34.01,Default,,0000,0000,0000,,In fact, so unlucky that a negligible-probability event just happened.
Dialogue: 0,0:05:34.01,0:05:35.91,Default,,0000,0000,0000,,Another way to say this is that,
Dialogue: 0,0:05:35.91,0:05:39.37,Default,,0000,0000,0000,,if you look at the set of all 1024-bit integers,
Dialogue: 0,0:05:39.37,0:05:43.74,Default,,0000,0000,0000,,then, well, there is the set of primes, when we write "prime" here,
Dialogue: 0,0:05:43.74,0:05:46.36,Default,,0000,0000,0000,,and then there is a small number of composites
Dialogue: 0,0:05:46.36,0:05:48.33,Default,,0000,0000,0000,,that actually will falsify the test,
Dialogue: 0,0:05:48.33,0:05:51.07,Default,,0000,0000,0000,,let's call them F for "false primes".
Dialogue: 0,0:05:51.07,0:05:54.20,Default,,0000,0000,0000,,Let's call them FP, for "false primes".
Dialogue: 0,0:05:54.20,0:05:56.13,Default,,0000,0000,0000,,There is a very small number of composites
Dialogue: 0,0:05:56.13,0:05:58.100,Default,,0000,0000,0000,,that are not prime and yet will pass this test,
Dialogue: 0,0:05:58.100,0:06:01.85,Default,,0000,0000,0000,,but as we choose random integers
Dialogue: 0,0:06:01.85,0:06:04.66,Default,,0000,0000,0000,,- you know, we choose one here and one here, and so on -
Dialogue: 0,0:06:04.66,0:06:05.92,Default,,0000,0000,0000,,as we choose random integers,
Dialogue: 0,0:06:05.92,0:06:09.04,Default,,0000,0000,0000,,the probability that we fall into this set of false primes
Dialogue: 0,0:06:09.04,0:06:12.95,Default,,0000,0000,0000,,is so small that it's essentially a negligible event
Dialogue: 0,0:06:12.95,0:06:14.54,Default,,0000,0000,0000,,that we can ignore.
Dialogue: 0,0:06:14.54,0:06:17.04,Default,,0000,0000,0000,,In other words, one can prove that the set of false primes
Dialogue: 0,0:06:17.04,0:06:18.53,Default,,0000,0000,0000,,is extremely small,
Dialogue: 0,0:06:18.53,0:06:24.14,Default,,0000,0000,0000,,and a random choice is unlikely to pick such a false prime.
Dialogue: 0,0:06:24.14,0:06:24.74,Default,,0000,0000,0000,,Now I should mention,
Dialogue: 0,0:06:24.74,0:06:27.59,Default,,0000,0000,0000,,in fact, this is a very simple algorithm for generating primes.
Dialogue: 0,0:06:27.59,0:06:29.79,Default,,0000,0000,0000,,It's actually by far not the best algorithm.
Dialogue: 0,0:06:29.79,0:06:31.74,Default,,0000,0000,0000,,We have much better algorithms now.
Dialogue: 0,0:06:31.74,0:06:33.24,Default,,0000,0000,0000,,And in fact, once you have a candidate prime
Dialogue: 0,0:06:33.24,0:06:35.27,Default,,0000,0000,0000,,we now have very efficient algorithms
Dialogue: 0,0:06:35.27,0:06:37.07,Default,,0000,0000,0000,,that will actually prove beyond a doubt
Dialogue: 0,0:06:37.07,0:06:40.33,Default,,0000,0000,0000,,that this candidate prime really is a prime.
Dialogue: 0,0:06:40.33,0:06:43.00,Default,,0000,0000,0000,,So we don't even have to rely on probabilistic statements.
Dialogue: 0,0:06:43.00,0:06:43.58,Default,,0000,0000,0000,,And nevertheless,
Dialogue: 0,0:06:43.58,0:06:44.84,Default,,0000,0000,0000,,this Fermat test is so simple
Dialogue: 0,0:06:44.84,0:06:46.42,Default,,0000,0000,0000,,that I just wanted to show you
Dialogue: 0,0:06:46.42,0:06:48.40,Default,,0000,0000,0000,,that it's an easy way to generate primes
Dialogue: 0,0:06:48.40,0:06:52.08,Default,,0000,0000,0000,,although in reality this is not how primes are generated.
Dialogue: 0,0:06:52.08,0:06:54.34,Default,,0000,0000,0000,,As a last point, I'll say that
Dialogue: 0,0:06:54.34,0:06:56.97,Default,,0000,0000,0000,,you might be wondering how many times this iteration
Dialogue: 0,0:06:56.97,0:07:00.00,Default,,0000,0000,0000,,has to repeat until we actually find a prime.
Dialogue: 0,0:07:00.00,0:07:01.47,Default,,0000,0000,0000,,And that's actually a classic result,
Dialogue: 0,0:07:01.47,0:07:02.88,Default,,0000,0000,0000,,it's called the Prime Number Theorem
Dialogue: 0,0:07:02.88,0:07:03.88,Default,,0000,0000,0000,,which says that
Dialogue: 0,0:07:03.88,0:07:05.34,Default,,0000,0000,0000,,after a few hundred iterations
Dialogue: 0,0:07:05.34,0:07:08.68,Default,,0000,0000,0000,,we'll find a prime with high probability.
Dialogue: 0,0:07:08.68,0:07:10.34,Default,,0000,0000,0000,,So expectation, one would expect
Dialogue: 0,0:07:10.34,0:07:14.08,Default,,0000,0000,0000,,a few hundred iterations, no more.
Dialogue: 0,0:07:14.08,0:07:15.93,Default,,0000,0000,0000,,Now that we understand Fermat's theorem,
Dialogue: 0,0:07:15.93,0:07:17.61,Default,,0000,0000,0000,,the next thing I want to talk about is
Dialogue: 0,0:07:17.61,0:07:20.21,Default,,0000,0000,0000,,what's called the structure of (Z_p)*.
Dialogue: 0,0:07:20.21,0:07:22.12,Default,,0000,0000,0000,,So here we're going to move a hundred years into the future,
Dialogue: 0,0:07:22.12,0:07:23.74,Default,,0000,0000,0000,,into the 18th century,
Dialogue: 0,0:07:23.74,0:07:25.52,Default,,0000,0000,0000,,and look at the work of Euler.
Dialogue: 0,0:07:25.52,0:07:27.28,Default,,0000,0000,0000,,And one of the first things Euler showed
Dialogue: 0,0:07:27.28,0:07:29.33,Default,,0000,0000,0000,,is, in modern language,
Dialogue: 0,0:07:29.33,0:07:32.81,Default,,0000,0000,0000,,is that (Z_p)* is what's called a cyclic group.
Dialogue: 0,0:07:32.81,0:07:35.47,Default,,0000,0000,0000,,So what does it mean that (Z_p)* is a cyclic group?
Dialogue: 0,0:07:35.47,0:07:36.08,Default,,0000,0000,0000,,What it means is:
Dialogue: 0,0:07:36.08,0:07:39.77,Default,,0000,0000,0000,,there exists some element g in (Z_p)*
Dialogue: 0,0:07:39.77,0:07:43.37,Default,,0000,0000,0000,,such that if we take g and raise it to a bunch of powers,
Dialogue: 0,0:07:43.37,0:07:47.10,Default,,0000,0000,0000,,g, g^2, g^3, g^4 and so on and so forth
Dialogue: 0,0:07:47.10,0:07:50.67,Default,,0000,0000,0000,,up until we reach g^(p-2)
Dialogue: 0,0:07:50.67,0:07:53.16,Default,,0000,0000,0000,,- notice there is no point of going beyond g^(p-2)
Dialogue: 0,0:07:53.16,0:07:57.80,Default,,0000,0000,0000,,because g^(p-1) by Fermat's theorem is equal to 1,
Dialogue: 0,0:07:57.80,0:08:00.21,Default,,0000,0000,0000,,so then we will cycle back to 1
Dialogue: 0,0:08:00.21,0:08:02.22,Default,,0000,0000,0000,,if we go back to g^(p-1),
Dialogue: 0,0:08:02.22,0:08:04.65,Default,,0000,0000,0000,,then g^p will be equal to g,
Dialogue: 0,0:08:04.65,0:08:07.42,Default,,0000,0000,0000,,g^(p+1) will be equal to g^2, and so on and so forth,
Dialogue: 0,0:08:07.42,0:08:08.60,Default,,0000,0000,0000,,so we'll actually get a cycle
Dialogue: 0,0:08:08.60,0:08:11.53,Default,,0000,0000,0000,,if we keep raising to higher and higher powers of g,
Dialogue: 0,0:08:11.53,0:08:17.34,Default,,0000,0000,0000,,so we might as well stop at the power of g^(p-2).
Dialogue: 0,0:08:17.34,0:08:18.37,Default,,0000,0000,0000,,And what Euler showed is
Dialogue: 0,0:08:18.37,0:08:20.34,Default,,0000,0000,0000,,that in fact there is an element g
Dialogue: 0,0:08:20.34,0:08:22.73,Default,,0000,0000,0000,,such that if we look at all of its powers,
Dialogue: 0,0:08:22.73,0:08:26.93,Default,,0000,0000,0000,,all of its powers span the entire group (Z_p)*.
Dialogue: 0,0:08:26.93,0:08:30.82,Default,,0000,0000,0000,,Powers of g give us all the elements in (Z_p)*.
Dialogue: 0,0:08:30.82,0:08:33.34,Default,,0000,0000,0000,,An element of this type is called a generator.
Dialogue: 0,0:08:33.34,0:08:36.85,Default,,0000,0000,0000,,So g would be said to be a generator of (Z_p)*.
Dialogue: 0,0:08:36.85,0:08:38.03,Default,,0000,0000,0000,,So let's look at a quick example.
Dialogue: 0,0:08:38.03,0:08:40.39,Default,,0000,0000,0000,,Let's look for example at p=7,
Dialogue: 0,0:08:40.39,0:08:43.54,Default,,0000,0000,0000,,and let's look at all the powers of 3,
Dialogue: 0,0:08:43.54,0:08:47.01,Default,,0000,0000,0000,,which are 3^2, 3^3, 3^4, 3^5.
Dialogue: 0,0:08:47.01,0:08:51.79,Default,,0000,0000,0000,,3^6 already, we know, is equal to 1 modulo 7 by Fermat's theorem,
Dialogue: 0,0:08:51.79,0:08:53.87,Default,,0000,0000,0000,,so there's no point in looking at 3^6:
Dialogue: 0,0:08:53.87,0:08:56.18,Default,,0000,0000,0000,,we know we would just get 1.
Dialogue: 0,0:08:56.18,0:08:58.08,Default,,0000,0000,0000,,So here I calculated all of these powers for you,
Dialogue: 0,0:08:58.08,0:08:59.34,Default,,0000,0000,0000,,and I wrote them out,
Dialogue: 0,0:08:59.34,0:09:03.50,Default,,0000,0000,0000,,and you see that in fact, we get all the numbers in (Z_7)*.
Dialogue: 0,0:09:03.50,0:09:10.08,Default,,0000,0000,0000,,In other words, we get 1, 2, 3, 4, 5 and 6.
Dialogue: 0,0:09:10.08,0:09:14.24,Default,,0000,0000,0000,,So we would say that 3 is a generator of (Z_7)*.
Dialogue: 0,0:09:14.24,0:09:17.21,Default,,0000,0000,0000,,Now I should point out that not every element is a generator.
Dialogue: 0,0:09:17.21,0:09:20.60,Default,,0000,0000,0000,,For example, if we look at all the powers of 2,
Dialogue: 0,0:09:20.60,0:09:23.03,Default,,0000,0000,0000,,well, that's not going to generate the entire group.
Dialogue: 0,0:09:23.03,0:09:25.88,Default,,0000,0000,0000,,In particular, if we look at 2^0, we get 1.
Dialogue: 0,0:09:25.88,0:09:28.31,Default,,0000,0000,0000,,2^1, we get 2.
Dialogue: 0,0:09:28.31,0:09:33.80,Default,,0000,0000,0000,,2^2 is 4, and 2^3 is 8, which is 1 modulo 7.
Dialogue: 0,0:09:33.80,0:09:35.40,Default,,0000,0000,0000,,So we cycled back.
Dialogue: 0,0:09:35.40,0:09:37.15,Default,,0000,0000,0000,,And then 2^4 would be 2,
Dialogue: 0,0:09:37.15,0:09:40.20,Default,,0000,0000,0000,,2^5 would be 4, and so on and so forth.
Dialogue: 0,0:09:40.20,0:09:41.92,Default,,0000,0000,0000,,So if we look at the powers of 2,
Dialogue: 0,0:09:41.92,0:09:43.95,Default,,0000,0000,0000,,we just get 1, 2 and 4.
Dialogue: 0,0:09:43.95,0:09:45.13,Default,,0000,0000,0000,,We don't get the whole group.
Dialogue: 0,0:09:45.13,0:09:49.95,Default,,0000,0000,0000,,And therefore we say that 2 is not a generator of (Z_7)*.
Dialogue: 0,0:09:49.95,0:09:51.79,Default,,0000,0000,0000,,Now again, something that we'll use very often
Dialogue: 0,0:09:51.79,0:09:56.20,Default,,0000,0000,0000,,is, given an element g of (Z_p)*,
Dialogue: 0,0:09:56.20,0:09:59.79,Default,,0000,0000,0000,,if we look at the set of all powers of g,
Dialogue: 0,0:09:59.79,0:10:01.97,Default,,0000,0000,0000,,the resulting set is going to be called
Dialogue: 0,0:10:01.97,0:10:04.95,Default,,0000,0000,0000,,the group generated by g.
Dialogue: 0,0:10:04.95,0:10:07.31,Default,,0000,0000,0000,,OK? So these are all the powers of g,
Dialogue: 0,0:10:07.31,0:10:10.51,Default,,0000,0000,0000,,they give us what's called a multiplicative group,
Dialogue: 0,0:10:10.51,0:10:12.00,Default,,0000,0000,0000,,again, the technical term doesn't matter,
Dialogue: 0,0:10:12.00,0:10:14.70,Default,,0000,0000,0000,,the point is: we're going to call all these powers of g
Dialogue: 0,0:10:14.70,0:10:17.57,Default,,0000,0000,0000,,the group generated by g.
Dialogue: 0,0:10:17.57,0:10:20.11,Default,,0000,0000,0000,,In fact, there's this notation which I don't use very often:
Dialogue: 0,0:10:20.11,0:10:26.21,Default,,0000,0000,0000,,"" to denote this group that's generated by g.
Dialogue: 0,0:10:26.21,0:10:28.97,Default,,0000,0000,0000,,And then we call the order of g in (Z_p)*,
Dialogue: 0,0:10:28.97,0:10:30.62,Default,,0000,0000,0000,,we simply let that be
Dialogue: 0,0:10:30.62,0:10:33.41,Default,,0000,0000,0000,,the size of the group that's generated by g.
Dialogue: 0,0:10:33.41,0:10:35.98,Default,,0000,0000,0000,,So in other words,
Dialogue: 0,0:10:35.98,0:10:36.80,Default,,0000,0000,0000,,the order of g in (Z_p)*
Dialogue: 0,0:10:36.80,0:10:38.68,Default,,0000,0000,0000,,is the size of this group.
Dialogue: 0,0:10:38.68,0:10:40.14,Default,,0000,0000,0000,,But another way to think about that
Dialogue: 0,0:10:40.14,0:10:43.30,Default,,0000,0000,0000,,is basically, it's the smallest integer a
Dialogue: 0,0:10:43.30,0:10:48.17,Default,,0000,0000,0000,,such that g^a is equal to 1 in Z_p.
Dialogue: 0,0:10:48.17,0:10:50.07,Default,,0000,0000,0000,,OK? It's basically the smallest power
Dialogue: 0,0:10:50.07,0:10:53.76,Default,,0000,0000,0000,,that causes a power of g to be equal to 1.
Dialogue: 0,0:10:53.76,0:10:54.49,Default,,0000,0000,0000,,And it's very easy to see that
Dialogue: 0,0:10:54.49,0:10:55.84,Default,,0000,0000,0000,,this equality here,
Dialogue: 0,0:10:55.84,0:10:58.82,Default,,0000,0000,0000,,basically if we look at all the powers of g
Dialogue: 0,0:10:58.82,0:11:03.42,Default,,0000,0000,0000,,- we look at 1, g, g^2, g^3 and so on and so forth,
Dialogue: 0,0:11:03.42,0:11:07.02,Default,,0000,0000,0000,,up until we get to g to the order of g minus 1,
Dialogue: 0,0:11:07.02,0:11:10.94,Default,,0000,0000,0000,,and then if we look at g to the order of g,
Dialogue: 0,0:11:10.94,0:11:14.41,Default,,0000,0000,0000,,this thing is simply going to be equal to 1 by definition.
Dialogue: 0,0:11:14.46,0:11:16.75,Default,,0000,0000,0000,,OK? So there's no point in looking into higher powers,
Dialogue: 0,0:11:16.95,0:11:19.30,Default,,0000,0000,0000,,we might as well just stop raising to powers here.
Dialogue: 0,0:11:19.40,0:11:25.68,Default,,0000,0000,0000,,And as a result, the size of the set,
Dialogue: 0,0:11:25.68,0:11:29.55,Default,,0000,0000,0000,,in fact, is the order of g.
Dialogue: 0,0:11:29.55,0:11:32.20,Default,,0000,0000,0000,,And you can see that the order is the smallest power
Dialogue: 0,0:11:32.20,0:11:34.02,Default,,0000,0000,0000,,such that raising g to that power
Dialogue: 0,0:11:34.02,0:11:37.58,Default,,0000,0000,0000,,gives us 1 in Z_p.
Dialogue: 0,0:11:37.58,0:11:38.76,Default,,0000,0000,0000,,So I hope this is clear,
Dialogue: 0,0:11:38.76,0:11:40.40,Default,,0000,0000,0000,,although it might take a little lateral thinking
Dialogue: 0,0:11:40.40,0:11:41.91,Default,,0000,0000,0000,,to absorb all this notation.
Dialogue: 0,0:11:41.91,0:11:44.57,Default,,0000,0000,0000,,But in the meantime, let's look at a few examples.
Dialogue: 0,0:11:44.57,0:11:48.06,Default,,0000,0000,0000,,So again, let's fix our prime to be 7.
Dialogue: 0,0:11:48.06,0:11:50.29,Default,,0000,0000,0000,,And let's look at the order of a number of elements.
Dialogue: 0,0:11:50.29,0:11:52.88,Default,,0000,0000,0000,,So what is the order of 3 modulo 7?
Dialogue: 0,0:11:52.88,0:11:55.10,Default,,0000,0000,0000,,Well, we're asking: what is the size of the group
Dialogue: 0,0:11:55.10,0:11:58.15,Default,,0000,0000,0000,,that 3 generates modulo 7?
Dialogue: 0,0:11:58.15,0:12:01.20,Default,,0000,0000,0000,,Well, we said that 3 is a generator of (Z_7)*,
Dialogue: 0,0:12:01.20,0:12:03.89,Default,,0000,0000,0000,,so it generates all of (Z_7)*.
Dialogue: 0,0:12:03.89,0:12:06.48,Default,,0000,0000,0000,,There are 6 elements in (Z_7)*.
Dialogue: 0,0:12:06.48,0:12:11.57,Default,,0000,0000,0000,,And therefore we say that the order of 3 is equal to 6.
Dialogue: 0,0:12:11.57,0:12:12.31,Default,,0000,0000,0000,,Similarly I can ask:
Dialogue: 0,0:12:12.31,0:12:14.67,Default,,0000,0000,0000,,well, what is the order of 2 modulo 7?
Dialogue: 0,0:12:14.67,0:12:17.30,Default,,0000,0000,0000,,And in fact, we already saw the answer.
Dialogue: 0,0:12:17.30,0:12:20.67,Default,,0000,0000,0000,,So, let's - I'll ask you, what is the order of 2 modulo 7
Dialogue: 0,0:12:20.67,0:12:25.44,Default,,0000,0000,0000,,and see if you can figure out what this answer is.
Dialogue: 0,0:12:25.44,0:12:26.87,Default,,0000,0000,0000,,So the answer is 3.
Dialogue: 0,0:12:26.87,0:12:27.85,Default,,0000,0000,0000,,And again, the reason is,
Dialogue: 0,0:12:27.85,0:12:31.66,Default,,0000,0000,0000,,if we look at the set of powers of 2 modulo 7,
Dialogue: 0,0:12:31.66,0:12:34.38,Default,,0000,0000,0000,,well, we have 1, 2, 2^2,
Dialogue: 0,0:12:34.38,0:12:36.85,Default,,0000,0000,0000,,and then 2^3 that's already equal to 1,
Dialogue: 0,0:12:36.85,0:12:40.08,Default,,0000,0000,0000,,so this is the entire set of powers of 2 modulo 7.
Dialogue: 0,0:12:40.08,0:12:42.47,Default,,0000,0000,0000,,There are only three of them.
Dialogue: 0,0:12:42.47,0:12:46.30,Default,,0000,0000,0000,,And therefore, the order of 2 modulo 7 is exactly 3.
Dialogue: 0,0:12:46.30,0:12:47.33,Default,,0000,0000,0000,,Now let me ask you a trick question:
Dialogue: 0,0:12:47.33,0:12:51.81,Default,,0000,0000,0000,,What's the order of 1 modulo 7?
Dialogue: 0,0:12:51.81,0:12:52.90,Default,,0000,0000,0000,,Well, the answer is 1,
Dialogue: 0,0:12:52.90,0:12:55.96,Default,,0000,0000,0000,,because if you look at the group that's generated by 1,
Dialogue: 0,0:12:55.96,0:12:57.71,Default,,0000,0000,0000,,well, there's only one number in that group,
Dialogue: 0,0:12:57.71,0:12:58.84,Default,,0000,0000,0000,,namely the number 1.
Dialogue: 0,0:12:58.84,0:13:00.28,Default,,0000,0000,0000,,If I raise 1 to a whole bunch of powers,
Dialogue: 0,0:13:00.28,0:13:01.87,Default,,0000,0000,0000,,I'm always going to get 1,
Dialogue: 0,0:13:01.87,0:13:04.34,Default,,0000,0000,0000,,and therefore the order of 1 modulo 7,
Dialogue: 0,0:13:04.34,0:13:06.47,Default,,0000,0000,0000,,in fact, the order of 1 modulo any prime,
Dialogue: 0,0:13:06.47,0:13:10.28,Default,,0000,0000,0000,,is always going to be 1.
Dialogue: 0,0:13:10.28,0:13:12.28,Default,,0000,0000,0000,,Now, there's an important theorem of Lagrange that
Dialogue: 0,0:13:12.28,0:13:15.79,Default,,0000,0000,0000,,- actually, this is a very very special case of what I was telling here.
Dialogue: 0,0:13:15.79,0:13:18.21,Default,,0000,0000,0000,,But Lagrange's theorem basically implies
Dialogue: 0,0:13:18.21,0:13:20.88,Default,,0000,0000,0000,,that if you look at the order of g modulo p,
Dialogue: 0,0:13:20.88,0:13:24.17,Default,,0000,0000,0000,,the order is always going to divide p-1.
Dialogue: 0,0:13:24.17,0:13:26.67,Default,,0000,0000,0000,,So in our two example[s], you see
Dialogue: 0,0:13:26.67,0:13:30.44,Default,,0000,0000,0000,,6 divides 7 minus 1. 6 divides 6.
Dialogue: 0,0:13:30.44,0:13:35.21,Default,,0000,0000,0000,,And similarly, 3 divides 7-1, namely again, 3 divides 6.
Dialogue: 0,0:13:35.21,0:13:36.61,Default,,0000,0000,0000,,But this is very general.
Dialogue: 0,0:13:36.61,0:13:40.27,Default,,0000,0000,0000,,The order is always going to be a factor of p-1.
Dialogue: 0,0:13:40.27,0:13:40.88,Default,,0000,0000,0000,,In fact, I'll tell you,
Dialogue: 0,0:13:40.88,0:13:42.43,Default,,0000,0000,0000,,maybe it's a puzzle for you to think about
Dialogue: 0,0:13:42.43,0:13:45.25,Default,,0000,0000,0000,,it's actually very easy to deduce Fermat's theorem
Dialogue: 0,0:13:45.25,0:13:49.15,Default,,0000,0000,0000,,directly from this fact, from this Lagrange's theorem fact,
Dialogue: 0,0:13:49.15,0:13:50.86,Default,,0000,0000,0000,,and so Fermat's theorem really in some sense
Dialogue: 0,0:13:50.86,0:13:55.80,Default,,0000,0000,0000,,follows directly from Lagrange's theorem.
Dialogue: 0,0:13:55.80,0:13:58.45,Default,,0000,0000,0000,,Lagrange, by the way, did this work in the 19th century,
Dialogue: 0,0:13:58.45,0:14:01.82,Default,,0000,0000,0000,,so we can already see how we're making progress through time.
Dialogue: 0,0:14:01.82,0:14:03.42,Default,,0000,0000,0000,,We started in Greek times,
Dialogue: 0,0:14:03.42,0:14:07.78,Default,,0000,0000,0000,,and already we ended up in the 19th century.
Dialogue: 0,0:14:07.78,0:14:09.25,Default,,0000,0000,0000,,And I can tell you that more advanced crypto
Dialogue: 0,0:14:09.25,0:14:13.30,Default,,0000,0000,0000,,actually uses 20th-century math very extensively.
Dialogue: 0,0:14:13.30,0:14:15.64,Default,,0000,0000,0000,,Now that we understand the structure of (Z_p)*,
Dialogue: 0,0:14:15.64,0:14:17.44,Default,,0000,0000,0000,,let's generalize that to composites
Dialogue: 0,0:14:17.44,0:14:19.96,Default,,0000,0000,0000,,and look at the structure of (Z_N)*.
Dialogue: 0,0:14:19.96,0:14:22.76,Default,,0000,0000,0000,,So what I want to show you here is what's called Euler's theorem,
Dialogue: 0,0:14:22.76,0:14:26.22,Default,,0000,0000,0000,,which is a direct generalization of Fermat's theorem.
Dialogue: 0,0:14:26.22,0:14:28.55,Default,,0000,0000,0000,,So Euler defined the following function:
Dialogue: 0,0:14:28.55,0:14:30.40,Default,,0000,0000,0000,,So given an integer N,
Dialogue: 0,0:14:30.40,0:14:33.57,Default,,0000,0000,0000,,we define what's called the phi function, phi of N,
Dialogue: 0,0:14:33.57,0:14:37.62,Default,,0000,0000,0000,,to be basically the size of the set (Z_N)*.
Dialogue: 0,0:14:37.62,0:14:40.22,Default,,0000,0000,0000,,This is sometimes called "Euler's phi function".
Dialogue: 0,0:14:40.22,0:14:42.79,Default,,0000,0000,0000,,The size of the set (Z_N)*.
Dialogue: 0,0:14:42.79,0:14:46.06,Default,,0000,0000,0000,,So for example, we already looked at (Z_12)*.
Dialogue: 0,0:14:46.06,0:14:49.17,Default,,0000,0000,0000,,We said that (Z_12)* contains these four elements
Dialogue: 0,0:14:49.17,0:14:51.21,Default,,0000,0000,0000,,1, 5, 7 and 11,
Dialogue: 0,0:14:51.21,0:14:56.01,Default,,0000,0000,0000,,and therefore we say that phi of 12 is simply the number of 4.
Dialogue: 0,0:14:56.01,0:14:57.21,Default,,0000,0000,0000,,So let me ask you as a puzzle:
Dialogue: 0,0:14:57.21,0:14:59.29,Default,,0000,0000,0000,,What is phi of p?
Dialogue: 0,0:14:59.29,0:15:04.07,Default,,0000,0000,0000,,It'll basically be the size of (Z_P)*.
Dialogue: 0,0:15:04.07,0:15:05.15,Default,,0000,0000,0000,,And so in fact we said
Dialogue: 0,0:15:05.15,0:15:08.14,Default,,0000,0000,0000,,that (Z_P)* contains all of Z_P
Dialogue: 0,0:15:08.14,0:15:09.93,Default,,0000,0000,0000,,except for the number zero,
Dialogue: 0,0:15:09.93,0:15:12.98,Default,,0000,0000,0000,,and therefore phi of p for any prime p
Dialogue: 0,0:15:12.98,0:15:16.74,Default,,0000,0000,0000,,is going to be p-1.
Dialogue: 0,0:15:16.74,0:15:18.70,Default,,0000,0000,0000,,Now there's a special case which I'm going to state here
Dialogue: 0,0:15:18.70,0:15:21.01,Default,,0000,0000,0000,,we're going to use later for the RSA system:
Dialogue: 0,0:15:21.01,0:15:23.57,Default,,0000,0000,0000,,if N happens to be a product of two primes,
Dialogue: 0,0:15:23.57,0:15:27.50,Default,,0000,0000,0000,,then phi of N is simply N minus p minus q plus 1.
Dialogue: 0,0:15:27.50,0:15:29.55,Default,,0000,0000,0000,,Let me just show you why that's true.
Dialogue: 0,0:15:29.55,0:15:32.44,Default,,0000,0000,0000,,Basically, N is the size of Z_N.
Dialogue: 0,0:15:32.44,0:15:34.56,Default,,0000,0000,0000,,And now we need to remove all the elements
Dialogue: 0,0:15:34.56,0:15:37.21,Default,,0000,0000,0000,,that are not relatively prime to N.
Dialogue: 0,0:15:37.21,0:15:40.02,Default,,0000,0000,0000,,Well, how can an element not be relatively prime to N?
Dialogue: 0,0:15:40.02,0:15:41.50,Default,,0000,0000,0000,,It's got to be divisible by p,
Dialogue: 0,0:15:41.50,0:15:43.75,Default,,0000,0000,0000,,or it's got to be divisible by q.
Dialogue: 0,0:15:43.75,0:15:45.76,Default,,0000,0000,0000,,Well, how many elements between zero and N-1
Dialogue: 0,0:15:45.76,0:15:48.88,Default,,0000,0000,0000,,are there that are divisible by p?
Dialogue: 0,0:15:48.88,0:15:50.43,Default,,0000,0000,0000,,Well, there are exactly q of them.
Dialogue: 0,0:15:50.43,0:15:53.00,Default,,0000,0000,0000,,How many elements are there that are divisible by q?
Dialogue: 0,0:15:53.00,0:15:54.51,Default,,0000,0000,0000,,Well, there are exactly p of them.
Dialogue: 0,0:15:54.51,0:15:57.97,Default,,0000,0000,0000,,So we subtract p to get rid of those divisible by q,
Dialogue: 0,0:15:57.97,0:16:01.10,Default,,0000,0000,0000,,we subtract q to get rid of those divisible by p.
Dialogue: 0,0:16:01.10,0:16:03.79,Default,,0000,0000,0000,,And you'll notice we subtracted 0 twice,
Dialogue: 0,0:16:03.79,0:16:07.67,Default,,0000,0000,0000,,because 0 is divisible both by p and q.
Dialogue: 0,0:16:07.67,0:16:09.25,Default,,0000,0000,0000,,And therefore we add 1,
Dialogue: 0,0:16:09.25,0:16:12.19,Default,,0000,0000,0000,,just to make sure we subtract 0 only once.
Dialogue: 0,0:16:12.19,0:16:13.18,Default,,0000,0000,0000,,And so it's not difficult to see
Dialogue: 0,0:16:13.18,0:16:17.06,Default,,0000,0000,0000,,that phi of N is N minus p minus q plus 1.
Dialogue: 0,0:16:17.06,0:16:18.37,Default,,0000,0000,0000,,And another way of writing that is simply:
Dialogue: 0,0:16:18.37,0:16:22.44,Default,,0000,0000,0000,,p minus 1, times q minus 1.
Dialogue: 0,0:16:22.44,0:16:24.21,Default,,0000,0000,0000,,OK? So this is a fact that we will use
Dialogue: 0,0:16:24.21,0:16:25.91,Default,,0000,0000,0000,,later on when we will come back
Dialogue: 0,0:16:25.91,0:16:29.42,Default,,0000,0000,0000,,and talk about the RSA system.
Dialogue: 0,0:16:29.42,0:16:32.69,Default,,0000,0000,0000,,So far, this is just defining this phi function of Euler.
Dialogue: 0,0:16:32.69,0:16:35.83,Default,,0000,0000,0000,,But now, Euler put this phi function to really good use.
Dialogue: 0,0:16:35.83,0:16:38.00,Default,,0000,0000,0000,,And what he proved is this amazing fact here
Dialogue: 0,0:16:38.00,0:16:39.18,Default,,0000,0000,0000,,that basically says
Dialogue: 0,0:16:39.18,0:16:43.07,Default,,0000,0000,0000,,that if you give me any element x in (Z_N)*,
Dialogue: 0,0:16:43.07,0:16:44.58,Default,,0000,0000,0000,,in fact it so happens that
Dialogue: 0,0:16:44.58,0:16:48.77,Default,,0000,0000,0000,,x to the power of phi of N is equal to 1 in Z_N.
Dialogue: 0,0:16:48.77,0:16:50.98,Default,,0000,0000,0000,,So you can see that this is a generalization of Fermat's theorem.
Dialogue: 0,0:16:50.98,0:16:53.99,Default,,0000,0000,0000,,In particular, Fermat's theorem only applied to primes.
Dialogue: 0,0:16:53.99,0:16:57.34,Default,,0000,0000,0000,,For primes we know that phi of p is equal to p-1,
Dialogue: 0,0:16:57.34,0:16:57.98,Default,,0000,0000,0000,,and in other words,
Dialogue: 0,0:16:57.98,0:17:01.34,Default,,0000,0000,0000,,if N were prime, we would simply write p-1 here,
Dialogue: 0,0:17:01.34,0:17:04.46,Default,,0000,0000,0000,,and then we would get exactly Fermat's theorem.
Dialogue: 0,0:17:04.46,0:17:06.12,Default,,0000,0000,0000,,The beauty of Euler's theorem is that
Dialogue: 0,0:17:06.12,0:17:09.25,Default,,0000,0000,0000,,it applies to composites and not just primes.
Dialogue: 0,0:17:09.71,0:17:13.76,Default,,0000,0000,0000,,So let's look at some examples:
Dialogue: 0,0:17:13.76,0:17:17.42,Default,,0000,0000,0000,,So let's look at 5 to the power of phi of 12.
Dialogue: 0,0:17:17.42,0:17:20.44,Default,,0000,0000,0000,,So 5 is an element of (Z_12)*.
Dialogue: 0,0:17:20.44,0:17:22.71,Default,,0000,0000,0000,,If we raise it to the power of phi of 12,
Dialogue: 0,0:17:22.71,0:17:24.10,Default,,0000,0000,0000,,we should be getting 1.
Dialogue: 0,0:17:24.10,0:17:26.48,Default,,0000,0000,0000,,Well, we know that phi of 12 is 4,
Dialogue: 0,0:17:26.48,0:17:29.80,Default,,0000,0000,0000,,so we're raising 5 to the power of 4.
Dialogue: 0,0:17:29.80,0:17:31.100,Default,,0000,0000,0000,,5 to the power of 4 is 625.
Dialogue: 0,0:17:31.100,0:17:33.47,Default,,0000,0000,0000,,And it's a simple calculation to show that
Dialogue: 0,0:17:33.47,0:17:36.43,Default,,0000,0000,0000,,that's equal to 1 modulo 12.
Dialogue: 0,0:17:36.43,0:17:37.79,Default,,0000,0000,0000,,So this is proof by example,
Dialogue: 0,0:17:37.79,0:17:38.96,Default,,0000,0000,0000,,but of course it's not a proof at all,
Dialogue: 0,0:17:38.96,0:17:40.12,Default,,0000,0000,0000,,it's just an example.
Dialogue: 0,0:17:40.12,0:17:42.48,Default,,0000,0000,0000,,And in fact, it's not difficult to prove Euler's theorem.
Dialogue: 0,0:17:42.48,0:17:44.38,Default,,0000,0000,0000,,And in fact I tell you that Euler's theorem
Dialogue: 0,0:17:44.38,0:17:46.12,Default,,0000,0000,0000,,is also a very special case
Dialogue: 0,0:17:46.12,0:17:49.37,Default,,0000,0000,0000,,of Lagrange's general theorem.
Dialogue: 0,0:17:49.37,0:17:51.44,Default,,0000,0000,0000,,OK. So we said that
Dialogue: 0,0:17:51.44,0:17:53.58,Default,,0000,0000,0000,,this is a generalization of Fermat's theorem
Dialogue: 0,0:17:53.58,0:17:54.96,Default,,0000,0000,0000,,and in fact, as we'll see,
Dialogue: 0,0:17:54.96,0:17:56.00,Default,,0000,0000,0000,,this Euler's theorem
Dialogue: 0,0:17:56.00,0:18:00.20,Default,,0000,0000,0000,,is the basis of the RSA cryptosystem.
Dialogue: 0,0:18:00.20,0:18:00.95,Default,,0000,0000,0000,,So I'll stop here,
Dialogue: 0,0:18:00.95,0:18:03.28,Default,,0000,0000,0000,,and we'll continue with modular quadratic equations
Dialogue: 0,0:18:03.28,9:59:59.99,Default,,0000,0000,0000,,in the next segment.