[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.53,Default,,0000,0000,0000,,The next thing we're going to look at is\Nhow to compute modular large integers. So
Dialogue: 0,0:00:04.53,0:00:09.02,Default,,0000,0000,0000,,the first question is how do we represent\Nlarge integers in a computer? So that's
Dialogue: 0,0:00:09.02,0:00:13.62,Default,,0000,0000,0000,,actually fairly straightforward. So\Nimagine we're on a 64 bit machine, what we
Dialogue: 0,0:00:13.62,0:00:18.36,Default,,0000,0000,0000,,would do is we would break the number we\Nwant to represent, into 32 bit buckets And
Dialogue: 0,0:00:18.36,0:00:22.69,Default,,0000,0000,0000,,then, we will basically have these n/32 bit buckets, and together they will
Dialogue: 0,0:00:22.69,0:00:26.91,Default,,0000,0000,0000,,represent the number that we want to store\Non the computer. Now, I should mention
Dialogue: 0,0:00:26.91,0:00:30.70,Default,,0000,0000,0000,,that I'm only giving 64 bit registers as\Nan example. In fact, many modern
Dialogue: 0,0:00:30.70,0:00:34.98,Default,,0000,0000,0000,,processors have 128 bit registers or more,\Nand you can even do multiplications on
Dialogue: 0,0:00:34.98,0:00:38.99,Default,,0000,0000,0000,,them. So normally you would actually use\Nmuch larger blocks than just 32 bits. The
Dialogue: 0,0:00:38.99,0:00:42.94,Default,,0000,0000,0000,,reason, by the way, you want to limit\Nyourself to 32 bits is so that you can
Dialogue: 0,0:00:42.94,0:00:46.95,Default,,0000,0000,0000,,multiply two blocks together, and the\Nresult will still be less than 64 bits,
Dialogue: 0,0:00:46.95,0:00:51.19,Default,,0000,0000,0000,,less than the word size on the machine. So\Nnow let's look at particular arithmetic
Dialogue: 0,0:00:51.19,0:00:54.79,Default,,0000,0000,0000,,operations and see how long each one\Ntakes. So addition and subtraction
Dialogue: 0,0:00:54.79,0:00:58.74,Default,,0000,0000,0000,,basically what you would do is that\Naddition would carry or subtraction would
Dialogue: 0,0:00:58.74,0:01:03.00,Default,,0000,0000,0000,,borrow and those are basically linear time\Noperations. In other words, if you want to
Dialogue: 0,0:01:03.00,0:01:06.95,Default,,0000,0000,0000,,add or subtract two n bit integers the\Nrunning time is basically
Dialogue: 0,0:01:06.95,0:01:12.63,Default,,0000,0000,0000,,linear in n. Multiplication\Nnaively will take quadratic time. In fact,
Dialogue: 0,0:01:12.63,0:01:16.68,Default,,0000,0000,0000,,this is what's called the high school\Nalgorithm. This is what you kind of
Dialogue: 0,0:01:16.68,0:01:21.11,Default,,0000,0000,0000,,learned in school, where if you think\Nabout this for a minute you'll see that,
Dialogue: 0,0:01:21.11,0:01:25.66,Default,,0000,0000,0000,,that algorithm basically is quadratic in\Nthe length of the numbers that are being
Dialogue: 0,0:01:25.66,0:01:30.16,Default,,0000,0000,0000,,multiplied. So a big surprise in the 1960s\Nwas an algorithm due to Karatsuba that
Dialogue: 0,0:01:30.16,0:01:34.15,Default,,0000,0000,0000,,actually achieves much better than\Nquadratic time in fact, it achieved a
Dialogue: 0,0:01:34.15,0:01:38.57,Default,,0000,0000,0000,,running time of n to the 1.585. And\Nthere's actually no point in me showing
Dialogue: 0,0:01:38.57,0:01:43.17,Default,,0000,0000,0000,,you how the algorithm actually worked,\NI'll just mention the main idea What
Dialogue: 0,0:01:43.17,0:01:48.07,Default,,0000,0000,0000,,Karatsuba realized, is that in fact when\Nyou want to multiply two numbers, you can
Dialogue: 0,0:01:48.07,0:01:52.98,Default,,0000,0000,0000,,write them as, you can take the first\Nnumber x, write it as 2 to the b times
Dialogue: 0,0:01:52.98,0:01:57.88,Default,,0000,0000,0000,,x2 plus x1. Where x2 and x1 are roughly\Nthe size of the square root of x. Okay, so
Dialogue: 0,0:01:57.88,0:02:02.91,Default,,0000,0000,0000,,we can kind of break the number x into the\Nleft part of x and the right part of x.
Dialogue: 0,0:02:02.91,0:02:07.65,Default,,0000,0000,0000,,And basically, you're writing x as if it\Nwas written base 2 to the b. So it's got
Dialogue: 0,0:02:07.65,0:02:12.40,Default,,0000,0000,0000,,two digits base 2 to the b. And you do\Nthe same thing with, y. You write y base
Dialogue: 0,0:02:12.40,0:02:16.91,Default,,0000,0000,0000,,2 to the b. Again, you would write it\Nas, the sum of the left half plus the
Dialogue: 0,0:02:16.91,0:02:21.54,Default,,0000,0000,0000,,right half, And then, normally, if you try\Nto do this multiplication, when you open
Dialogue: 0,0:02:21.54,0:02:27.49,Default,,0000,0000,0000,,up the parentheses. You see that, this\Nwould require 4 multiplications, right?
Dialogue: 0,0:02:27.49,0:02:33.36,Default,,0000,0000,0000,,It would require x2 times y2, x2 times y1,\Nx1 times y2, and x1 times y1. What
Dialogue: 0,0:02:33.36,0:02:39.88,Default,,0000,0000,0000,,Karatsuba realized is there's a way to do\Nthis multiplication of x by y using only
Dialogue: 0,0:02:39.88,0:02:45.85,Default,,0000,0000,0000,,three multiplications of x1 x2 y1 y2. So it's just a big multiplication of x times y
Dialogue: 0,0:02:45.85,0:02:50.21,Default,,0000,0000,0000,,only it takes three little multiplications. You can now recursively
Dialogue: 0,0:02:50.21,0:02:55.09,Default,,0000,0000,0000,,apply exactly the same procedure to\Nmultiplying x2 by y2, and x2 by y1, and so
Dialogue: 0,0:02:55.09,0:02:59.96,Default,,0000,0000,0000,,on and so forth. And you would get this\Nrecursive algorithm. And if you do the
Dialogue: 0,0:02:59.96,0:03:05.09,Default,,0000,0000,0000,,recursive analysis, you will see that\Nbasically, you get a running time of n to the 1.585.
Dialogue: 0,0:03:05.09,0:03:13.64,Default,,0000,0000,0000,,This number is basically, the 1.585 is basically, log of 3 base 2.
Dialogue: 0,0:03:13.64,0:03:17.84,Default,,0000,0000,0000,,Surprisingly, it turns out that Karatsuba\Nisn't even the best multiplication
Dialogue: 0,0:03:17.84,0:03:23.91,Default,,0000,0000,0000,,algorithm out there. It turns out that, in fact, you can do multiplication in about n*log(n) time.
Dialogue: 0,0:03:23.91,0:03:28.68,Default,,0000,0000,0000,,So you can do multiplication in almost linear time. However, this is an extremely asymptotic results.
Dialogue: 0,0:03:28.68,0:03:31.48,Default,,0000,0000,0000,,The big O here hides very big constants. And as a
Dialogue: 0,0:03:31.48,0:03:35.45,Default,,0000,0000,0000,,result, this algorithm only becomes\Npractical when the numbers are absolutely
Dialogue: 0,0:03:35.45,0:03:39.15,Default,,0000,0000,0000,,enormous. And so this algorithm is\Nactually not used very often. But
Dialogue: 0,0:03:39.15,0:03:43.18,Default,,0000,0000,0000,,Karatsuba's algorithm is very practical.\NAnd in fact, most crypto-libraries
Dialogue: 0,0:03:43.18,0:03:47.88,Default,,0000,0000,0000,,implement Karatsuba's algorithm for\Nmultiplication. However, for simplicity
Dialogue: 0,0:03:47.88,0:03:51.92,Default,,0000,0000,0000,,here, I'm just gonna ignore Karatsuba's\Nalgorithm, and just for simplicity, I'm
Dialogue: 0,0:03:51.92,0:03:55.96,Default,,0000,0000,0000,,gonna assume that multiplication runs in\Nquadratic time. But in your mind, you
Dialogue: 0,0:03:55.96,0:03:59.89,Default,,0000,0000,0000,,should always be thinking all multiplication really is a little bit faster than quadratic.
Dialogue: 0,0:03:59.89,0:04:04.79,Default,,0000,0000,0000,,And then the next question after multiplication is what about
Dialogue: 0,0:04:04.79,0:04:10.30,Default,,0000,0000,0000,,division with remainder and it turns out\Nthat's also a quadratic time algorithm.
Dialogue: 0,0:04:10.30,0:04:15.42,Default,,0000,0000,0000,,So the main operation that remains, and one\Nthat we've used many times so far, and
Dialogue: 0,0:04:15.42,0:04:20.35,Default,,0000,0000,0000,,I've never, actually never, ever told you\Nhow to actually compute it, is this
Dialogue: 0,0:04:20.35,0:04:26.34,Default,,0000,0000,0000,,question of exponentiation. So let's solve\Nthis exponentiation problem a bit more
Dialogue: 0,0:04:26.34,0:04:31.56,Default,,0000,0000,0000,,abstractly. So imagine we have a finite\Ncyclic group G. All this means is that
Dialogue: 0,0:04:31.56,0:04:37.12,Default,,0000,0000,0000,,this group is generated from the powers of\Nsome generator little g. So for example
Dialogue: 0,0:04:37.12,0:04:42.67,Default,,0000,0000,0000,,think of this group as simply ZP*, and think of little g as some generator of
Dialogue: 0,0:04:42.67,0:04:48.89,Default,,0000,0000,0000,,big G. The reason I'm sitting in this way,\Nis I'm, I want you to start getting used
Dialogue: 0,0:04:48.89,0:04:54.02,Default,,0000,0000,0000,,to this abstraction where we deal with a\Ngeneric group G and ZP* really is just
Dialogue: 0,0:04:54.02,0:04:58.92,Default,,0000,0000,0000,,one example of such a group. But, in fact,\Nthere are many other examples of finite
Dialogue: 0,0:04:58.92,0:05:03.38,Default,,0000,0000,0000,,cyclic groups. And again I want to\Nemphasis basically that group G, all it
Dialogue: 0,0:05:03.38,0:05:08.09,Default,,0000,0000,0000,,is, it's simply this powers of this\Ngenerator up to the order of the group.
Dialogue: 0,0:05:08.09,0:05:15.15,Default,,0000,0000,0000,,I'll write it as G to the Q. So our goal\Nnow is given this element g, and some
Dialogue: 0,0:05:15.15,0:05:20.80,Default,,0000,0000,0000,,exponent x, our goal is to compute the\Nvalue of g to the x. Now normally what you
Dialogue: 0,0:05:20.80,0:05:24.81,Default,,0000,0000,0000,,would say is, you would think well, you\Nknow, if x is equal to 3 then I'm
Dialogue: 0,0:05:24.81,0:05:28.90,Default,,0000,0000,0000,,gonna compute you know, g cubed. Well,\Nthere's really nothing to do. All I do is
Dialogue: 0,0:05:28.90,0:05:32.80,Default,,0000,0000,0000,,I just do g times g times g and I get g\Ncubed, which is what I wanted. So that's
Dialogue: 0,0:05:32.80,0:05:36.79,Default,,0000,0000,0000,,actually pretty easy. But in fact, that's\Nnot the case that we're interested in. In
Dialogue: 0,0:05:36.79,0:05:40.64,Default,,0000,0000,0000,,our case, our exponents are gonna be\Nenormous. And so if you try, you know,
Dialogue: 0,0:05:40.64,0:05:45.64,Default,,0000,0000,0000,,think of like a 500-bit number and so if\Nyou try to compute g to the power of a
Dialogue: 0,0:05:45.64,0:05:50.71,Default,,0000,0000,0000,,500-bit number simply by multiplying g by\Ng by g by g this is gonna take quite a
Dialogue: 0,0:05:50.71,0:05:55.72,Default,,0000,0000,0000,,while. In fact it will take exponential\Ntime which is not something that we want
Dialogue: 0,0:05:55.90,0:06:00.72,Default,,0000,0000,0000,,to do. So the question is whether even\Nthough x is enormous, can we still compute
Dialogue: 0,0:06:00.72,0:06:05.67,Default,,0000,0000,0000,,g to the x relatively fast and the answer\Nis yes and the algorithm that does that
Dialogue: 0,0:06:05.67,0:06:10.82,Default,,0000,0000,0000,,is called a repeated squaring algorithm.\NAnd so let me show you how repeated
Dialogue: 0,0:06:10.82,0:06:15.59,Default,,0000,0000,0000,,squaring works. So let's take as an\Nexample, 53. Naively you would have to do
Dialogue: 0,0:06:15.59,0:06:20.30,Default,,0000,0000,0000,,53 multiplications of g by g by g by g\Nuntil you get to g by the 53 but I want to
Dialogue: 0,0:06:20.30,0:06:25.28,Default,,0000,0000,0000,,show you how you can do it very quickly.\NSo what we'll do is we'll write 53 in
Dialogue: 0,0:06:25.28,0:06:30.50,Default,,0000,0000,0000,,binary. So here this is the binary\Nrepresentation of 53. And all that means
Dialogue: 0,0:06:30.50,0:06:36.28,Default,,0000,0000,0000,,is, you notice this one corresponds to 32,\Nthis one corresponds to 16, this one
Dialogue: 0,0:06:36.28,0:06:41.29,Default,,0000,0000,0000,,corresponds to 4, and this one\Ncorresponds to 1. So really 53 is 32
Dialogue: 0,0:06:41.29,0:06:47.04,Default,,0000,0000,0000,,plus 16 plus 4 plus 1. But what\Nthat means is that g to the power of 53 is
Dialogue: 0,0:06:47.04,0:06:51.80,Default,,0000,0000,0000,,g to the power of 32+16+4+1. And we can\Nbreak that up, using again, the rules of
Dialogue: 0,0:06:51.80,0:06:57.24,Default,,0000,0000,0000,,exponentiation. We can break that up as g\Nto the 32 times g to the 16 times g to the
Dialogue: 0,0:06:57.24,0:07:02.94,Default,,0000,0000,0000,,4 times g to the 1, Now that should start\Ngiving you an idea for how to compute g to
Dialogue: 0,0:07:02.94,0:07:07.14,Default,,0000,0000,0000,,the 53 very quickly. What we'll do is,\Nsimply, we'll take g and we'll start
Dialogue: 0,0:07:07.14,0:07:11.46,Default,,0000,0000,0000,,squaring it. So what square wants, g wants\Nto get g squared. We square it again to
Dialogue: 0,0:07:11.46,0:07:15.78,Default,,0000,0000,0000,,get g to the 4, turn g to the 8.\NTurn g to the 16, g to the 32. So
Dialogue: 0,0:07:15.78,0:07:20.61,Default,,0000,0000,0000,,we've computed all these squares of g. And\Nnow, what we're gonna do is we're simply
Dialogue: 0,0:07:20.61,0:07:25.72,Default,,0000,0000,0000,,gonna multiply the appropriate powers to\Ngive us the g to the 53. So this is g to
Dialogue: 0,0:07:25.72,0:07:30.39,Default,,0000,0000,0000,,the one times g to the 4 times g to the 16 times g to the 32, is basically
Dialogue: 0,0:07:30.39,0:07:35.38,Default,,0000,0000,0000,,gonna give us the value that we want,\Nwhich is g to the 53. So here you see that
Dialogue: 0,0:07:35.38,0:07:40.17,Default,,0000,0000,0000,,all we had to do was just compute, let's\Nsee, we had to do one, two, three, four,
Dialogue: 0,0:07:40.17,0:07:49.34,Default,,0000,0000,0000,,five squaring, plus four more multiplications\Nso with 9 multiplications we computed g
Dialogue: 0,0:07:49.34,0:07:53.73,Default,,0000,0000,0000,,to the 53. Okay so that's pretty\Ninteresting. And it turns out this is a
Dialogue: 0,0:07:53.73,0:07:58.25,Default,,0000,0000,0000,,general phenomena that allows us to raise\Ng to very, very high powers and do it very
Dialogue: 0,0:07:58.25,0:08:02.51,Default,,0000,0000,0000,,quickly. So let me show you the algorithm,\Nas I said this is called the repeated
Dialogue: 0,0:08:02.51,0:08:06.50,Default,,0000,0000,0000,,squaring algorithm. So the input to the\Nalgorithm is the element g and the
Dialogue: 0,0:08:06.50,0:08:10.86,Default,,0000,0000,0000,,exponent x. And the output is g to the x.\NSo what we're gonna do is we're gonna
Dialogue: 0,0:08:10.86,0:08:15.42,Default,,0000,0000,0000,,write x in binary notation. So let's say\Nthat x has n bits. And this is the actual
Dialogue: 0,0:08:15.42,0:08:19.52,Default,,0000,0000,0000,,bit representation of x as a binary\Nnumber. And then what we'll do is the
Dialogue: 0,0:08:19.52,0:08:24.25,Default,,0000,0000,0000,,following. We'll have these two registers.\Ny is gonna be a register that's constantly
Dialogue: 0,0:08:24.25,0:08:28.13,Default,,0000,0000,0000,,squared. And then z is gonna be an\Naccumulator that multiplies in the
Dialogue: 0,0:08:28.13,0:08:32.68,Default,,0000,0000,0000,,appropriate powers of g as needed. So all\Nwe do is the following we loop through the
Dialogue: 0,0:08:32.68,0:08:36.53,Default,,0000,0000,0000,,bits of x starting from the least\Nsignificant bits, And then we do the
Dialogue: 0,0:08:36.53,0:08:41.41,Default,,0000,0000,0000,,following: in every iteration we're simply\Ngonna square y. Okay, so y just keeps on
Dialogue: 0,0:08:41.41,0:08:45.94,Default,,0000,0000,0000,,squaring at every iteration. And then\Nwhenever the corresponding bit of the
Dialogue: 0,0:08:45.94,0:08:50.55,Default,,0000,0000,0000,,exponent x happens to be one, we simply\Naccumulate the current value of y into
Dialogue: 0,0:08:50.55,0:08:55.17,Default,,0000,0000,0000,,this accumulator z and then at the end, we\Nsimply output z. That's it. That's the
Dialogue: 0,0:08:55.17,0:08:59.56,Default,,0000,0000,0000,,whole algorithm, and that's the repeated\Nsquaring algorithm. So, let's see an
Dialogue: 0,0:08:59.56,0:09:04.06,Default,,0000,0000,0000,,example with G to the 53. So,\Nyou can see the two columns. y is one
Dialogue: 0,0:09:04.06,0:09:08.39,Default,,0000,0000,0000,,column, as it evolves through the\Niterations, and z is another column, again
Dialogue: 0,0:09:08.39,0:09:13.06,Default,,0000,0000,0000,,as it evolves through the iterations. So,\Ny is not very interesting. Basically, all
Dialogue: 0,0:09:13.06,0:09:17.45,Default,,0000,0000,0000,,that happens to y is that at every\Niteration, it simply gets squared. And so
Dialogue: 0,0:09:17.45,0:09:22.30,Default,,0000,0000,0000,,it just walks through the powers of two\Nand the exponents and that's it. z is the
Dialogue: 0,0:09:22.30,0:09:26.92,Default,,0000,0000,0000,,more interesting register where what it\Ndoes is it accumulates the appropriate
Dialogue: 0,0:09:26.92,0:09:31.88,Default,,0000,0000,0000,,powers of g whenever the corresponding bit\Nto the exponent is one. So for example the
Dialogue: 0,0:09:31.88,0:09:36.03,Default,,0000,0000,0000,,first bit of the exponent is one,\Ntherefore, the, at the end of the first
Dialogue: 0,0:09:36.03,0:09:41.22,Default,,0000,0000,0000,,iteration the value of z is simply equal to\Ng. The second bit of the exponent is zero
Dialogue: 0,0:09:41.22,0:09:46.47,Default,,0000,0000,0000,,so the value of z doesn't change after the\Nsecond iteration. And at the end of the
Dialogue: 0,0:09:46.47,0:09:51.86,Default,,0000,0000,0000,,third iteration well the third bit of the\Nexponent is one so we accumulate g to the
Dialogue: 0,0:09:51.86,0:09:56.66,Default,,0000,0000,0000,,fourth into z. The next bit of the\Nexponent is zero so z doesn't change. The
Dialogue: 0,0:09:56.66,0:10:02.11,Default,,0000,0000,0000,,next bit of the exponent is one and so now\Nwe're supposed to accumulate the previous
Dialogue: 0,0:10:02.11,0:10:07.49,Default,,0000,0000,0000,,value of y into the accumulator z so let\Nme ask you so what's gonna be the value of z?
Dialogue: 0,0:10:10.87,0:10:14.24,Default,,0000,0000,0000,,Well, we simply accumulate g to the\N16 into z and so we simply compute the sum
Dialogue: 0,0:10:14.24,0:10:19.59,Default,,0000,0000,0000,,of 16 and 5 we get g to the 21.\NFinally, the last bit is also set to one
Dialogue: 0,0:10:19.59,0:10:24.94,Default,,0000,0000,0000,,so we accumulate it into z, we do 32 plus 21 and we get the finally output g to the 53.
Dialogue: 0,0:10:24.94,0:10:30.02,Default,,0000,0000,0000,,Okay, so this gives you an idea of how\Nthis repeated squaring algorithm works.
Dialogue: 0,0:10:30.02,0:10:35.78,Default,,0000,0000,0000,,It's is quite an interesting algorithm and\Nit allows us to compute enormous powers of
Dialogue: 0,0:10:35.78,0:10:41.06,Default,,0000,0000,0000,,g very, very, very quickly. So the number\Nof iterations here, essentially, would be
Dialogue: 0,0:10:41.06,0:10:46.46,Default,,0000,0000,0000,,log base 2 of x. Okay. You notice the\Nnumber of iterations simply depends on the
Dialogue: 0,0:10:46.46,0:10:51.95,Default,,0000,0000,0000,,number of digits of x, which is basically\Nthe log base 2 of x. So even if x is a
Dialogue: 0,0:10:51.95,0:10:56.52,Default,,0000,0000,0000,,500 bit number in 500 multiplication,\Nwell, 500 iterations, really 1,000
Dialogue: 0,0:10:56.52,0:11:01.74,Default,,0000,0000,0000,,multiplications because we have to square\Nand we have to accumulate. So in 1,000
Dialogue: 0,0:11:01.74,0:11:06.63,Default,,0000,0000,0000,,multiplications we'll be able to raise g\Nto the power of a 500 bit exponent.
Dialogue: 0,0:11:06.63,0:11:12.76,Default,,0000,0000,0000,,Okay so now we can summarize kind of the running times so suppose we
Dialogue: 0,0:11:12.76,0:11:17.68,Default,,0000,0000,0000,,have an N bit modulus capital N as we\Nsaid addition and subtraction in ZN takes
Dialogue: 0,0:11:17.68,0:11:22.16,Default,,0000,0000,0000,,linear time. Multiplication of just, you\Nknow, as I said, Karatsuba's actually makes this
Dialogue: 0,0:11:22.16,0:11:26.90,Default,,0000,0000,0000,,more efficient, but for simplicity we'll\Njust say that it takes quadratic time. And
Dialogue: 0,0:11:26.90,0:11:31.58,Default,,0000,0000,0000,,then exponentiation, as I said, basically\Ntakes log of x iterations, and at each
Dialogue: 0,0:11:31.58,0:11:35.51,Default,,0000,0000,0000,,iteration we basically do two\Nmultiplications. So it's O(log (x))
Dialogue: 0,0:11:35.51,0:11:40.31,Default,,0000,0000,0000,,times the time to multiply. And let's say\Nthat the time to multiply is quadratic. So
Dialogue: 0,0:11:40.31,0:11:44.76,Default,,0000,0000,0000,,the running time would be, really, N\Nsquared log x. And since x is always gonna
Dialogue: 0,0:11:44.76,0:11:49.17,Default,,0000,0000,0000,,be less than N, by Fermat's theorem\Nthere's no point in raising g to a power
Dialogue: 0,0:11:49.17,0:11:53.96,Default,,0000,0000,0000,,that's larger than the modulus. So x is\Ngonna be less than N. Let's suppose that x
Dialogue: 0,0:11:53.96,0:11:58.57,Default,,0000,0000,0000,,is also an N-bit integer, then, really\Nexponentiation is a cubic-time algorithm.
Dialogue: 0,0:11:58.57,0:12:02.97,Default,,0000,0000,0000,,Okay so that's what I wanted you to\Nremember, that exponentiation is actually
Dialogue: 0,0:12:02.97,0:12:07.16,Default,,0000,0000,0000,,a relatively slow. These days, it actually\Ntakes a few microseconds on a modern
Dialogue: 0,0:12:07.16,0:12:11.26,Default,,0000,0000,0000,,computer. But still, microseconds for a,\Nfor a, say a four gigahertz processor is
Dialogue: 0,0:12:11.26,0:12:15.09,Default,,0000,0000,0000,,quite a bit of work. And so just keep in\Nmind that all the exponentiation
Dialogue: 0,0:12:15.09,0:12:19.56,Default,,0000,0000,0000,,operations we talked about. For example,\Nfor determining if a number is a quadratic
Dialogue: 0,0:12:19.56,0:12:23.60,Default,,0000,0000,0000,,residue or not, All those, all those\Nexponentiations basically take cubic time.
Dialogue: 0,0:12:24.78,0:12:29.68,Default,,0000,0000,0000,,Okay, so that completes our discussion of\Narithmetic algorithms, and then in the
Dialogue: 0,0:12:29.68,0:12:34.08,Default,,0000,0000,0000,,next segment we'll start talking about\Nhard problems, modulo, primes and composites.