1 00:00:00,000 --> 00:00:03,870 PROFESSOR: So if you want to hand in your problem sets, we 2 00:00:03,870 --> 00:00:05,610 have three handouts. 3 00:00:05,610 --> 00:00:10,305 The old problem set solutions, the new problem set, and we're 4 00:00:10,305 --> 00:00:12,536 also handing out chapter eight today. 5 00:00:12,536 --> 00:00:14,370 Of course, these are all on the web. 6 00:00:14,370 --> 00:00:17,060 7 00:00:17,060 --> 00:00:19,490 Reminders of previously announced events. 8 00:00:19,490 --> 00:00:20,970 Next week I'm going to be away. 9 00:00:20,970 --> 00:00:25,540 Ralf Koetter will be a much-improved substitute. 10 00:00:25,540 --> 00:00:28,790 He'll be talking about Reed-Solomon codes and 11 00:00:28,790 --> 00:00:30,090 Reed-Solomon decoding. 12 00:00:30,090 --> 00:00:33,100 He's one of the world experts on these things. 13 00:00:33,100 --> 00:00:34,630 He's a great lecturer. 14 00:00:34,630 --> 00:00:39,180 So you're really lucky, I believe. 15 00:00:39,180 --> 00:00:42,030 I will, of course, look at the video afterwards and see how 16 00:00:42,030 --> 00:00:45,580 he did, but I'm sure he'll do it better than I 17 00:00:45,580 --> 00:00:46,940 would have done it. 18 00:00:46,940 --> 00:00:49,205 And midterm is in two weeks. 19 00:00:49,205 --> 00:00:52,870 20 00:00:52,870 --> 00:00:55,480 That's just a reminder. 21 00:00:55,480 --> 00:00:58,770 When I come back, we'll have a Monday class to go over 22 00:00:58,770 --> 00:01:02,570 anything that Ralf may have missed, or really anything in 23 00:01:02,570 --> 00:01:05,300 the whole course up through chapter eight. 24 00:01:05,300 --> 00:01:08,490 You can bring questions in to that. 25 00:01:08,490 --> 00:01:13,330 I don't know how much I feel I'll need to embellish and 26 00:01:13,330 --> 00:01:15,800 cover, so I don't know how much time 27 00:01:15,800 --> 00:01:16,870 there will be for questions. 28 00:01:16,870 --> 00:01:19,690 But that can be a fairly free form lecture. 29 00:01:19,690 --> 00:01:22,620 And then Ashish is going to run a review session on the 30 00:01:22,620 --> 00:01:27,560 Tuesday with exactly the same purpose. 31 00:01:27,560 --> 00:01:31,431 So hopefully that'll put you in good shape for the midterm. 32 00:01:31,431 --> 00:01:34,440 We have to make up the midterm. 33 00:01:34,440 --> 00:01:37,660 No idea what's going to be on the midterm yet. 34 00:01:37,660 --> 00:01:39,460 OK. 35 00:01:39,460 --> 00:01:43,350 Any questions about these things? 36 00:01:43,350 --> 00:01:46,280 Homework processes going OK? 37 00:01:46,280 --> 00:01:48,890 Office hours? 38 00:01:48,890 --> 00:01:50,060 Solutions? 39 00:01:50,060 --> 00:01:52,010 Everything seems to be all right so far? 40 00:01:52,010 --> 00:01:53,260 Good. 41 00:01:53,260 --> 00:01:55,800 42 00:01:55,800 --> 00:01:57,270 We're in chapter seven. 43 00:01:57,270 --> 00:01:59,580 I certainly plan to complete it today. 44 00:01:59,580 --> 00:02:04,380 I'm not going to cover all of chapter seven, but the key 45 00:02:04,380 --> 00:02:06,260 elements that I want you to know. 46 00:02:06,260 --> 00:02:08,070 You're responsible only for what's covered in 47 00:02:08,070 --> 00:02:10,930 class, by the way. 48 00:02:10,930 --> 00:02:15,205 We've talked about a lot of algebraic objects. 49 00:02:15,205 --> 00:02:18,190 50 00:02:18,190 --> 00:02:22,590 Our main emphasis has been to get the finite field, and at 51 00:02:22,590 --> 00:02:25,120 this point, we have prime fields. 52 00:02:25,120 --> 00:02:27,970 Fields with a prime number p of elements. 53 00:02:27,970 --> 00:02:33,410 And we find that we can construct such a field by 54 00:02:33,410 --> 00:02:36,500 taking the integers mod p. 55 00:02:36,500 --> 00:02:38,830 You can write that as z mod p z. 56 00:02:38,830 --> 00:02:42,830 You can equally well consider this as the equivalence 57 00:02:42,830 --> 00:02:52,040 classes of integers of the cosets of pz nz which are each 58 00:02:52,040 --> 00:02:57,050 identified by a remainder or residue r between 59 00:02:57,050 --> 00:03:02,430 0 and p minus 1. 60 00:03:02,430 --> 00:03:02,840 OK. 61 00:03:02,840 --> 00:03:06,630 So basically, the elements of the field are these remainders 62 00:03:06,630 --> 00:03:09,560 or these cosets. 63 00:03:09,560 --> 00:03:10,950 There are p of them. 64 00:03:10,950 --> 00:03:16,080 We do arithmetic by simply doing mod p addition and 65 00:03:16,080 --> 00:03:17,510 multiplication. 66 00:03:17,510 --> 00:03:22,190 So if you understand arithmetic mod p, you 67 00:03:22,190 --> 00:03:24,710 understand this field. 68 00:03:24,710 --> 00:03:27,475 Yes? 69 00:03:27,475 --> 00:03:31,100 AUDIENCE: Is Fp and Zp isomorphic? 70 00:03:31,100 --> 00:03:34,020 PROFESSOR: As an additive group, it's isomorphic to Zp. 71 00:03:34,020 --> 00:03:37,960 Zp we use that notation for the group. 72 00:03:37,960 --> 00:03:40,650 We use this notation for the field. 73 00:03:40,650 --> 00:03:45,170 And I write Zp is isomorphic to Z mod pZ 74 00:03:45,170 --> 00:03:46,580 as a quotient group. 75 00:03:46,580 --> 00:03:49,920 Here I've added in the multiplication operation mod p 76 00:03:49,920 --> 00:03:51,970 to make this a field. 77 00:03:51,970 --> 00:03:57,290 So this is somewhat more than just a quotient group. 78 00:03:57,290 --> 00:04:00,050 Sorry. 79 00:04:00,050 --> 00:04:04,210 The notation is supposed to be more suggestive than precise. 80 00:04:04,210 --> 00:04:06,560 This is not a math class. 81 00:04:06,560 --> 00:04:08,485 I hope it's helpful rather than otherwise. 82 00:04:08,485 --> 00:04:12,170 83 00:04:12,170 --> 00:04:12,570 OK. 84 00:04:12,570 --> 00:04:16,100 So today, we're going to construct all the rest of the 85 00:04:16,100 --> 00:04:19,060 finite fields. 86 00:04:19,060 --> 00:04:23,330 By the way, we showed that these are the only fields with 87 00:04:23,330 --> 00:04:25,090 a prime number of elements. 88 00:04:25,090 --> 00:04:31,240 Today we're going to construct fields with a prime power 89 00:04:31,240 --> 00:04:36,240 number of elements in a very analogous way, and it will 90 00:04:36,240 --> 00:04:38,460 turn out -- although I'm not going to prove this -- that 91 00:04:38,460 --> 00:04:43,790 these are the only finite fields. 92 00:04:43,790 --> 00:04:47,240 Well, these are generalization of this, so all finite fields 93 00:04:47,240 --> 00:04:50,090 have a prime power number of elements and are basically 94 00:04:50,090 --> 00:04:53,040 isomorphic to one of these fields. 95 00:04:53,040 --> 00:04:56,990 96 00:04:56,990 --> 00:04:59,090 How do we construct this field? 97 00:04:59,090 --> 00:05:03,660 To give you a preview, very analogously to the way we 98 00:05:03,660 --> 00:05:05,450 constructed this field. 99 00:05:05,450 --> 00:05:09,130 You'll see that the character of the arguments is 100 00:05:09,130 --> 00:05:10,670 very much the same. 101 00:05:10,670 --> 00:05:14,770 And that's because there is a great algebraic similarity 102 00:05:14,770 --> 00:05:20,030 between the integers and the polynomials over a field. 103 00:05:20,030 --> 00:05:22,220 And we'll talk about that in a second. 104 00:05:22,220 --> 00:05:27,520 Basically, they're both countably infinite rings, or 105 00:05:27,520 --> 00:05:29,060 infinite rings. 106 00:05:29,060 --> 00:05:33,250 Countably infinite if it's over a finite field. 107 00:05:33,250 --> 00:05:36,960 And they both have analogous factorization properties. 108 00:05:36,960 --> 00:05:39,900 They're both unique factorization domains, would 109 00:05:39,900 --> 00:05:45,690 be one characterization, algebraically. 110 00:05:45,690 --> 00:05:46,230 All right. 111 00:05:46,230 --> 00:05:47,850 How do we construct this field? 112 00:05:47,850 --> 00:05:50,540 We're basically going to construct it by taking the set 113 00:05:50,540 --> 00:05:56,320 of all polynomials over Fp which is denoted by Fp square 114 00:05:56,320 --> 00:05:58,510 brackets x. 115 00:05:58,510 --> 00:06:03,690 And we're going to take that mod the set of all polynomials 116 00:06:03,690 --> 00:06:08,080 that are divisible by G of x, or G of x times the set of all 117 00:06:08,080 --> 00:06:08,820 polynomials. 118 00:06:08,820 --> 00:06:12,500 The set of all multiples of G of x. 119 00:06:12,500 --> 00:06:15,110 Or more simply, just mod G of x. 120 00:06:15,110 --> 00:06:19,910 Where we're going to take G of x to be a prime polynomial. 121 00:06:19,910 --> 00:06:26,060 And I guess I have to add that the degree of G of x is going 122 00:06:26,060 --> 00:06:28,320 to be equal to m. 123 00:06:28,320 --> 00:06:32,080 So we basically need to find a prime polynomial degree m. 124 00:06:32,080 --> 00:06:36,620 Then we take the set of all polynomials modulo this prime 125 00:06:36,620 --> 00:06:37,800 polynomial. 126 00:06:37,800 --> 00:06:41,970 They're going to be exactly p to the m residue classes, or 127 00:06:41,970 --> 00:06:47,070 equivalence classes, or remainders modulo g of x. 128 00:06:47,070 --> 00:06:51,290 And we'll use the arithmetic operations from mod G of x 129 00:06:51,290 --> 00:06:55,680 arithmetic, addition mod G of x, multiplication mod G of x, 130 00:06:55,680 --> 00:06:59,910 and we'll find that the resulting object has satisfied 131 00:06:59,910 --> 00:07:02,170 the axioms of the field. 132 00:07:02,170 --> 00:07:02,550 OK? 133 00:07:02,550 --> 00:07:05,026 So that's where we're going. 134 00:07:05,026 --> 00:07:08,210 You with me? 135 00:07:08,210 --> 00:07:08,630 OK. 136 00:07:08,630 --> 00:07:10,710 So let's talk about factorization. 137 00:07:10,710 --> 00:07:18,330 And I think it makes it easy to understand polynomials if 138 00:07:18,330 --> 00:07:22,530 we understand the analogies to the integers. 139 00:07:22,530 --> 00:07:25,960 In particular where I'm headed is unique factorization. 140 00:07:25,960 --> 00:07:28,740 141 00:07:28,740 --> 00:07:32,450 Both the integers and the polynomials have unique 142 00:07:32,450 --> 00:07:33,230 factorizations. 143 00:07:33,230 --> 00:07:38,210 The integers into product of integers, and any polynomial 144 00:07:38,210 --> 00:07:42,010 is uniquely factorizable into a product of polynomials. 145 00:07:42,010 --> 00:07:45,300 Now I wasn't quite precise when I said that. 146 00:07:45,300 --> 00:07:52,560 We have to be a little bit more precise when we talk 147 00:07:52,560 --> 00:07:53,810 about factorization. 148 00:07:53,810 --> 00:07:55,810 149 00:07:55,810 --> 00:07:59,600 In particular, we have a certain kind of trivial 150 00:07:59,600 --> 00:08:02,870 factorization that involves units. 151 00:08:02,870 --> 00:08:06,470 Units, if you remember, are the invertible elements. 152 00:08:06,470 --> 00:08:09,870 We're in a ring, so not every element has an inverse, but 153 00:08:09,870 --> 00:08:11,120 some of them do. 154 00:08:11,120 --> 00:08:13,170 155 00:08:13,170 --> 00:08:17,930 And in the integers, what were the invertible integers under 156 00:08:17,930 --> 00:08:19,030 multiplication? 157 00:08:19,030 --> 00:08:22,910 Everything here is about multiplication, you know? 158 00:08:22,910 --> 00:08:28,220 A ring is something that satisfies all of the 159 00:08:28,220 --> 00:08:32,710 properties of the field, except that some of the 160 00:08:32,710 --> 00:08:35,039 elements don't have inverses, so that division is not 161 00:08:35,039 --> 00:08:39,850 necessarily well-defined, even for non-zero elements. 162 00:08:39,850 --> 00:08:40,250 OK? 163 00:08:40,250 --> 00:08:41,440 Sorry. 164 00:08:41,440 --> 00:08:42,919 I think I said that before. 165 00:08:42,919 --> 00:08:46,430 But we're not emphasizing that these are rings, 166 00:08:46,430 --> 00:08:47,515 although they are. 167 00:08:47,515 --> 00:08:48,775 That's an informal definition. 168 00:08:48,775 --> 00:08:51,650 169 00:08:51,650 --> 00:08:55,260 So in the integers, of course 12 doesn't have a 170 00:08:55,260 --> 00:08:58,480 multiplicative inverse, but it's an integer. 171 00:08:58,480 --> 00:09:00,805 But which integers do have multiplicative inverses? 172 00:09:00,805 --> 00:09:03,680 173 00:09:03,680 --> 00:09:04,930 Plus or minus 1. 174 00:09:04,930 --> 00:09:07,980 175 00:09:07,980 --> 00:09:11,950 So if an integer is divisible by n, it's also 176 00:09:11,950 --> 00:09:14,880 divisible by minus n. 177 00:09:14,880 --> 00:09:16,350 All right? 178 00:09:16,350 --> 00:09:18,870 Trivially. 179 00:09:18,870 --> 00:09:21,370 These are the only ones in the integers. 180 00:09:21,370 --> 00:09:24,210 And last time we actually talked, if I remember 181 00:09:24,210 --> 00:09:27,320 correctly, about the units and the polynomials. 182 00:09:27,320 --> 00:09:29,800 Which polynomials have inverses? 183 00:09:29,800 --> 00:09:33,970 184 00:09:33,970 --> 00:09:34,056 Excuse me. 185 00:09:34,056 --> 00:09:34,930 The degree 0. 186 00:09:34,930 --> 00:09:36,180 Thank you. 187 00:09:36,180 --> 00:09:40,480 188 00:09:40,480 --> 00:09:45,760 The degree 0 polynomials have inverses because they are 189 00:09:45,760 --> 00:09:48,390 basically the non-zero elements of the field. 190 00:09:48,390 --> 00:09:51,070 191 00:09:51,070 --> 00:09:51,320 OK? 192 00:09:51,320 --> 00:09:55,440 It's slight abuse of notation. 193 00:09:55,440 --> 00:09:58,500 We identify the field elements with the degree zero 194 00:09:58,500 --> 00:09:59,250 polynomials. 195 00:09:59,250 --> 00:10:03,710 These are polynomials just of the form F of x equals F_0 a 196 00:10:03,710 --> 00:10:05,940 constant, where the constant is non-zero. 197 00:10:05,940 --> 00:10:08,570 198 00:10:08,570 --> 00:10:08,990 OK. 199 00:10:08,990 --> 00:10:17,960 So similarly, we will have to have representatives of 200 00:10:17,960 --> 00:10:20,370 equivalence classes with respect to the units. 201 00:10:20,370 --> 00:10:23,620 202 00:10:23,620 --> 00:10:29,330 So if both plus or minus n divide something, what we take 203 00:10:29,330 --> 00:10:34,704 as the representative is we take the positive integers. 204 00:10:34,704 --> 00:10:37,690 When we talk about divisibility, we talk only 205 00:10:37,690 --> 00:10:42,700 about divisibility by positive integers or factorization by 206 00:10:42,700 --> 00:10:43,720 positive integers. 207 00:10:43,720 --> 00:10:47,650 It's trivial that if something is divisible by n, it's also 208 00:10:47,650 --> 00:10:49,680 divisible by minus n. 209 00:10:49,680 --> 00:10:56,400 Similarly for polynomials, the representatives are taken as 210 00:10:56,400 --> 00:10:57,650 mnemonic polynomials. 211 00:10:57,650 --> 00:11:03,880 212 00:11:03,880 --> 00:11:09,790 And this means that the highest order term, Fm is 213 00:11:09,790 --> 00:11:11,040 equal to 1. 214 00:11:11,040 --> 00:11:17,620 215 00:11:17,620 --> 00:11:23,600 So we can take any polynomial, and by multiplying it by one 216 00:11:23,600 --> 00:11:29,050 of these invertible elements, basically by a non-zero 217 00:11:29,050 --> 00:11:33,420 constant in the ground field, we can make the highest order 218 00:11:33,420 --> 00:11:34,500 term equal to 1. 219 00:11:34,500 --> 00:11:35,400 Right? 220 00:11:35,400 --> 00:11:41,990 So if a polynomial is divisible by F of x, it's also 221 00:11:41,990 --> 00:11:46,750 divisible by alpha F of x, where alpha is any non-zero 222 00:11:46,750 --> 00:11:49,490 field element, right? 223 00:11:49,490 --> 00:11:54,230 And so we may as well fix the highest order coefficient 224 00:11:54,230 --> 00:11:55,610 equal to 1. 225 00:11:55,610 --> 00:11:59,390 Actually, for some purposes in the literature, like you've 226 00:11:59,390 --> 00:12:04,560 probably seen this in filter design, or we always make the 227 00:12:04,560 --> 00:12:06,490 lowest order coefficient equal to one. 228 00:12:06,490 --> 00:12:08,060 F0 equal to 1. 229 00:12:08,060 --> 00:12:11,990 You could also adopt that convention, and say that 230 00:12:11,990 --> 00:12:16,530 that's going to be a mnemonic polynomial. 231 00:12:16,530 --> 00:12:19,120 Here we'll focus on the high order coefficient, but you 232 00:12:19,120 --> 00:12:21,720 could do it either way. 233 00:12:21,720 --> 00:12:25,380 And these both have the nice property that the product of 234 00:12:25,380 --> 00:12:28,080 positive integers is a positive integer. 235 00:12:28,080 --> 00:12:30,640 The product of monic polynomials is a monic 236 00:12:30,640 --> 00:12:33,450 polynomial, right? 237 00:12:33,450 --> 00:12:36,440 The highest order term of the product is going to have a 238 00:12:36,440 --> 00:12:38,880 highest order term equal to 1. 239 00:12:38,880 --> 00:12:40,520 Or if you chose the lowest order one, 240 00:12:40,520 --> 00:12:41,560 that would work, too. 241 00:12:41,560 --> 00:12:46,920 The lowest order term of the product would be equal to 1. 242 00:12:46,920 --> 00:12:47,390 All right. 243 00:12:47,390 --> 00:12:52,340 So having recognized this, when we talk about unique 244 00:12:52,340 --> 00:12:55,930 factorization, just as with the integers, what we really 245 00:12:55,930 --> 00:12:58,820 mean is factorization of a positive integer into a 246 00:12:58,820 --> 00:13:00,720 product of positive integers. 247 00:13:00,720 --> 00:13:03,280 It's unique up to units. 248 00:13:03,280 --> 00:13:09,040 We can always put units either on the integer that we're 249 00:13:09,040 --> 00:13:13,730 factoring or on any of the factors, and we can freely 250 00:13:13,730 --> 00:13:16,180 multiply any of these things by units, and it won't affect 251 00:13:16,180 --> 00:13:18,670 the factorization. 252 00:13:18,670 --> 00:13:21,920 Similarly over here, when we talk about unique 253 00:13:21,920 --> 00:13:25,090 factorization, we mean unique up to units. 254 00:13:25,090 --> 00:13:27,730 We're basically going to talk about the factorization of 255 00:13:27,730 --> 00:13:35,250 monic polynomials into a product of monic polynomials. 256 00:13:35,250 --> 00:13:41,100 257 00:13:41,100 --> 00:13:43,560 Not getting a real positive feeling that everybody's 258 00:13:43,560 --> 00:13:43,980 following me. 259 00:13:43,980 --> 00:13:46,020 Would it help if I wrote down more things, 260 00:13:46,020 --> 00:13:47,270 or wrote some examples? 261 00:13:47,270 --> 00:13:53,670 262 00:13:53,670 --> 00:13:57,770 In F2 of x, for instance, we have -- 263 00:13:57,770 --> 00:13:59,940 well, this isn't a very good example. 264 00:13:59,940 --> 00:14:05,070 Let's write R of x. 265 00:14:05,070 --> 00:14:06,320 OK? 266 00:14:06,320 --> 00:14:08,080 267 00:14:08,080 --> 00:14:10,910 We're going to talk about factorizations like this. x 268 00:14:10,910 --> 00:14:17,900 squared minus 1 equals x minus 1 times x plus 1. 269 00:14:17,900 --> 00:14:21,730 That's a factorization of a monic polynomial into a 270 00:14:21,730 --> 00:14:27,990 product of monic polynomials of a lower degree. 271 00:14:27,990 --> 00:14:29,160 Happens in F2 of x. 272 00:14:29,160 --> 00:14:32,560 Since there is only one non-zero field element, then 273 00:14:32,560 --> 00:14:36,164 all polynomials are monic, except for the 0 polynomial. 274 00:14:36,164 --> 00:14:39,070 275 00:14:39,070 --> 00:14:41,540 The only non-zero term we have play with is one. 276 00:14:41,540 --> 00:14:45,082 So the highest order non-zero term is always 1. 277 00:14:45,082 --> 00:14:48,000 All right. 278 00:14:48,000 --> 00:14:48,095 OK. 279 00:14:48,095 --> 00:14:51,440 So that's what we're going to mean by unique factorization. 280 00:14:51,440 --> 00:14:55,200 Now, there's one other qualifier. 281 00:14:55,200 --> 00:14:56,640 There's some trivial factors. 282 00:14:56,640 --> 00:15:04,760 283 00:15:04,760 --> 00:15:10,190 We took some care to use the standard mathematical 284 00:15:10,190 --> 00:15:13,580 terminology in the notes, so if it says trivial devisors, 285 00:15:13,580 --> 00:15:14,330 then that's what I mean. 286 00:15:14,330 --> 00:15:18,280 What would the trivial divisors of integer n be? 287 00:15:18,280 --> 00:15:23,450 288 00:15:23,450 --> 00:15:27,160 1 and n are always going to divide in. 289 00:15:27,160 --> 00:15:29,000 And we're really not interested in those when we 290 00:15:29,000 --> 00:15:30,250 talk about factorization. 291 00:15:30,250 --> 00:15:34,210 292 00:15:34,210 --> 00:15:36,820 Similarly, over here, the trivial divisor of a 293 00:15:36,820 --> 00:15:41,740 polynomial F of x are 1 and F of x. 294 00:15:41,740 --> 00:15:43,060 We're not interested in those. 295 00:15:43,060 --> 00:15:46,570 296 00:15:46,570 --> 00:15:53,340 So when we talk about unique factorization, we mean up to 297 00:15:53,340 --> 00:15:59,010 units and nontrivial factors. 298 00:15:59,010 --> 00:16:04,100 299 00:16:04,100 --> 00:16:07,400 And for the integers, that means that we're going to talk 300 00:16:07,400 --> 00:16:13,980 about divisors d, let's say, such that d is 301 00:16:13,980 --> 00:16:15,360 between 1 and n. 302 00:16:15,360 --> 00:16:21,080 303 00:16:21,080 --> 00:16:26,440 And for polynomials, what this means is we're not interested 304 00:16:26,440 --> 00:16:29,200 in degree 0 factors. 305 00:16:29,200 --> 00:16:34,630 The only factor of degree the same as F of x is going to be 306 00:16:34,630 --> 00:16:37,070 F of x up to units. 307 00:16:37,070 --> 00:16:44,010 We're interested in divisors d of x such that the degree that 308 00:16:44,010 --> 00:16:50,200 0 is less than the degree of the divisor less than the 309 00:16:50,200 --> 00:16:53,685 degree of what it's dividing into. 310 00:16:53,685 --> 00:16:54,090 Sorry. 311 00:16:54,090 --> 00:16:57,290 I'm not defining everything, but I hope that's clear. 312 00:16:57,290 --> 00:17:02,480 We're just interested in factors that have degree less 313 00:17:02,480 --> 00:17:05,910 than the polynomial that we're factoring, but we're not 314 00:17:05,910 --> 00:17:07,310 interested in degree 0 factors. 315 00:17:07,310 --> 00:17:10,349 316 00:17:10,349 --> 00:17:14,109 So that's what's meant by unique factorization. 317 00:17:14,109 --> 00:17:17,585 It also shows you the analogy in general. 318 00:17:17,585 --> 00:17:20,280 319 00:17:20,280 --> 00:17:27,269 In the case of integers, the key thing in a divisor is that 320 00:17:27,269 --> 00:17:31,670 it have magnitude between 1 and n. 321 00:17:31,670 --> 00:17:37,370 The key thing in a polynomial is it have degree between 0 322 00:17:37,370 --> 00:17:41,370 and the degree of F of x. 323 00:17:41,370 --> 00:17:45,790 Basically, we want to factor something into 324 00:17:45,790 --> 00:17:47,240 smaller things here. 325 00:17:47,240 --> 00:17:49,850 And when we say smaller, we talk about magnitude. 326 00:17:49,850 --> 00:17:52,680 Here when we say smaller, we're talking about degrees. 327 00:17:52,680 --> 00:17:54,650 In general, we go between these two things. 328 00:17:54,650 --> 00:17:57,780 The concept of magnitude is replaced by the concept of 329 00:17:57,780 --> 00:18:01,350 degree, to say how big something is. 330 00:18:01,350 --> 00:18:05,120 331 00:18:05,120 --> 00:18:11,600 In both of these, the key to all proofs is the Euclidean 332 00:18:11,600 --> 00:18:12,850 division algorithm. 333 00:18:12,850 --> 00:18:24,510 334 00:18:24,510 --> 00:18:33,810 Suppose we want to see if n is a divisor of m. 335 00:18:33,810 --> 00:18:36,965 I've forgotten what I put in the notes. 336 00:18:36,965 --> 00:18:41,380 Then we go through division, and we find that m is equal to 337 00:18:41,380 --> 00:18:46,440 q, some quotient times n, plus a remainder r. 338 00:18:46,440 --> 00:18:49,190 This is standard grade school division. 339 00:18:49,190 --> 00:18:52,520 But it's really the key in the universe in talking about 340 00:18:52,520 --> 00:18:55,680 these two domains. 341 00:18:55,680 --> 00:18:58,440 And this is what we've used, really, to prove everything 342 00:18:58,440 --> 00:19:02,270 about the factorization properties of integers. 343 00:19:02,270 --> 00:19:07,400 And how would you actually prove that everything can be 344 00:19:07,400 --> 00:19:08,050 written this way? 345 00:19:08,050 --> 00:19:09,510 There's an important caveat. 346 00:19:09,510 --> 00:19:13,730 That the remainder we can always choose to have to be in 347 00:19:13,730 --> 00:19:16,180 the range from 0 less than r less than or 348 00:19:16,180 --> 00:19:19,380 equal to n minus 1. 349 00:19:19,380 --> 00:19:23,920 And the remainder is what we call m mod n. 350 00:19:23,920 --> 00:19:28,340 351 00:19:28,340 --> 00:19:31,910 We divide and we get a remainder that's one of these 352 00:19:31,910 --> 00:19:37,030 n things, and that's the main thing we get out of this 353 00:19:37,030 --> 00:19:44,080 division, is m mod n, which is equal to the remainder r. 354 00:19:44,080 --> 00:19:47,070 And there are precisely n remainders. 355 00:19:47,070 --> 00:19:49,340 Now, how do you actually prove this? 356 00:19:49,340 --> 00:19:51,600 You prove this, if you want, very 357 00:19:51,600 --> 00:19:55,310 easily, just by recursion. 358 00:19:55,310 --> 00:20:03,630 You take m, and you ask, is it already in this range? 359 00:20:03,630 --> 00:20:05,740 If it is, you're done. 360 00:20:05,740 --> 00:20:08,850 m is the remainder and q is zero. 361 00:20:08,850 --> 00:20:13,510 If not, then you subtract n from m, thereby reducing the 362 00:20:13,510 --> 00:20:14,410 magnitude of m. 363 00:20:14,410 --> 00:20:17,850 You can use the magnitude as an indicator of how far you've 364 00:20:17,850 --> 00:20:19,720 gotten in this process. 365 00:20:19,720 --> 00:20:25,220 You reduce the magnitude, and then you ask, is the result in 366 00:20:25,220 --> 00:20:28,070 this range? 367 00:20:28,070 --> 00:20:28,180 OK. 368 00:20:28,180 --> 00:20:32,140 If it's in that range, fine, you finish this and q is 1. 369 00:20:32,140 --> 00:20:34,170 Otherwise, you continue. 370 00:20:34,170 --> 00:20:36,980 And in the recursion, you're continually reducing the 371 00:20:36,980 --> 00:20:40,870 magnitude, and it's easy to show that eventually, the 372 00:20:40,870 --> 00:20:44,990 magnitude has to fall into this range and be one of these 373 00:20:44,990 --> 00:20:50,060 n remainder numbers, and then you're done. 374 00:20:50,060 --> 00:20:50,550 OK? 375 00:20:50,550 --> 00:20:53,290 So it's a descending chain where the chain 376 00:20:53,290 --> 00:20:54,880 has a bottom at 0. 377 00:20:54,880 --> 00:20:58,020 If you start with a positive integer, you can't go below 0. 378 00:20:58,020 --> 00:20:59,790 And this is the only way it can come out. 379 00:20:59,790 --> 00:21:01,040 Very easy to prove that. 380 00:21:01,040 --> 00:21:03,420 381 00:21:03,420 --> 00:21:03,850 All right. 382 00:21:03,850 --> 00:21:09,950 Similarly in polynomials, we get an analogous expression. 383 00:21:09,950 --> 00:21:16,340 If we want to take F of x and see if G of x is a divisor, we 384 00:21:16,340 --> 00:21:21,220 take F of x, and we can always write this as some quotient 385 00:21:21,220 --> 00:21:25,900 times G of x plus some remainder. 386 00:21:25,900 --> 00:21:28,770 Where the important thing here about the remainder is that 387 00:21:28,770 --> 00:21:33,220 the degree of the remainder is less than the 388 00:21:33,220 --> 00:21:36,460 degree of G of x. 389 00:21:36,460 --> 00:21:42,245 And here the remainder is called F of x mod G of x. 390 00:21:42,245 --> 00:21:45,310 391 00:21:45,310 --> 00:21:51,750 Just as the remainder here is called m mod n. 392 00:21:51,750 --> 00:21:54,790 393 00:21:54,790 --> 00:22:00,190 And there's a unique remainder. 394 00:22:00,190 --> 00:22:05,900 And again, how would you prove this? 395 00:22:05,900 --> 00:22:08,580 You could just take any long division algorithm that you 396 00:22:08,580 --> 00:22:15,150 know for dividing G of x into F of x. 397 00:22:15,150 --> 00:22:19,920 Basically long division amounts to taking F of x. 398 00:22:19,920 --> 00:22:27,650 You can always choose some scalar multiple of G of x such 399 00:22:27,650 --> 00:22:33,360 that F of x minus alpha G of x has degree less than F of x. 400 00:22:33,360 --> 00:22:37,770 So you pick the top term to reduce the degree, all right? 401 00:22:37,770 --> 00:22:39,370 Let's take G of x to be monic. 402 00:22:39,370 --> 00:22:42,100 We're only interested in monic polynomials. 403 00:22:42,100 --> 00:22:45,180 If the top term of F of x is -- well, we're only going to 404 00:22:45,180 --> 00:22:48,520 divide it into monic polynomials. 405 00:22:48,520 --> 00:22:51,190 But as we go along, we may get non-monic ones. 406 00:22:51,190 --> 00:22:55,260 So you take the top term, whatever it 407 00:22:55,260 --> 00:22:56,930 is over here, f(m). 408 00:22:56,930 --> 00:22:59,390 You multiply f(m) times g of x. 409 00:22:59,390 --> 00:23:02,220 You subtract f(m) g of x from f of x. 410 00:23:02,220 --> 00:23:04,208 You reduce the degree. 411 00:23:04,208 --> 00:23:05,196 OK? 412 00:23:05,196 --> 00:23:06,446 AUDIENCE: [INAUDIBLE PHRASE]. 413 00:23:06,446 --> 00:23:10,730 414 00:23:10,730 --> 00:23:12,680 PROFESSOR: Correct. 415 00:23:12,680 --> 00:23:13,570 Thank you very much. 416 00:23:13,570 --> 00:23:18,740 You need also a term x to whatever the difference in 417 00:23:18,740 --> 00:23:24,256 degrees is here to move the degree up to the top. 418 00:23:24,256 --> 00:23:28,803 When we're actually doing long division, we write f(m) f(m 419 00:23:28,803 --> 00:23:32,220 minus 1) down to f(0). 420 00:23:32,220 --> 00:23:38,310 We divide g(n) down to g(1). 421 00:23:38,310 --> 00:23:42,770 And the first term, g(n) is going to be equal to 1. 422 00:23:42,770 --> 00:23:45,410 We take f(m) up here. 423 00:23:45,410 --> 00:23:54,189 We implicitly move it over to get f(m) dot dot dot dot, down 424 00:23:54,189 --> 00:23:55,890 to f(m) alpha. 425 00:23:55,890 --> 00:24:00,060 We subtract, and we're down to something that only has 426 00:24:00,060 --> 00:24:01,250 degree m minus 1. 427 00:24:01,250 --> 00:24:06,440 That's what polynomial long division is shorthand for. 428 00:24:06,440 --> 00:24:10,130 429 00:24:10,130 --> 00:24:13,470 So you all know how to do this. 430 00:24:13,470 --> 00:24:14,010 OK. 431 00:24:14,010 --> 00:24:18,790 Again, similar kind of proof, that you must be able to get a 432 00:24:18,790 --> 00:24:20,890 remainder in this range, and furthermore, the 433 00:24:20,890 --> 00:24:22,140 remainder is unique. 434 00:24:22,140 --> 00:24:25,040 435 00:24:25,040 --> 00:24:27,390 You basically can go through this process. 436 00:24:27,390 --> 00:24:30,220 You reduce the degree by at least one every time. 437 00:24:30,220 --> 00:24:33,030 438 00:24:33,030 --> 00:24:38,960 Therefore, degree must eventually be reduced to where 439 00:24:38,960 --> 00:24:41,090 it's less than degree g of x. 440 00:24:41,090 --> 00:24:46,560 At that point, you can't continue this process. 441 00:24:46,560 --> 00:24:47,640 You're stuck. 442 00:24:47,640 --> 00:24:48,730 And that's your remainder. 443 00:24:48,730 --> 00:24:51,780 There's no way of taking something of lesser degree of 444 00:24:51,780 --> 00:24:54,770 g of x and then subtracting some multiple from g of x from 445 00:24:54,770 --> 00:24:58,160 it to still further reduce the degree. 446 00:24:58,160 --> 00:24:58,570 All right. 447 00:24:58,570 --> 00:25:00,490 So similar proof. 448 00:25:00,490 --> 00:25:03,160 Uniqueness is pretty obvious. 449 00:25:03,160 --> 00:25:10,080 So you get a unique remainder of lesser degree than g of x. 450 00:25:10,080 --> 00:25:20,810 And so you can reduce any f of x to some remainder r of x, 451 00:25:20,810 --> 00:25:22,270 which is called f of x mod g of x. 452 00:25:22,270 --> 00:25:30,840 453 00:25:30,840 --> 00:25:39,490 And if we do arithmetic, the way we do arithmetic over here 454 00:25:39,490 --> 00:25:43,770 for addition is we just, if we want to add two remainders mod 455 00:25:43,770 --> 00:25:47,310 n, we take the sum of them, and then if necessary, reduce 456 00:25:47,310 --> 00:25:49,610 them mod n. 457 00:25:49,610 --> 00:25:50,846 Similarly with multiplication. 458 00:25:50,846 --> 00:25:54,040 If we want to multiply them, we take the product of two 459 00:25:54,040 --> 00:25:57,320 remainders, and if necessary, reduce them again to a 460 00:25:57,320 --> 00:26:02,272 legitimate remainder which is in this range or to mod n. 461 00:26:02,272 --> 00:26:05,270 It's the same over here. 462 00:26:05,270 --> 00:26:10,450 If we want to add two 463 00:26:10,450 --> 00:26:13,490 remainders, that's easy enough. 464 00:26:13,490 --> 00:26:16,160 We can do that and we won't increase the degree, so we 465 00:26:16,160 --> 00:26:18,850 automatically get something when we add two remainders 466 00:26:18,850 --> 00:26:24,100 that satisfies this degree property. 467 00:26:24,100 --> 00:26:26,060 We don't have to reduce mod g of x. 468 00:26:26,060 --> 00:26:30,060 If we multiply, you do have to check that when you multiply 469 00:26:30,060 --> 00:26:35,900 two remainders, then all you need to do is reduce 470 00:26:35,900 --> 00:26:38,050 the mod g of x. 471 00:26:38,050 --> 00:26:41,440 And basically, the assertion is that -- 472 00:26:41,440 --> 00:26:46,390 473 00:26:46,390 --> 00:26:48,570 let's see. r of x, s of x -- 474 00:26:48,570 --> 00:26:53,520 475 00:26:53,520 --> 00:26:57,300 it's hard to write this without being tautological. 476 00:26:57,300 --> 00:26:59,710 r of x, s of x. 477 00:26:59,710 --> 00:27:06,420 Reduced mod n, I'm sorry, mod g of x. 478 00:27:06,420 --> 00:27:06,670 I'm sorry. 479 00:27:06,670 --> 00:27:08,860 This is not worth writing. 480 00:27:08,860 --> 00:27:11,080 r of x, s of x, mod g of x. 481 00:27:11,080 --> 00:27:15,340 482 00:27:15,340 --> 00:27:18,104 Something like that. 483 00:27:18,104 --> 00:27:18,540 Bah. 484 00:27:18,540 --> 00:27:19,900 It's a total tautology. 485 00:27:19,900 --> 00:27:21,110 Forget it. 486 00:27:21,110 --> 00:27:23,940 Said correctly in the notes. 487 00:27:23,940 --> 00:27:28,710 I'd rather think of it as residue classes. 488 00:27:28,710 --> 00:27:38,512 If we, say, we talk about this as a coset, f of x plus r of 489 00:27:38,512 --> 00:27:43,600 x, and we want to multiply any element. 490 00:27:43,600 --> 00:27:48,160 This coset times any element of the coset f 491 00:27:48,160 --> 00:27:50,520 of x plus s of x. 492 00:27:50,520 --> 00:27:53,030 493 00:27:53,030 --> 00:27:58,500 Then the result is just multiplying out symbolically 494 00:27:58,500 --> 00:28:01,300 the polynomials times the polynomials are the 495 00:28:01,300 --> 00:28:02,810 polynomials. 496 00:28:02,810 --> 00:28:06,180 Any polynomial times a polynomial is a polynomial. 497 00:28:06,180 --> 00:28:08,840 Plus r of x f of x. 498 00:28:08,840 --> 00:28:11,800 We could get some multiple of r of x, 499 00:28:11,800 --> 00:28:12,955 some polynomial multiple. 500 00:28:12,955 --> 00:28:16,130 We could get some polynomial multiple of s of x. 501 00:28:16,130 --> 00:28:19,450 502 00:28:19,450 --> 00:28:22,280 Plus r of x s of x. 503 00:28:22,280 --> 00:28:26,740 504 00:28:26,740 --> 00:28:29,450 But this is a polynomial that's included in here. 505 00:28:29,450 --> 00:28:30,830 We don't need to say that again. 506 00:28:30,830 --> 00:28:32,590 Similarly here. 507 00:28:32,590 --> 00:28:39,310 And so this is equal to f of x. 508 00:28:39,310 --> 00:28:44,360 It's equal to the coset f of x plus r of x s of x. 509 00:28:44,360 --> 00:28:50,190 510 00:28:50,190 --> 00:28:52,900 But this is another polynomial that 511 00:28:52,900 --> 00:28:55,090 probably has higher degree. 512 00:28:55,090 --> 00:29:03,160 This is equal to the coset f of x plus r of x s 513 00:29:03,160 --> 00:29:09,780 of x mod g of x. 514 00:29:09,780 --> 00:29:10,170 OK. 515 00:29:10,170 --> 00:29:17,180 So this tells us that to multiply cosets, coset with 516 00:29:17,180 --> 00:29:20,270 representative r of x times the coset with representative 517 00:29:20,270 --> 00:29:26,120 s of x, we're going to get something in the coset whose 518 00:29:26,120 --> 00:29:31,210 representative is r of x, s of x mod g of x. 519 00:29:31,210 --> 00:29:36,870 So this is a sketch of a proof that basically mod g of x 520 00:29:36,870 --> 00:29:39,830 commutes with multiplication. 521 00:29:39,830 --> 00:29:44,760 To multiply r of x times s of x. 522 00:29:44,760 --> 00:29:45,210 All right. 523 00:29:45,210 --> 00:29:46,460 So -- 524 00:29:46,460 --> 00:29:50,390 525 00:29:50,390 --> 00:29:51,640 AUDIENCE: [INAUDIBLE PHRASE]. 526 00:29:51,640 --> 00:29:58,873 527 00:29:58,873 --> 00:30:00,370 PROFESSOR: Yeah. 528 00:30:00,370 --> 00:30:04,230 You're quite correct. 529 00:30:04,230 --> 00:30:08,220 What I mean is the cosets of g of x of f of x. 530 00:30:08,220 --> 00:30:10,750 So I now understand all the blank looks. 531 00:30:10,750 --> 00:30:18,638 532 00:30:18,638 --> 00:30:20,300 Are we better off now? 533 00:30:20,300 --> 00:30:25,120 534 00:30:25,120 --> 00:30:31,000 We have a group consisting of the set of all multiples of g 535 00:30:31,000 --> 00:30:37,450 of x, which I write as g of x times all the polynomials. 536 00:30:37,450 --> 00:30:40,900 The cosets of the group are precisely -- 537 00:30:40,900 --> 00:30:44,230 there's one remainder of degree less than g of x in 538 00:30:44,230 --> 00:30:44,980 every coset. 539 00:30:44,980 --> 00:30:49,270 So this is the representative of the coset. 540 00:30:49,270 --> 00:30:55,190 This is a sketch of a proof that multiplication basically 541 00:30:55,190 --> 00:30:58,150 just amounts to multiplying the remainders. 542 00:30:58,150 --> 00:31:03,010 The representative of the product coset is the product 543 00:31:03,010 --> 00:31:05,760 of the representatives modulo g of x. 544 00:31:05,760 --> 00:31:09,170 I think I said it correctly for once. 545 00:31:09,170 --> 00:31:12,260 Please read the notes if you are still confused, as I can 546 00:31:12,260 --> 00:31:13,510 see some of you are. 547 00:31:13,510 --> 00:31:24,721 548 00:31:24,721 --> 00:31:26,740 Maybe it would help to do an example. 549 00:31:26,740 --> 00:31:34,480 550 00:31:34,480 --> 00:31:43,670 Let's take g of x to be equal to x squared plus x 551 00:31:43,670 --> 00:31:50,480 plus 1 in f2 of x. 552 00:31:50,480 --> 00:31:54,350 It's a binary polynomial. 553 00:31:54,350 --> 00:32:01,370 Then r of x. 554 00:32:01,370 --> 00:32:12,760 The remainders are equal to 0,1. 555 00:32:12,760 --> 00:32:16,680 This was degree minus infinity, this is degree 0. 556 00:32:16,680 --> 00:32:18,900 They're x or x plus one. 557 00:32:18,900 --> 00:32:23,260 558 00:32:23,260 --> 00:32:24,500 OK? 559 00:32:24,500 --> 00:32:29,650 These are the possible remainders when I take any 560 00:32:29,650 --> 00:32:31,620 polynomial modulo g of x. 561 00:32:31,620 --> 00:32:36,080 Divide it by g of x, and I'm going to get a polynomial in 562 00:32:36,080 --> 00:32:40,340 f2 of x of degree less than or equal to 1, and those are all 563 00:32:40,340 --> 00:32:44,765 of the polynomials that are decisively for degree less 564 00:32:44,765 --> 00:32:47,140 than or equal to 1. 565 00:32:47,140 --> 00:32:49,020 All right? 566 00:32:49,020 --> 00:32:52,340 So what's the addition table? 567 00:32:52,340 --> 00:32:54,026 Addition is pretty easy. 568 00:32:54,026 --> 00:33:07,780 569 00:33:07,780 --> 00:33:09,620 0 plus anything is itself. 570 00:33:09,620 --> 00:33:13,820 571 00:33:13,820 --> 00:33:19,070 1 plus 1 in F2 is simply 0. 572 00:33:19,070 --> 00:33:24,440 1 plus x is 1 plus x, sorry, x plus 1 as I've written. 573 00:33:24,440 --> 00:33:27,750 And 1 plus x plus 1 is x. 574 00:33:27,750 --> 00:33:31,710 x, x plus 1. 575 00:33:31,710 --> 00:33:33,290 x plus x is what? 576 00:33:33,290 --> 00:33:35,890 577 00:33:35,890 --> 00:33:37,136 Hello? 578 00:33:37,136 --> 00:33:37,540 0. 579 00:33:37,540 --> 00:33:38,830 Thank you. 580 00:33:38,830 --> 00:33:42,360 x plus x plus 1? 581 00:33:42,360 --> 00:33:43,392 Thank you. 582 00:33:43,392 --> 00:33:47,080 x plus 1, x. 583 00:33:47,080 --> 00:33:49,770 x plus x plus 1, 1, and 0. 584 00:33:49,770 --> 00:33:52,460 So that's what the addition table looks like. 585 00:33:52,460 --> 00:33:55,150 586 00:33:55,150 --> 00:34:01,770 Actually you could think of these as being just written as 587 00:34:01,770 --> 00:34:10,670 binary pairs, 0 0, 0 1, 1 0, 1 1, where this pair is 588 00:34:10,670 --> 00:34:13,760 basically F1 F0. 589 00:34:13,760 --> 00:34:19,110 And then the addition table is precisely the same as the 590 00:34:19,110 --> 00:34:21,370 addition table for these binary 2-tuples. 591 00:34:21,370 --> 00:34:26,480 You just add, component-wise, the lowest order coefficient, 592 00:34:26,480 --> 00:34:28,850 the F1 coefficient. 593 00:34:28,850 --> 00:34:37,780 So addition is just like addition in F2 squared. 594 00:34:37,780 --> 00:34:41,550 Or z2 squared, if you like. 595 00:34:41,550 --> 00:34:42,000 OK. 596 00:34:42,000 --> 00:34:44,610 That's actually an additive group. 597 00:34:44,610 --> 00:34:46,080 Check it out. 598 00:34:46,080 --> 00:34:48,219 It's not z4 by the way. 599 00:34:48,219 --> 00:34:54,120 The other abelian group, or the other group of size four, 600 00:34:54,120 --> 00:34:56,969 sometimes called the Klein four-group, but it's really 601 00:34:56,969 --> 00:35:00,120 just the addition table for the set of all binary 602 00:35:00,120 --> 00:35:00,640 [UNINTELLIGIBLE] 603 00:35:00,640 --> 00:35:02,760 two-tuples. 604 00:35:02,760 --> 00:35:04,010 OK? 605 00:35:04,010 --> 00:35:05,440 606 00:35:05,440 --> 00:35:06,690 Multiplication. 607 00:35:06,690 --> 00:35:14,320 608 00:35:14,320 --> 00:35:16,520 One very nice thing about finite fields is 609 00:35:16,520 --> 00:35:18,470 you can simply -- 610 00:35:18,470 --> 00:35:18,800 sorry. 611 00:35:18,800 --> 00:35:21,062 This was supposed to be addition, this was supposed to 612 00:35:21,062 --> 00:35:22,312 be multiplication. 613 00:35:22,312 --> 00:35:24,390 614 00:35:24,390 --> 00:35:28,750 You know can simply write out what all the rules are in a 615 00:35:28,750 --> 00:35:30,000 finite space. 616 00:35:30,000 --> 00:35:33,900 617 00:35:33,900 --> 00:35:34,360 OK. 618 00:35:34,360 --> 00:35:35,680 So what's 0 times anything? 619 00:35:35,680 --> 00:35:40,720 620 00:35:40,720 --> 00:35:41,970 What's 1 times anything? 621 00:35:41,970 --> 00:35:44,550 622 00:35:44,550 --> 00:35:45,180 Itself. 623 00:35:45,180 --> 00:35:46,750 1 is the multiplicative identity. 624 00:35:46,750 --> 00:35:50,720 625 00:35:50,720 --> 00:35:52,080 But you know. 626 00:35:52,080 --> 00:35:54,150 You could formally do this by doing polynomial 627 00:35:54,150 --> 00:35:55,360 multiplication. 628 00:35:55,360 --> 00:35:55,880 All right. 629 00:35:55,880 --> 00:35:56,850 Here's an interesting one. 630 00:35:56,850 --> 00:35:58,330 What's x times x? 631 00:35:58,330 --> 00:36:02,150 632 00:36:02,150 --> 00:36:04,060 Do x times x. 633 00:36:04,060 --> 00:36:08,280 634 00:36:08,280 --> 00:36:11,700 What is that going to be equal to? 635 00:36:11,700 --> 00:36:12,500 x plus 1. 636 00:36:12,500 --> 00:36:15,600 How did you do that? 637 00:36:15,600 --> 00:36:17,410 We did the modulo. 638 00:36:17,410 --> 00:36:20,510 First of all, we write that that's x squared. 639 00:36:20,510 --> 00:36:24,990 But then we have to do x squared modulo g of x. 640 00:36:24,990 --> 00:36:27,540 x squared plus x plus 1. 641 00:36:27,540 --> 00:36:31,970 So we have to go through a little long division process. 642 00:36:31,970 --> 00:36:34,720 We have to subtract this out from that. 643 00:36:34,720 --> 00:36:36,430 And that gives us x plus 1. 644 00:36:36,430 --> 00:36:41,380 645 00:36:41,380 --> 00:36:42,560 So that's the key rule. 646 00:36:42,560 --> 00:36:47,970 Whenever we see something of degree two or higher, we can 647 00:36:47,970 --> 00:36:51,170 always reduce it by subtracting out some multiple 648 00:36:51,170 --> 00:36:54,810 of g of x down to something of lower degree. 649 00:36:54,810 --> 00:36:55,100 Right? 650 00:36:55,100 --> 00:36:57,230 So this is what I've been talking about. 651 00:36:57,230 --> 00:37:01,100 So x times x is x plus 1. 652 00:37:01,100 --> 00:37:02,975 What's x times x plus 1? 653 00:37:02,975 --> 00:37:08,230 654 00:37:08,230 --> 00:37:09,480 Equals what? 655 00:37:09,480 --> 00:37:12,162 656 00:37:12,162 --> 00:37:12,660 Good. 657 00:37:12,660 --> 00:37:15,780 You can do that in your heads. 658 00:37:15,780 --> 00:37:18,860 And what's x plus 1 times x plus 1? 659 00:37:18,860 --> 00:37:25,160 660 00:37:25,160 --> 00:37:27,810 Remember, we're doing mod-2 arithmetic in 661 00:37:27,810 --> 00:37:29,760 our base field here. 662 00:37:29,760 --> 00:37:32,170 So this equals what? 663 00:37:32,170 --> 00:37:33,520 x squared plus 1. 664 00:37:33,520 --> 00:37:35,130 We reduce that, we get x. 665 00:37:35,130 --> 00:37:42,970 666 00:37:42,970 --> 00:37:45,560 OK. 667 00:37:45,560 --> 00:37:48,040 Let me check right now. 668 00:37:48,040 --> 00:37:51,920 Is this a field? 669 00:37:51,920 --> 00:37:54,760 These four elements with these rules for addition and 670 00:37:54,760 --> 00:37:56,260 multiplication. 671 00:37:56,260 --> 00:37:57,510 Does that form a field? 672 00:37:57,510 --> 00:38:03,370 673 00:38:03,370 --> 00:38:07,230 What do I have to check, apart from formalities like the 674 00:38:07,230 --> 00:38:10,520 distributive law? 675 00:38:10,520 --> 00:38:12,370 Which follows from the distributive law for 676 00:38:12,370 --> 00:38:14,690 polynomials. 677 00:38:14,690 --> 00:38:18,432 That's always going to hold through mod x arithmetic. 678 00:38:18,432 --> 00:38:19,860 What do I have to check? 679 00:38:19,860 --> 00:38:21,730 What are my field axioms? 680 00:38:21,730 --> 00:38:23,800 Anybody? 681 00:38:23,800 --> 00:38:26,920 Closure under multiplication. 682 00:38:26,920 --> 00:38:29,610 683 00:38:29,610 --> 00:38:33,720 That's getting towards a very crisp statement of the -- 684 00:38:33,720 --> 00:38:36,060 I'm looking for two group axioms. 685 00:38:36,060 --> 00:38:39,850 One has to do with something we have to check for addition. 686 00:38:39,850 --> 00:38:41,760 Something has to do with something we have to check for 687 00:38:41,760 --> 00:38:43,010 multiplication. 688 00:38:43,010 --> 00:38:46,190 689 00:38:46,190 --> 00:38:47,230 Inverses? 690 00:38:47,230 --> 00:38:48,480 AUDIENCE: [INAUDIBLE PHRASE]. 691 00:38:48,480 --> 00:38:52,450 692 00:38:52,450 --> 00:38:53,130 PROFESSOR: OK. 693 00:38:53,130 --> 00:38:56,840 Between the two of you I heard the two answers that I want. 694 00:38:56,840 --> 00:38:58,620 We have to check that this forms an 695 00:38:58,620 --> 00:39:01,930 abelian group under addition. 696 00:39:01,930 --> 00:39:04,310 So we have to check that the addition table is the addition 697 00:39:04,310 --> 00:39:08,170 table of an abelian group. 698 00:39:08,170 --> 00:39:10,850 And under multiplication, we have to check that the 699 00:39:10,850 --> 00:39:14,410 non-zero elements form a billion group. 700 00:39:14,410 --> 00:39:22,000 So just this part of the table has to form an abelian group, 701 00:39:22,000 --> 00:39:25,830 and both these have to have an identity, of course. 702 00:39:25,830 --> 00:39:34,480 But the identity in mod g of x arithmetic is always going to 703 00:39:34,480 --> 00:39:37,430 be 0 for addition and it's always going to be 1 for 704 00:39:37,430 --> 00:39:38,680 multiplication. 705 00:39:38,680 --> 00:39:42,930 706 00:39:42,930 --> 00:39:43,350 All right. 707 00:39:43,350 --> 00:39:44,990 So I check this. 708 00:39:44,990 --> 00:39:46,180 Is this a group table? 709 00:39:46,180 --> 00:39:49,080 Basically, I just have to check whether every row and 710 00:39:49,080 --> 00:39:55,080 column is a permutation of the elements. 711 00:39:55,080 --> 00:39:57,180 And it is. 712 00:39:57,180 --> 00:40:02,810 And 0 acts as 0 should act. 713 00:40:02,810 --> 00:40:06,600 Has the additive identity. 714 00:40:06,600 --> 00:40:08,450 All right? 715 00:40:08,450 --> 00:40:12,290 Here what I have to check is that the nonzero elements, 716 00:40:12,290 --> 00:40:21,070 these three, form an abelian group under multiplication. 717 00:40:21,070 --> 00:40:25,830 Well, there really is only one group of size three. 718 00:40:25,830 --> 00:40:29,790 It is isomorphic to Z3. 719 00:40:29,790 --> 00:40:31,710 If I replace -- 720 00:40:31,710 --> 00:40:38,360 let's remember what Z3 looks like under addition. 721 00:40:38,360 --> 00:40:45,270 This looks like 0 1 2, 0 1 2, 0 1 2, 0 1 2. 722 00:40:45,270 --> 00:40:46,270 It's mod-3. 723 00:40:46,270 --> 00:40:52,420 1 plus 1 is 2, 1 plus 2 is 3, which is 0, 1 plus 2 is 3, 724 00:40:52,420 --> 00:40:56,360 which is 0, 2 plus 2 equals 1. 725 00:40:56,360 --> 00:40:58,710 So gee whiz. 726 00:40:58,710 --> 00:41:03,930 This is isomorphic to that if I relabel 1 by 0, x by 1, and 727 00:41:03,930 --> 00:41:06,475 x plus 1 by 2. 728 00:41:06,475 --> 00:41:09,700 That's the only thing it could be. 729 00:41:09,700 --> 00:41:14,690 The only group table in which every row and column is a 730 00:41:14,690 --> 00:41:16,025 permutation of every other. 731 00:41:16,025 --> 00:41:18,620 732 00:41:18,620 --> 00:41:19,870 OK? 733 00:41:19,870 --> 00:41:21,730 734 00:41:21,730 --> 00:41:26,430 So we verified that we now have a finite 735 00:41:26,430 --> 00:41:32,540 field with four elements. 736 00:41:32,540 --> 00:41:36,470 737 00:41:36,470 --> 00:41:37,985 Prime power number of elements. 738 00:41:37,985 --> 00:41:41,020 739 00:41:41,020 --> 00:41:43,480 Right? 740 00:41:43,480 --> 00:41:48,310 The elements of my field are these four remainders, or you 741 00:41:48,310 --> 00:41:50,340 can think of them as representatives for their 742 00:41:50,340 --> 00:41:53,020 cosets, modulo g of x. 743 00:41:53,020 --> 00:42:02,410 The addition rule is addition modulo g of x, and the 744 00:42:02,410 --> 00:42:07,720 multiplication rule is multiplication modulo g of x. 745 00:42:07,720 --> 00:42:10,920 And it satisfies the field axioms, therefore, it's a 746 00:42:10,920 --> 00:42:12,333 finite field. 747 00:42:12,333 --> 00:42:13,750 All right? 748 00:42:13,750 --> 00:42:16,470 I can add, subtract. 749 00:42:16,470 --> 00:42:19,360 Addition and subtraction basically looks like addition 750 00:42:19,360 --> 00:42:23,170 and subtraction of binary two-tuples, just 751 00:42:23,170 --> 00:42:24,680 component-wise. 752 00:42:24,680 --> 00:42:27,320 Multiplication is a little bit more mysterious 753 00:42:27,320 --> 00:42:29,045 right now, but it works. 754 00:42:29,045 --> 00:42:33,370 755 00:42:33,370 --> 00:42:35,203 Let me tell you where we're going to go on multiplication. 756 00:42:35,203 --> 00:42:40,690 757 00:42:40,690 --> 00:42:47,010 In this case, I can write x plus 1 in a different way. 758 00:42:47,010 --> 00:42:52,530 I note that x plus 1 is equal to x squared. 759 00:42:52,530 --> 00:42:54,240 All right? 760 00:42:54,240 --> 00:43:03,840 So let me write a little log table over here for 761 00:43:03,840 --> 00:43:05,135 multiplication purposes. 762 00:43:05,135 --> 00:43:08,260 763 00:43:08,260 --> 00:43:12,320 I'm going to write x -- 764 00:43:12,320 --> 00:43:13,570 I'm going to call that alpha. 765 00:43:13,570 --> 00:43:17,620 766 00:43:17,620 --> 00:43:20,590 And x plus 1 is equal to x squared, 767 00:43:20,590 --> 00:43:21,925 or it's alpha squared. 768 00:43:21,925 --> 00:43:25,700 769 00:43:25,700 --> 00:43:26,950 What's alpha cubed? 770 00:43:26,950 --> 00:43:33,210 771 00:43:33,210 --> 00:43:38,636 Alpha cubed is x times this again. 772 00:43:38,636 --> 00:43:43,050 Let me look in the table. x times x plus 1 is equal to 1. 773 00:43:43,050 --> 00:43:45,940 So 1 equals alpha cubed. 774 00:43:45,940 --> 00:43:49,590 Or I could write that as alpha to 0. 775 00:43:49,590 --> 00:43:53,730 If I multiply by x again, I just cycle. 776 00:43:53,730 --> 00:43:55,990 So I'm going to get a cyclic group here. 777 00:43:55,990 --> 00:43:58,910 778 00:43:58,910 --> 00:43:59,720 And now I'm going to write the 779 00:43:59,720 --> 00:44:01,405 multiplication table as follows. 780 00:44:01,405 --> 00:44:04,630 781 00:44:04,630 --> 00:44:07,310 I'm going to write the elements of the group as 1, 782 00:44:07,310 --> 00:44:12,915 alpha, alpha squared, 0, 1, alpha, alpha squared. 783 00:44:12,915 --> 00:44:17,910 784 00:44:17,910 --> 00:44:20,060 Again, 0 times anything is 0. 785 00:44:20,060 --> 00:44:23,130 We never have to worry about that. 786 00:44:23,130 --> 00:44:25,040 1, alpha, alpha squared. 787 00:44:25,040 --> 00:44:29,330 788 00:44:29,330 --> 00:44:31,540 Alpha times alpha is alpha squared. 789 00:44:31,540 --> 00:44:34,610 Alpha times alpha squared is alpha cubed. 790 00:44:34,610 --> 00:44:37,520 But that's equal to 1. 791 00:44:37,520 --> 00:44:38,860 Same here. 792 00:44:38,860 --> 00:44:40,680 Alpha squared times alpha squared -- 793 00:44:40,680 --> 00:44:43,750 what's that? 794 00:44:43,750 --> 00:44:47,360 Alpha to the fourth, but what does alpha fourth equal to if 795 00:44:47,360 --> 00:44:49,280 alpha cubed is equal to 1? 796 00:44:49,280 --> 00:44:51,930 797 00:44:51,930 --> 00:44:54,830 This has to be equal to alpha. 798 00:44:54,830 --> 00:44:59,560 Point is, because of this relationship here, I can 799 00:44:59,560 --> 00:45:03,420 always reduce the exponents modulo 3. 800 00:45:03,420 --> 00:45:08,270 I've basically got a little multiplicative cyclic group of 801 00:45:08,270 --> 00:45:12,830 order three that's, of course, isomorphic to the 802 00:45:12,830 --> 00:45:14,230 additive group, Z3. 803 00:45:14,230 --> 00:45:17,770 804 00:45:17,770 --> 00:45:22,240 So there are two ways I can do multiplication. 805 00:45:22,240 --> 00:45:25,560 One is, I can do it by this mod g of x way. 806 00:45:25,560 --> 00:45:32,435 I can represent things by these which basically stand 807 00:45:32,435 --> 00:45:37,010 for polynomials of degree one or less. 808 00:45:37,010 --> 00:45:40,540 And I can multiply two of these by simply going through 809 00:45:40,540 --> 00:45:43,040 standard polynomial multiplication over the 810 00:45:43,040 --> 00:45:44,850 appropriate field. 811 00:45:44,850 --> 00:45:47,870 And then I'll likely get some powers of x squared or higher, 812 00:45:47,870 --> 00:45:51,850 and I reduce those to modulo x squared plus x plus 1. 813 00:45:51,850 --> 00:45:53,820 That's legitimate and that gives me this statement. 814 00:45:53,820 --> 00:45:56,460 815 00:45:56,460 --> 00:45:58,820 Well, the other thing I can do is for multiplication, I can 816 00:45:58,820 --> 00:46:00,990 have a different representation. 817 00:46:00,990 --> 00:46:03,980 This is basically just a log table. 818 00:46:03,980 --> 00:46:06,280 OK? 819 00:46:06,280 --> 00:46:11,740 For each, I would have in my little computer a separate 820 00:46:11,740 --> 00:46:16,790 table where I'd write that this corresponds to 0, 0 1 821 00:46:16,790 --> 00:46:21,230 corresponds to 1, 1 0 corresponds to alpha, and 1 1 822 00:46:21,230 --> 00:46:24,430 corresponds to alpha squared. 823 00:46:24,430 --> 00:46:27,170 Or of course, I would just represent these by their 824 00:46:27,170 --> 00:46:31,810 exponents that have some special value for 0. 825 00:46:31,810 --> 00:46:34,940 And then all I have to do is add exponents modulo 3 for 826 00:46:34,940 --> 00:46:37,360 multiplication. 827 00:46:37,360 --> 00:46:45,700 So log of x is 1, log of x plus 1 is 2, log of 1 is 0, 828 00:46:45,700 --> 00:46:54,220 and then I just use this for my multiplication operation, 829 00:46:54,220 --> 00:46:58,990 or equivalently this cyclic multiplicative group. 830 00:46:58,990 --> 00:47:02,590 Then I go through some inverse log operation to get back to 831 00:47:02,590 --> 00:47:05,926 the other representation, if I wanted to. 832 00:47:05,926 --> 00:47:08,760 And in fact, in finite field arithmetic, this is what's 833 00:47:08,760 --> 00:47:09,550 typically done. 834 00:47:09,550 --> 00:47:13,140 There's just a little table lookup such that you can go 835 00:47:13,140 --> 00:47:16,450 back and forth between this representation, which we use 836 00:47:16,450 --> 00:47:19,380 for addition, and this representation, which we use 837 00:47:19,380 --> 00:47:20,630 for multiplication. 838 00:47:20,630 --> 00:47:24,188 839 00:47:24,188 --> 00:47:25,170 Yeah? 840 00:47:25,170 --> 00:47:26,420 AUDIENCE: [INAUDIBLE PHRASE]. 841 00:47:26,420 --> 00:47:30,140 842 00:47:30,140 --> 00:47:32,410 PROFESSOR: You have to represent it as being special 843 00:47:32,410 --> 00:47:34,130 in some way. 844 00:47:34,130 --> 00:47:43,010 So if, in fact, literally, I made log x equal to 1, log x 845 00:47:43,010 --> 00:47:50,060 plus 1 equal to 2, log 1 equal to 0 -- 846 00:47:50,060 --> 00:47:52,860 one thing I suggest in the notes, you can make log 0 847 00:47:52,860 --> 00:47:55,190 equal to minus infinity. 848 00:47:55,190 --> 00:47:57,620 That will always work. 849 00:47:57,620 --> 00:48:03,220 If you ever multiply by 0, you'll be 850 00:48:03,220 --> 00:48:04,450 adding minus infinity. 851 00:48:04,450 --> 00:48:06,750 The result will be minus infinity, so the 852 00:48:06,750 --> 00:48:08,020 inverse log is 0. 853 00:48:08,020 --> 00:48:10,770 So that's one way you can do it. 854 00:48:10,770 --> 00:48:13,540 Or you could do what you do in ordinary real and complex 855 00:48:13,540 --> 00:48:14,160 arithmetic. 856 00:48:14,160 --> 00:48:18,340 You could just, say, have some special routine for 857 00:48:18,340 --> 00:48:21,040 multiplication by 0 is always 0. 858 00:48:21,040 --> 00:48:24,300 Division by 0 is illegal. 859 00:48:24,300 --> 00:48:25,550 Put out some error message. 860 00:48:25,550 --> 00:48:29,400 861 00:48:29,400 --> 00:48:29,770 All right? 862 00:48:29,770 --> 00:48:32,820 So that's how you actually build a little finite field 863 00:48:32,820 --> 00:48:34,500 computer for this finite field. 864 00:48:34,500 --> 00:48:38,270 865 00:48:38,270 --> 00:48:39,520 OK. 866 00:48:39,520 --> 00:48:42,050 867 00:48:42,050 --> 00:48:45,005 Now, I chose this advisedly. 868 00:48:45,005 --> 00:48:51,700 869 00:48:51,700 --> 00:48:57,240 Suppose I have chosen g of x equal to x squared plus 1. 870 00:48:57,240 --> 00:49:00,980 871 00:49:00,980 --> 00:49:01,640 OK? 872 00:49:01,640 --> 00:49:06,230 I can do mod g of x arithmetic for x squared plus 1. 873 00:49:06,230 --> 00:49:09,070 Again, my four field elements are going to be the four 874 00:49:09,070 --> 00:49:13,370 binary polynomials of degree 1 or less. 875 00:49:13,370 --> 00:49:15,750 The addition table is going to be exactly the same. 876 00:49:15,750 --> 00:49:16,750 So let's just write the 877 00:49:16,750 --> 00:49:18,440 multiplication table over here. 878 00:49:18,440 --> 00:49:23,150 879 00:49:23,150 --> 00:49:30,680 0, 1, x, x plus 1, 0, 1, x, x plus 1. 880 00:49:30,680 --> 00:49:35,930 0 times anything is 0 in ordinary polynomial 881 00:49:35,930 --> 00:49:39,360 multiplication, and therefore also in mod g of x 882 00:49:39,360 --> 00:49:40,450 for any g of x. 883 00:49:40,450 --> 00:49:43,020 1 times anything is itself. 884 00:49:43,020 --> 00:49:45,600 No problem there. 885 00:49:45,600 --> 00:49:49,190 x, x plus 1. 886 00:49:49,190 --> 00:49:54,090 So we again have to give a little bit care to x squared. 887 00:49:54,090 --> 00:49:57,260 What's that going to be equal to? 888 00:49:57,260 --> 00:49:58,910 1. 889 00:49:58,910 --> 00:50:07,870 And x times x plus 1 is equal to what? 890 00:50:07,870 --> 00:50:14,200 891 00:50:14,200 --> 00:50:16,360 x squared plus x is equal to what? 892 00:50:16,360 --> 00:50:23,570 893 00:50:23,570 --> 00:50:25,940 Looks like there's a problem. 894 00:50:25,940 --> 00:50:30,050 x plus 1 times x squared x plus 1 is equal to x squared 895 00:50:30,050 --> 00:50:33,080 plus 1, what's that equal? 896 00:50:33,080 --> 00:50:34,320 0. 897 00:50:34,320 --> 00:50:35,580 Yuck. 898 00:50:35,580 --> 00:50:36,830 Didn't work. 899 00:50:36,830 --> 00:50:41,540 900 00:50:41,540 --> 00:50:43,070 What's the essential problem here? 901 00:50:43,070 --> 00:50:46,998 902 00:50:46,998 --> 00:50:47,490 Yeah. 903 00:50:47,490 --> 00:50:51,650 This clearly is not a group. 904 00:50:51,650 --> 00:50:54,070 It's not even closed under multiplication. 905 00:50:54,070 --> 00:50:58,790 Because x plus 1 times x plus 1 is equal to 0. 906 00:50:58,790 --> 00:51:01,640 The essential problem is that there are two polynomials of 907 00:51:01,640 --> 00:51:08,590 degree less than two whose product is x squared plus 1. 908 00:51:08,590 --> 00:51:11,880 In other words, this is factorizable. 909 00:51:11,880 --> 00:51:17,860 910 00:51:17,860 --> 00:51:18,340 OK? 911 00:51:18,340 --> 00:51:20,050 In F2 of x. 912 00:51:20,050 --> 00:51:22,730 913 00:51:22,730 --> 00:51:23,330 All right? 914 00:51:23,330 --> 00:51:31,200 So whereas x squared plus x plus 1. 915 00:51:31,200 --> 00:51:34,250 Does that have any factors of degree 1 or less? 916 00:51:34,250 --> 00:51:36,750 Any nontrivial factors of degree 1 or less? 917 00:51:36,750 --> 00:51:39,610 918 00:51:39,610 --> 00:51:43,050 Well, basically we proved that it didn't, when we wrote this 919 00:51:43,050 --> 00:51:45,870 multiplication table. 920 00:51:45,870 --> 00:51:52,620 We tried all products of degree 1 or less polynomials 921 00:51:52,620 --> 00:51:56,160 where they're both non-zero, and we never got 0. 922 00:51:56,160 --> 00:52:00,030 923 00:52:00,030 --> 00:52:08,520 So this will work if and only if g of x is irreducible, has 924 00:52:08,520 --> 00:52:11,980 no nontrivial factors, is a prime polynomial. 925 00:52:11,980 --> 00:52:14,600 These are all equivalent in F2 of x. 926 00:52:14,600 --> 00:52:17,300 927 00:52:17,300 --> 00:52:22,730 There's this distinction in other fields that irreducible 928 00:52:22,730 --> 00:52:25,060 just means has no nontrivial factors. 929 00:52:25,060 --> 00:52:27,370 Prime means there's a monic polynomial with 930 00:52:27,370 --> 00:52:29,460 no non-trivial factors. 931 00:52:29,460 --> 00:52:36,800 So that's what I said back here. 932 00:52:36,800 --> 00:52:40,850 That the way we're ultimately going to have to construct 933 00:52:40,850 --> 00:52:45,510 finite fields is take the polynomials in Fp, Fp of x -- 934 00:52:45,510 --> 00:52:47,530 we've been looking at F2 of x -- 935 00:52:47,530 --> 00:52:50,150 modulo a prime polynomial g of x. 936 00:52:50,150 --> 00:52:57,450 937 00:52:57,450 --> 00:53:03,560 So what we're going to need to find is prime polynomials. 938 00:53:03,560 --> 00:53:04,300 Let's see. 939 00:53:04,300 --> 00:53:11,690 Can I already prove that this is going to work for any prime 940 00:53:11,690 --> 00:53:12,940 polynomial? 941 00:53:12,940 --> 00:53:19,400 942 00:53:19,400 --> 00:53:26,160 So I'm going to force the g of x to be equal to a prime 943 00:53:26,160 --> 00:53:33,546 polynomial in Fp of x of degree m. 944 00:53:33,546 --> 00:53:44,360 All right 945 00:53:44,360 --> 00:53:48,135 For example, x squared plus x plus 1 is a prime polynomial. 946 00:53:48,135 --> 00:53:54,360 947 00:53:54,360 --> 00:54:15,250 And I'm going to ask if the remainders mod g of x form a 948 00:54:15,250 --> 00:54:21,980 field under mod g of x arithmetic. 949 00:54:21,980 --> 00:54:33,370 950 00:54:33,370 --> 00:54:34,620 OK. 951 00:54:34,620 --> 00:54:36,290 952 00:54:36,290 --> 00:54:39,660 Let's flow this out a little bit. 953 00:54:39,660 --> 00:54:46,740 Again, what are the remainders going to be of any polynomial 954 00:54:46,740 --> 00:54:47,990 of degree m? 955 00:54:47,990 --> 00:54:54,450 956 00:54:54,450 --> 00:55:00,750 So this is basically going to be the polynomials of degree 957 00:55:00,750 --> 00:55:06,915 less than m in Fp of x. 958 00:55:06,915 --> 00:55:11,000 959 00:55:11,000 --> 00:55:12,620 How many of them are there, by the way? 960 00:55:12,620 --> 00:55:19,620 961 00:55:19,620 --> 00:55:20,390 p to the m. 962 00:55:20,390 --> 00:55:30,390 So the size of this is p to the m. 963 00:55:30,390 --> 00:55:34,200 And one of the representations for these polynomials is just 964 00:55:34,200 --> 00:55:40,350 to write out F0, F1, up to m minus 1. 965 00:55:40,350 --> 00:55:49,350 So this just basically looks like the polynomial m-tuples. 966 00:55:49,350 --> 00:55:59,420 Set of F0, F1 up to F minus 1, for each of these an element 967 00:55:59,420 --> 00:56:00,670 of the field. 968 00:56:00,670 --> 00:56:05,230 969 00:56:05,230 --> 00:56:05,830 OK? 970 00:56:05,830 --> 00:56:09,030 I can make a one-to-one correspondence between the 971 00:56:09,030 --> 00:56:12,930 polynomials of degree less than m and the set of all 972 00:56:12,930 --> 00:56:16,130 coefficient m-tuples over Fp. 973 00:56:16,130 --> 00:56:19,260 These are just m-tuples over Fp. 974 00:56:19,260 --> 00:56:20,660 So there are p to the m of them. 975 00:56:20,660 --> 00:56:23,430 976 00:56:23,430 --> 00:56:29,580 And so it's a finite set, size p to the m. 977 00:56:29,580 --> 00:56:33,018 Does it form a field under mod g of x arithmetic? 978 00:56:33,018 --> 00:56:34,268 AUDIENCE: [INAUDIBLE PHRASE]. 979 00:56:34,268 --> 00:56:42,490 980 00:56:42,490 --> 00:56:42,920 PROFESSOR: Correct. 981 00:56:42,920 --> 00:56:44,320 And that's a homework problem. 982 00:56:44,320 --> 00:56:48,450 983 00:56:48,450 --> 00:56:51,970 So I'm not going to do it in class, but I will sketch here 984 00:56:51,970 --> 00:56:53,400 how it's going to be done. 985 00:56:53,400 --> 00:56:56,360 But I'm glad that you instantly see that. 986 00:56:56,360 --> 00:56:59,030 Because again, we just model everything we do on what we 987 00:56:59,030 --> 00:57:01,160 did for integers. 988 00:57:01,160 --> 00:57:04,650 If you remember how we proved it for integers. 989 00:57:04,650 --> 00:57:08,820 First of all, we really need to check two things. 990 00:57:08,820 --> 00:57:10,070 Addition. 991 00:57:10,070 --> 00:57:12,680 992 00:57:12,680 --> 00:57:15,620 Just as we did for this specific example up here, we 993 00:57:15,620 --> 00:57:20,550 first have to check that the addition table is that of an 994 00:57:20,550 --> 00:57:25,072 abelian group, that these supposed field elements form 995 00:57:25,072 --> 00:57:29,440 an abelian group under addition. 996 00:57:29,440 --> 00:57:32,810 And we've already observed several times that addition is 997 00:57:32,810 --> 00:57:38,460 just basically component-wise addition of these m-tuples. 998 00:57:38,460 --> 00:57:40,210 So it's just like vector addition. 999 00:57:40,210 --> 00:57:43,270 1000 00:57:43,270 --> 00:57:47,390 And vector addition, of course, 1001 00:57:47,390 --> 00:57:48,560 has the group property. 1002 00:57:48,560 --> 00:57:54,230 So addition is basically just like vector addition. 1003 00:57:54,230 --> 00:58:00,370 Or I could write, perhaps more precisely, Zp over m. 1004 00:58:00,370 --> 00:58:03,540 Distinction without a difference, really. 1005 00:58:03,540 --> 00:58:11,145 So it's just component-wise addition of the coefficients. 1006 00:58:11,145 --> 00:58:13,760 1007 00:58:13,760 --> 00:58:16,510 That's how we do polynomial addition. 1008 00:58:16,510 --> 00:58:20,780 And it will give us a remainder that has a degree of 1009 00:58:20,780 --> 00:58:23,850 less than m, so we don't have to have ever reduce it. 1010 00:58:23,850 --> 00:58:28,970 Modulo g of x, we just simply add component-wise. 1011 00:58:28,970 --> 00:58:29,420 OK. 1012 00:58:29,420 --> 00:58:31,180 So that's easy to verify. 1013 00:58:31,180 --> 00:58:34,180 The addition table is always going to be OK. 1014 00:58:34,180 --> 00:58:36,150 So what do we have to prove now? 1015 00:58:36,150 --> 00:58:37,400 We have to -- 1016 00:58:37,400 --> 00:58:40,029 1017 00:58:40,029 --> 00:58:41,250 what am I going to call these? 1018 00:58:41,250 --> 00:58:42,680 Rg of x. 1019 00:58:42,680 --> 00:58:45,420 The remainders mod g of x. 1020 00:58:45,420 --> 00:58:55,070 For multiplication, we have to prove that Rg of x star -- 1021 00:58:55,070 --> 00:59:08,350 the non-zero polynomials form an abelian group, which, as I 1022 00:59:08,350 --> 00:59:09,640 say, it's a homework problem. 1023 00:59:09,640 --> 00:59:11,090 Let me sketch the proof. 1024 00:59:11,090 --> 00:59:13,560 It's precisely analogous to the proof that 1025 00:59:13,560 --> 00:59:18,060 we made for Zp star. 1026 00:59:18,060 --> 00:59:21,980 We basically have to check closure. 1027 00:59:21,980 --> 00:59:27,070 If we multiply two non-zero polynomials, do we get another 1028 00:59:27,070 --> 00:59:28,320 non-zero polynomial? 1029 00:59:28,320 --> 00:59:32,820 1030 00:59:32,820 --> 00:59:37,130 Asking another way, is it possible to multiply two 1031 00:59:37,130 --> 00:59:44,410 polynomials of degree less than m and get a result which 1032 00:59:44,410 --> 00:59:50,910 is a multiple of g of x, which is either equal to g of x or a 1033 00:59:50,910 --> 00:59:53,870 multiple of g of x? 1034 00:59:53,870 --> 00:59:59,050 And it's, I think, easy to convince yourself if this has 1035 00:59:59,050 --> 01:00:01,460 no factors -- 1036 01:00:01,460 --> 01:00:04,910 its only factors are itself and 1, no 1037 01:00:04,910 --> 01:00:07,860 non-trivial factors -- 1038 01:00:07,860 --> 01:00:14,510 then you can't multiply two lesser degree polynomials and 1039 01:00:14,510 --> 01:00:19,090 get either g of x, of course, or any multiple of g of x. 1040 01:00:19,090 --> 01:00:21,800 And it's an exercise for the student to 1041 01:00:21,800 --> 01:00:24,060 write that proof out. 1042 01:00:24,060 --> 01:00:24,440 OK? 1043 01:00:24,440 --> 01:00:27,400 But it's just exactly analogous to the proof that 1044 01:00:27,400 --> 01:00:32,920 you can't multiply two integers less than a prime p 1045 01:00:32,920 --> 01:00:35,790 and get a multiple of p. 1046 01:00:35,790 --> 01:00:40,472 So use that as a model, if you want to, in your proof. 1047 01:00:40,472 --> 01:00:44,070 That of course depends on this being prime. 1048 01:00:44,070 --> 01:00:49,210 If this is factorizable, non-prime, then of course 1049 01:00:49,210 --> 01:00:52,020 there are going to be two nontrivial factors, two 1050 01:00:52,020 --> 01:00:58,380 remainders of degree less than m, whose product is equal to g 1051 01:00:58,380 --> 01:01:01,060 of x itself, if it's factorizable. 1052 01:01:01,060 --> 01:01:04,040 So you can't possibly get closure. 1053 01:01:04,040 --> 01:01:07,850 So this is why non-prime polynomials don't work, just 1054 01:01:07,850 --> 01:01:14,310 like non-prime integers don't work when we constructed Fp. 1055 01:01:14,310 --> 01:01:17,580 Exactly analogous reasons. 1056 01:01:17,580 --> 01:01:19,940 All right. 1057 01:01:19,940 --> 01:01:25,760 Second question is, when we go through this multiplication, 1058 01:01:25,760 --> 01:01:34,640 suppose we take r of x times -- 1059 01:01:34,640 --> 01:01:36,430 let's construct a multiplication table. 1060 01:01:36,430 --> 01:01:37,720 Let's take a particular row. 1061 01:01:37,720 --> 01:01:42,340 Let's take r of x times all the non-zero things. 1062 01:01:42,340 --> 01:01:45,630 Can we possibly get any repeats? 1063 01:01:45,630 --> 01:01:51,950 Can r of x times s of x equal r of x times t of x? 1064 01:01:51,950 --> 01:01:54,280 And again, it's easy to convince yourself that that's 1065 01:01:54,280 --> 01:01:55,020 not possible. 1066 01:01:55,020 --> 01:01:59,010 If that were possible, then r of x times s of x minus t of x 1067 01:01:59,010 --> 01:02:01,210 would be equal to 0. 1068 01:02:01,210 --> 01:02:04,630 And so we're back to where we were before -- 1069 01:02:04,630 --> 01:02:05,740 mod g of x. 1070 01:02:05,740 --> 01:02:08,170 And this is impossible. 1071 01:02:08,170 --> 01:02:10,260 These are both degrees less than m. 1072 01:02:10,260 --> 01:02:13,210 We can't multiply two things of lower degree together to 1073 01:02:13,210 --> 01:02:14,965 get a multiple of g of x. 1074 01:02:14,965 --> 01:02:17,060 So it can't equal 0. 1075 01:02:17,060 --> 01:02:19,880 That means there can't be any repeats. 1076 01:02:19,880 --> 01:02:22,390 That means that each row is a permutation 1077 01:02:22,390 --> 01:02:24,050 of every other row. 1078 01:02:24,050 --> 01:02:25,180 Similarly for columns. 1079 01:02:25,180 --> 01:02:27,500 If you want to do that, all you have to 1080 01:02:27,500 --> 01:02:29,780 actually prove is one. 1081 01:02:29,780 --> 01:02:39,070 So every row or column is a permutations of every other 1082 01:02:39,070 --> 01:02:44,100 one, if we just look at the non-zero polynomials, star. 1083 01:02:44,100 --> 01:02:54,240 And therefore, this forms an abelian group whose identity 1084 01:02:54,240 --> 01:02:55,490 is always one. 1085 01:02:55,490 --> 01:02:58,520 1086 01:02:58,520 --> 01:03:00,880 Just as we proved up here. 1087 01:03:00,880 --> 01:03:06,522 So this depends on irreducibility. 1088 01:03:06,522 --> 01:03:17,605 Depends on no nontrivial factors of g of x. 1089 01:03:17,605 --> 01:03:24,990 1090 01:03:24,990 --> 01:03:25,380 OK. 1091 01:03:25,380 --> 01:03:26,640 And that's all we have to check. 1092 01:03:26,640 --> 01:03:29,730 1093 01:03:29,730 --> 01:03:35,350 So I claim that by this process, I can, given a prime 1094 01:03:35,350 --> 01:03:39,200 polynomial in Fp of x of degree m, I can construct a 1095 01:03:39,200 --> 01:03:46,235 finite field with p to the m elements, that the addition 1096 01:03:46,235 --> 01:03:49,360 and multiplication rules can be taken as mod g of x 1097 01:03:49,360 --> 01:03:53,700 arithmetic, and they will satisfy the field axioms. 1098 01:03:53,700 --> 01:03:58,550 So you can now construct a finite field for any prime 1099 01:03:58,550 --> 01:04:03,160 power p to the m, right? 1100 01:04:03,160 --> 01:04:07,250 There's actually still a hole in this. 1101 01:04:07,250 --> 01:04:08,500 AUDIENCE: [INAUDIBLE PHRASE]. 1102 01:04:08,500 --> 01:04:13,040 1103 01:04:13,040 --> 01:04:14,680 PROFESSOR: Define prime polynomial? 1104 01:04:14,680 --> 01:04:16,315 The term, or -- 1105 01:04:16,315 --> 01:04:18,800 AUDIENCE: Define the [UNINTELLIGIBLE] of degree m. 1106 01:04:18,800 --> 01:04:21,280 PROFESSOR: Correct. 1107 01:04:21,280 --> 01:04:24,225 Is there going to be a prime polynomial of every degree? 1108 01:04:24,225 --> 01:04:28,990 1109 01:04:28,990 --> 01:04:30,240 I don't know. 1110 01:04:30,240 --> 01:04:33,410 1111 01:04:33,410 --> 01:04:37,230 Suppose you want to define an irreducible polynomial over, 1112 01:04:37,230 --> 01:04:44,390 say, F2 of x or F3 of x of degree 4. 1113 01:04:44,390 --> 01:04:45,640 Could you do that? 1114 01:04:45,640 --> 01:04:49,460 1115 01:04:49,460 --> 01:04:50,710 AUDIENCE: [INAUDIBLE PHRASE]. 1116 01:04:50,710 --> 01:05:09,520 1117 01:05:09,520 --> 01:05:10,180 PROFESSOR: Beautiful. 1118 01:05:10,180 --> 01:05:11,920 I mean, that's an excellent suggestion. 1119 01:05:11,920 --> 01:05:25,110 So the question is, does there exist a prime polynomial in Fp 1120 01:05:25,110 --> 01:05:28,390 of x of every degree? 1121 01:05:28,390 --> 01:05:33,680 1122 01:05:33,680 --> 01:05:34,945 Or of a given degree? 1123 01:05:34,945 --> 01:05:42,330 1124 01:05:42,330 --> 01:05:46,140 And there are various ways of attacking this question. 1125 01:05:46,140 --> 01:05:49,240 First of all, I'll tell you the answer is yes. 1126 01:05:49,240 --> 01:05:52,830 1127 01:05:52,830 --> 01:05:57,870 For every p and every m, there does exist a prime polynomial. 1128 01:05:57,870 --> 01:05:59,790 Which is fortunate. 1129 01:05:59,790 --> 01:06:04,530 So from that, we conclude there is a finite field with p 1130 01:06:04,530 --> 01:06:07,500 to the m elements for every prime p and every m greater 1131 01:06:07,500 --> 01:06:08,750 than or equal to 1. 1132 01:06:08,750 --> 01:06:11,680 1133 01:06:11,680 --> 01:06:17,410 Now, how might we prove that? 1134 01:06:17,410 --> 01:06:21,840 One is, look it up on Google. 1135 01:06:21,840 --> 01:06:26,920 1136 01:06:26,920 --> 01:06:31,960 You can certainly formulate a question that will lead you to 1137 01:06:31,960 --> 01:06:35,910 a webpage that will have a listing of all the prime 1138 01:06:35,910 --> 01:06:39,800 polynomials of all degrees over any field that you're 1139 01:06:39,800 --> 01:06:42,060 interested in. 1140 01:06:42,060 --> 01:06:45,830 So perhaps that will suffice for you. 1141 01:06:45,830 --> 01:06:47,441 Two. 1142 01:06:47,441 --> 01:06:50,280 What I'm going to talk about is the sieve method. 1143 01:06:50,280 --> 01:06:56,460 1144 01:06:56,460 --> 01:06:58,120 Three. 1145 01:06:58,120 --> 01:07:12,520 You could do a bound on the number of polynomials of each 1146 01:07:12,520 --> 01:07:19,540 degree in d, and show that it's greater than 1147 01:07:19,540 --> 01:07:22,240 or equal to 1, always. 1148 01:07:22,240 --> 01:07:26,340 And this is done in the notes. 1149 01:07:26,340 --> 01:07:29,800 Section 7.9 I think. 1150 01:07:29,800 --> 01:07:34,550 Or four, you can do what Mr. Agarwal has suggested. 1151 01:07:34,550 --> 01:07:43,250 You can actually do the closed form combinatoric 1152 01:07:43,250 --> 01:07:52,310 formula, which -- 1153 01:07:52,310 --> 01:07:54,310 I haven't done any number theory here. 1154 01:07:54,310 --> 01:07:56,230 There's a little bit of elementary number 1155 01:07:56,230 --> 01:07:58,150 theory in the notes. 1156 01:07:58,150 --> 01:08:02,050 Euler numbers, this sort of thing. 1157 01:08:02,050 --> 01:08:12,330 We get formulas for the number of integers degree d that -- 1158 01:08:12,330 --> 01:08:15,920 well, number of integers that have multiplicative orders d 1159 01:08:15,920 --> 01:08:17,700 mod n, and so forth. 1160 01:08:17,700 --> 01:08:23,520 It's a lovely combinatoric field. 1161 01:08:23,520 --> 01:08:26,960 There is a lovely closed form for this that you get from the 1162 01:08:26,960 --> 01:08:30,140 Mobius inversion formula. 1163 01:08:30,140 --> 01:08:33,439 And it can be found in combinatoric books. 1164 01:08:33,439 --> 01:08:40,440 I know it's in Berlekamp's Algebraic Coding Theory book. 1165 01:08:40,440 --> 01:08:42,330 And it's extremely pretty. 1166 01:08:42,330 --> 01:08:45,750 And then of course, given the formula, you have to prove to 1167 01:08:45,750 --> 01:08:48,620 all of the -- 1168 01:08:48,620 --> 01:08:51,120 again, n of d is greater than or equal to 1. 1169 01:08:51,120 --> 01:08:54,880 But there is a closed form expression for it that you get 1170 01:08:54,880 --> 01:08:55,880 out of combinatorics. 1171 01:08:55,880 --> 01:08:58,420 We're not going to do that here. 1172 01:08:58,420 --> 01:09:00,180 I'll be satisfied -- 1173 01:09:00,180 --> 01:09:03,330 well, this is the real engineering solution here. 1174 01:09:03,330 --> 01:09:05,484 This is the mathematical engineering solution. 1175 01:09:05,484 --> 01:09:07,990 1176 01:09:07,990 --> 01:09:13,800 And what do I mean by the sieve method? 1177 01:09:13,800 --> 01:09:17,850 Again, take the analogy with the integers. 1178 01:09:17,850 --> 01:09:21,080 One of the first mathematical accomplishments was 1179 01:09:21,080 --> 01:09:25,630 Eratosthenes' sieve for finding prime numbers. 1180 01:09:25,630 --> 01:09:27,660 How does it work? 1181 01:09:27,660 --> 01:09:30,430 You start to write down all the -- 1182 01:09:30,430 --> 01:09:30,920 well. 1183 01:09:30,920 --> 01:09:34,939 Imagine first writing down all the integers. 1184 01:09:34,939 --> 01:09:35,720 All right? 1185 01:09:35,720 --> 01:09:36,630 Cross off 1. 1186 01:09:36,630 --> 01:09:39,240 Start with 2. 1187 01:09:39,240 --> 01:09:40,080 All right. 1188 01:09:40,080 --> 01:09:42,700 So the first prime is 2. 1189 01:09:42,700 --> 01:09:44,890 Then you cross off all multiples of 2. 1190 01:09:44,890 --> 01:09:47,710 4,6,8, so forth. 1191 01:09:47,710 --> 01:09:49,979 OK? 1192 01:09:49,979 --> 01:09:52,460 So what's the next number that you haven't crossed off? 1193 01:09:52,460 --> 01:09:54,370 It's 3, so that's the next prime. 1194 01:09:54,370 --> 01:09:57,370 You cross off all the multiples of 3. 1195 01:09:57,370 --> 01:10:00,480 3,6,9. 1196 01:10:00,480 --> 01:10:01,790 So forth. 1197 01:10:01,790 --> 01:10:03,900 15. 1198 01:10:03,900 --> 01:10:07,970 And thereby you continue. 1199 01:10:07,970 --> 01:10:15,590 So the steps are, find the next integer on the list. 1200 01:10:15,590 --> 01:10:17,460 That's going to be a prime, because it won't have been 1201 01:10:17,460 --> 01:10:19,370 crossed off by any previous steps. 1202 01:10:19,370 --> 01:10:23,970 It's not a multiple of any integer of lower degree. 1203 01:10:23,970 --> 01:10:28,240 Then cross off all of its multiples, up to however long 1204 01:10:28,240 --> 01:10:30,870 your scribe has written this on the tablet. 1205 01:10:30,870 --> 01:10:35,770 And this way, you can find the primes up to 1206 01:10:35,770 --> 01:10:37,960 any number you want. 1207 01:10:37,960 --> 01:10:41,580 Gets kind of tedious after a while, but you can certainly 1208 01:10:41,580 --> 01:10:45,210 find all the primes up to 100 in a few 1209 01:10:45,210 --> 01:10:48,092 minutes doing this, right? 1210 01:10:48,092 --> 01:10:52,250 Well, it's the same for integers, and it's the same 1211 01:10:52,250 --> 01:10:54,260 for polynomials. 1212 01:10:54,260 --> 01:11:02,256 So let's, for instance, do a polynomial sieve. 1213 01:11:02,256 --> 01:11:05,335 1214 01:11:05,335 --> 01:11:10,750 Of course, what we're most interested in is the 1215 01:11:10,750 --> 01:11:13,670 polynomials with binary coefficients, F2 of x. 1216 01:11:13,670 --> 01:11:16,470 1217 01:11:16,470 --> 01:11:18,500 And how do we do it? 1218 01:11:18,500 --> 01:11:21,430 Let's write down -- 1219 01:11:21,430 --> 01:11:24,490 let's forget about 0 and 1. 1220 01:11:24,490 --> 01:11:28,280 Those are not considered to be prime. 1221 01:11:28,280 --> 01:11:32,770 Let's start with the degree 1 polynomials. 1222 01:11:32,770 --> 01:11:35,770 What are the degree one polynomials? 1223 01:11:35,770 --> 01:11:38,505 They're x, x plus 1. 1224 01:11:38,505 --> 01:11:42,300 1225 01:11:42,300 --> 01:11:43,550 Are these factorizable? 1226 01:11:43,550 --> 01:11:48,720 1227 01:11:48,720 --> 01:11:52,160 Obviously their only factors are one and themselves. 1228 01:11:52,160 --> 01:11:54,460 They have no nontrivial factors. 1229 01:11:54,460 --> 01:11:55,710 So these are primes. 1230 01:11:55,710 --> 01:12:00,210 1231 01:12:00,210 --> 01:12:01,460 OK. 1232 01:12:01,460 --> 01:12:03,310 1233 01:12:03,310 --> 01:12:11,995 So now let's write down all the polynomials of degree two. 1234 01:12:11,995 --> 01:12:17,550 1235 01:12:17,550 --> 01:12:22,700 I'm sort of doing this in an interleaved manner. 1236 01:12:22,700 --> 01:12:25,950 There are going to be two of degree 1, four of degree 2. 1237 01:12:25,950 --> 01:12:28,330 All I'm going to do is -- well, the only polynomials are 1238 01:12:28,330 --> 01:12:30,410 monic in F2 of x, so I don't have to make that 1239 01:12:30,410 --> 01:12:32,350 qualification. 1240 01:12:32,350 --> 01:12:32,700 All right. 1241 01:12:32,700 --> 01:12:35,000 So here are the four of degree 2, right? 1242 01:12:35,000 --> 01:12:38,150 1243 01:12:38,150 --> 01:12:40,800 Now I go through with my sieve and we take out all 1244 01:12:40,800 --> 01:12:42,560 multiples of x. 1245 01:12:42,560 --> 01:12:48,040 Multiples of x are polynomials with 0 constant term, right? 1246 01:12:48,040 --> 01:12:49,960 A lowest order term. 1247 01:12:49,960 --> 01:12:52,380 So obviously this is a multiple of x, this is a 1248 01:12:52,380 --> 01:12:53,630 multiple of x. 1249 01:12:53,630 --> 01:12:56,580 1250 01:12:56,580 --> 01:12:58,060 Multiples of x plus 1. 1251 01:12:58,060 --> 01:13:00,590 How do you recognize those over the binary field? 1252 01:13:00,590 --> 01:13:05,450 1253 01:13:05,450 --> 01:13:12,380 This is basically the polynomial whose root is 1. 1254 01:13:12,380 --> 01:13:14,050 That means the mod-2 sum of the 1255 01:13:14,050 --> 01:13:16,420 coefficients is equal to 0. 1256 01:13:16,420 --> 01:13:20,200 So any polynomial that has an even number of non-zero 1257 01:13:20,200 --> 01:13:23,500 coefficients is divisible by x plus 1. 1258 01:13:23,500 --> 01:13:24,920 Did you all get that? 1259 01:13:24,920 --> 01:13:29,270 If not, try that at home. 1260 01:13:29,270 --> 01:13:31,510 That's the easy way to recognize whether something is 1261 01:13:31,510 --> 01:13:32,750 a multiple of x plus 1. 1262 01:13:32,750 --> 01:13:36,640 It has an even number of non-zero coefficients. 1263 01:13:36,640 --> 01:13:38,530 So this is a multiple of x plus 1. 1264 01:13:38,530 --> 01:13:40,380 We wrote it out explicitly. 1265 01:13:40,380 --> 01:13:46,600 It's x plus 1 squared in F2 of x, and this is not. 1266 01:13:46,600 --> 01:13:58,410 So there is only one prime polynomial over F2 of x 1267 01:13:58,410 --> 01:13:59,690 that's degree 2. 1268 01:13:59,690 --> 01:14:03,480 So this is our only possible choice if we want to construct 1269 01:14:03,480 --> 01:14:05,985 a finite field with four elements, 1270 01:14:05,985 --> 01:14:07,235 due to the two elements. 1271 01:14:07,235 --> 01:14:09,380 1272 01:14:09,380 --> 01:14:09,870 OK. 1273 01:14:09,870 --> 01:14:13,200 So that might begin to get us scared. 1274 01:14:13,200 --> 01:14:15,080 Is it possible that there are no prime 1275 01:14:15,080 --> 01:14:18,260 polynomials of degree three? 1276 01:14:18,260 --> 01:14:20,390 Well, we had two here, one here. 1277 01:14:20,390 --> 01:14:21,875 Is it going down? 1278 01:14:21,875 --> 01:14:25,710 Let's write down the polynomials of degree 3. 1279 01:14:25,710 --> 01:14:33,400 x third, x third plus 1, x to the three plus x, to the three 1280 01:14:33,400 --> 01:14:38,225 plus x plus 1, x to the three plus x squared, x to the three 1281 01:14:38,225 --> 01:14:44,760 plus x squared plus 1, x to the three plus x squared plus 1282 01:14:44,760 --> 01:14:50,620 x, x to the three plus x squared plus x plus 1. 1283 01:14:50,620 --> 01:14:52,130 Eight of them. 1284 01:14:52,130 --> 01:14:54,370 So that's working in our favor. 1285 01:14:54,370 --> 01:14:57,810 There's double the number of polynomials as we 1286 01:14:57,810 --> 01:15:01,300 go up one in degree. 1287 01:15:01,300 --> 01:15:03,430 And again, let's go through the sieve. 1288 01:15:03,430 --> 01:15:11,990 Which are multiples of x, non-zero constant term? 1289 01:15:11,990 --> 01:15:16,960 Which are multiples of x plus 1, even number of non-zero 1290 01:15:16,960 --> 01:15:18,210 coefficients? 1291 01:15:18,210 --> 01:15:21,450 1292 01:15:21,450 --> 01:15:23,950 If you doubt that, write it out. 1293 01:15:23,950 --> 01:15:27,180 Which are multiples of x squared plus x plus 1? 1294 01:15:27,180 --> 01:15:29,690 Well, they're going to have to be x squared plus x plus 1 1295 01:15:29,690 --> 01:15:33,600 times x plus 1 or times x, so we've already got them. 1296 01:15:33,600 --> 01:15:36,370 If we take this times itself, we're going to get a 1297 01:15:36,370 --> 01:15:38,260 polynomial of degree 4. 1298 01:15:38,260 --> 01:15:41,000 Not going to be on this list. 1299 01:15:41,000 --> 01:15:43,020 So we have to multiply this by these. 1300 01:15:43,020 --> 01:15:44,160 We've already got those. 1301 01:15:44,160 --> 01:15:46,530 So whew. 1302 01:15:46,530 --> 01:15:47,520 We found two. 1303 01:15:47,520 --> 01:15:50,190 We could use either of these to construct a finite field 1304 01:15:50,190 --> 01:15:51,440 with eight elements. 1305 01:15:51,440 --> 01:15:56,040 1306 01:15:56,040 --> 01:15:56,810 And so forth. 1307 01:15:56,810 --> 01:15:59,780 And it turns out as you go up to higher degrees, that the 1308 01:15:59,780 --> 01:16:02,760 number now increases very nicely, and there's no problem 1309 01:16:02,760 --> 01:16:05,420 finding a prime polynomial of each degree. 1310 01:16:05,420 --> 01:16:09,270 And in fact, you could be cute about it and try to find one 1311 01:16:09,270 --> 01:16:13,860 with only three non-zero terms, or has some other nice 1312 01:16:13,860 --> 01:16:17,760 property that makes it easy to calculate with. 1313 01:16:17,760 --> 01:16:20,480 And so forth. 1314 01:16:20,480 --> 01:16:24,240 So do you understand the sieve method? 1315 01:16:24,240 --> 01:16:28,410 If you do, then I believe you could find a -- 1316 01:16:28,410 --> 01:16:34,070 suppose you want to construct a field with 64 elements. 1317 01:16:34,070 --> 01:16:36,510 What do you need? 1318 01:16:36,510 --> 01:16:38,900 64 is 2 to the sixth, so you're going to need a 1319 01:16:38,900 --> 01:16:42,260 polynomial with p equals 2 and m equals 6. 1320 01:16:42,260 --> 01:16:47,540 You're going to need a binary polynomial of degree 6 that is 1321 01:16:47,540 --> 01:16:49,300 prime, irreducible. 1322 01:16:49,300 --> 01:16:52,230 1323 01:16:52,230 --> 01:16:54,770 And again, in a few minutes by going through the sieve 1324 01:16:54,770 --> 01:16:57,460 process, you can quickly find one, or you could look it up 1325 01:16:57,460 --> 01:17:01,260 in Google, or in Peterson's book, or any algebraic coding 1326 01:17:01,260 --> 01:17:05,490 theory book, or probably a lot of other places. 1327 01:17:05,490 --> 01:17:07,810 So this is a practical solution for the problem for 1328 01:17:07,810 --> 01:17:09,120 any given p and m. 1329 01:17:09,120 --> 01:17:13,430 Of course, it hardly proves that there's one of every 1330 01:17:13,430 --> 01:17:15,730 degree, because they're kind of an 1331 01:17:15,730 --> 01:17:18,190 infinite number of degrees. 1332 01:17:18,190 --> 01:17:19,780 Yeah? 1333 01:17:19,780 --> 01:17:24,566 AUDIENCE: So there's two order 3 polynomials that are prime. 1334 01:17:24,566 --> 01:17:27,372 Will it generate two separate fields, or are they going to 1335 01:17:27,372 --> 01:17:29,450 be isomorphic to each other? 1336 01:17:29,450 --> 01:17:32,020 PROFESSOR: Great question. 1337 01:17:32,020 --> 01:17:35,820 All fields with p to the m elements are isomorphic to 1338 01:17:35,820 --> 01:17:37,730 each other. 1339 01:17:37,730 --> 01:17:39,240 That's proved in the notes. 1340 01:17:39,240 --> 01:17:40,490 I'm not going to do it in class. 1341 01:17:40,490 --> 01:17:42,810 1342 01:17:42,810 --> 01:17:45,410 And the other thing that's proved in the notes is the 1343 01:17:45,410 --> 01:17:48,200 analog to Zp. 1344 01:17:48,200 --> 01:17:52,790 There are no other finite fields with other than p to 1345 01:17:52,790 --> 01:17:55,920 the m number of elements. 1346 01:17:55,920 --> 01:17:56,230 OK? 1347 01:17:56,230 --> 01:17:58,520 So this is it. 1348 01:17:58,520 --> 01:18:01,870 Now, if you explicitly write out these two, and 1349 01:18:01,870 --> 01:18:04,570 write out their -- 1350 01:18:04,570 --> 01:18:07,960 well, the addition tables are always look the same, because 1351 01:18:07,960 --> 01:18:11,630 it's always just binary three-tuples, in this case. 1352 01:18:11,630 --> 01:18:15,170 But multiplication tables are going to look different. 1353 01:18:15,170 --> 01:18:16,483 But there is some isomorphism. 1354 01:18:16,483 --> 01:18:19,720 1355 01:18:19,720 --> 01:18:25,820 x and 1 may be equivalent to x squared plus 1 on the other 1356 01:18:25,820 --> 01:18:27,490 one, or something. 1357 01:18:27,490 --> 01:18:31,040 But if you go through that isomorphism, you'll find that 1358 01:18:31,040 --> 01:18:33,270 the field tables are the same. 1359 01:18:33,270 --> 01:18:36,220 1360 01:18:36,220 --> 01:18:38,790 Actually, I guess I'm going to prove that, because I'm going 1361 01:18:38,790 --> 01:18:41,860 to prove that the multiplication 1362 01:18:41,860 --> 01:18:45,390 table is always cyclic. 1363 01:18:45,390 --> 01:18:50,530 That the group to which it's isomorphic is z mod p 1364 01:18:50,530 --> 01:18:53,590 to the m minus 1. 1365 01:18:53,590 --> 01:18:56,260 Just as it was to Z3 here. 1366 01:18:56,260 --> 01:18:59,080 And I guess that's sufficient with the addition table 1367 01:18:59,080 --> 01:19:00,310 isomorphism. 1368 01:19:00,310 --> 01:19:02,140 I guess you have to prove they're equivalent. 1369 01:19:02,140 --> 01:19:04,140 You saw it in a different way in the notes. 1370 01:19:04,140 --> 01:19:10,360 But you're going to see that all the multiplication group 1371 01:19:10,360 --> 01:19:14,900 is always a cyclic group, with p to the m minus 1 elements, 1372 01:19:14,900 --> 01:19:17,530 and that goes a long way towards suggesting that these 1373 01:19:17,530 --> 01:19:20,150 are always going to be isomorphic to each other. 1374 01:19:20,150 --> 01:19:20,846 Yeah? 1375 01:19:20,846 --> 01:19:23,230 AUDIENCE: Identify roots, right? 1376 01:19:23,230 --> 01:19:24,480 PROFESSOR: Identify roots? 1377 01:19:24,480 --> 01:19:27,460 1378 01:19:27,460 --> 01:19:29,340 If I understand what you're saying, that's basically the 1379 01:19:29,340 --> 01:19:31,010 way it's done in the notes. 1380 01:19:31,010 --> 01:19:37,230 You first show there's always going to be some primitive 1381 01:19:37,230 --> 01:19:41,330 element that generates the cyclic group. 1382 01:19:41,330 --> 01:19:45,070 Some single generator such that alpha alpha squared, so 1383 01:19:45,070 --> 01:19:50,170 forth, is the entire non-zero set. 1384 01:19:50,170 --> 01:19:54,600 You're going to show that alpha has some minimal 1385 01:19:54,600 --> 01:19:59,950 polynomial, and the set of all linear combinations of powers 1386 01:19:59,950 --> 01:20:04,350 of alpha is basically equal to the whole field. 1387 01:20:04,350 --> 01:20:10,970 And so this allows you to establish the isomorphism. 1388 01:20:10,970 --> 01:20:15,250 and I think that's what you're suggesting. 1389 01:20:15,250 --> 01:20:17,950 So you're well equipped to read the notes, but I'm not 1390 01:20:17,950 --> 01:20:19,200 going to do that in class. 1391 01:20:19,200 --> 01:20:23,520 1392 01:20:23,520 --> 01:20:24,370 Yeah. 1393 01:20:24,370 --> 01:20:28,340 I'm very interested in your questions. 1394 01:20:28,340 --> 01:20:32,320 Please ask more, as many questions as you like. 1395 01:20:32,320 --> 01:20:35,230 What I'm getting from it is, you know, you all come from 1396 01:20:35,230 --> 01:20:36,170 different backgrounds. 1397 01:20:36,170 --> 01:20:40,350 Some of you have seen this in perhaps a math context, or 1398 01:20:40,350 --> 01:20:43,360 some other context, or you've seen parts of it, or some of 1399 01:20:43,360 --> 01:20:45,650 the words are familiar. 1400 01:20:45,650 --> 01:20:49,050 And of course, there are many different ways to present this 1401 01:20:49,050 --> 01:20:52,320 and to make the proofs and so forth. 1402 01:20:52,320 --> 01:20:56,770 So I'm trying to pick a line that works for the particular 1403 01:20:56,770 --> 01:20:58,030 results that I want to get to. 1404 01:20:58,030 --> 01:21:00,560 I don't think you would do anything much different if you 1405 01:21:00,560 --> 01:21:03,950 wanted to develop finite fields. 1406 01:21:03,950 --> 01:21:09,275 But the class has a very different set of backgrounds, 1407 01:21:09,275 --> 01:21:10,910 and I'm trying to reach all of you. 1408 01:21:10,910 --> 01:21:14,940 1409 01:21:14,940 --> 01:21:16,540 Don't be alarmed if you've never seen 1410 01:21:16,540 --> 01:21:17,930 anything like this before. 1411 01:21:17,930 --> 01:21:21,560 You're not way behind everybody else, either. 1412 01:21:21,560 --> 01:21:26,310 I think it's pretty easy to understand. 1413 01:21:26,310 --> 01:21:29,900 Maybe it would take you a couple hours longer than 1414 01:21:29,900 --> 01:21:31,470 somebody who has more background, but 1415 01:21:31,470 --> 01:21:32,720 not more than that. 1416 01:21:32,720 --> 01:21:35,990 1417 01:21:35,990 --> 01:21:37,830 OK. 1418 01:21:37,830 --> 01:21:42,360 So that's how we construct finite fields. 1419 01:21:42,360 --> 01:21:45,940 You have an example of it. 1420 01:21:45,940 --> 01:21:46,440 Goodness. 1421 01:21:46,440 --> 01:21:48,740 Is it really 11 o'clock? 1422 01:21:48,740 --> 01:21:49,520 OK. 1423 01:21:49,520 --> 01:21:51,390 So I'm not even -- 1424 01:21:51,390 --> 01:21:56,010 so I've simply asserted, but not proved. 1425 01:21:56,010 --> 01:21:59,020 You saw in this case that the multiplicative group was a 1426 01:21:59,020 --> 01:22:00,770 cyclic group. 1427 01:22:00,770 --> 01:22:04,530 And we could always, for multiplication, represent 1428 01:22:04,530 --> 01:22:06,800 grouped elements by this log table. 1429 01:22:06,800 --> 01:22:08,590 So I'd hoped to prove that in class. 1430 01:22:08,590 --> 01:22:11,860 I'm not going to be able to prove that in class. 1431 01:22:11,860 --> 01:22:16,400 And I'll simply ask you to read that, too. 1432 01:22:16,400 --> 01:22:20,370 This is important for working with finite fields, because it 1433 01:22:20,370 --> 01:22:23,500 is the way, probably the preferred way, to implement 1434 01:22:23,500 --> 01:22:24,750 multiplication. 1435 01:22:24,750 --> 01:22:26,910 1436 01:22:26,910 --> 01:22:31,180 So you ought to be thinking of how you would program up a 1437 01:22:31,180 --> 01:22:34,810 finite field multiplier. 1438 01:22:34,810 --> 01:22:36,700 One way is polynomial multiplication. 1439 01:22:36,700 --> 01:22:41,200 The other way is just use the fact that the multiplicative 1440 01:22:41,200 --> 01:22:43,160 group is cyclic. 1441 01:22:43,160 --> 01:22:44,580 And then it's easy. 1442 01:22:44,580 --> 01:22:50,810 Just add exponents and reduce modulo q minus 1. 1443 01:22:50,810 --> 01:22:51,120 OK. 1444 01:22:51,120 --> 01:22:54,700 I'm sorry not to have had a chance to go over that. 1445 01:22:54,700 --> 01:22:57,510 Next time, Ralf Koetter will start to get into chapter 1446 01:22:57,510 --> 01:22:58,760 eight, Reed-Solomon codes. 1447 01:22:58,760 --> 01:23:10,676