Fast Fourier Transform Definitions | Part 1

In the previous video, I mentioned that the fast warrior transform is a algorithm that evaluates a polomial p of degree less than n at n roots of unity where w is the nth primitive root of unity. To understand this statement, you need to know what a polomial is, what the degree of roots of unities are, and what is a primitive nth root of unity. So in this video, I'm going to explain what a polomial is, what it means for a polomial p to have degree less than n. the m roots of unity and finally the primitive mth root of unity. So let's begin by defining what a polomial is. A polomial is a equation of the form a 0 + a1 * x + a2 * x^ 2 + a3 * x rais^ 3 so on all the way up to let's say n minus one. So there are n terms starting from 0 to n minus one. These variables that you see in blue are called coefficients. In this video series, you can think about these coefficients as simply numbers. I'm going to be teaching you fast for your transform in the context of finite fields. Moreover, the finite field that we're going to be working with is called prime fields. Basically, we're dealing with numbers with x mod p where this p will be a prime number. And what this means is that we're basically going to be doing addition and multiplications on numbers between 0 to p minus one. So all of these coefficients a 0, a1, a2, a3 all the way up to a minus one, you can think about it as a number between 0 to p minus one. And what goes inside this x? This x will be a element in the finite field. In our context, we're going to be working with the prime field. So again x will be one of these numbers between 0 to p minus one. So that is polomial basically a equation of this form. So now that we know what a polomial is what is a degree of polomial what does it mean for a polomial to have degree less than n. The degree of polomial p is the highest power of x where the coefficient a is not equal to zero. So looking at this equation and let's say that a to the n minus one the coefficient is not equal to zero. It's a number between 1 to p minus one. Then in this case the degree of this polomial will be n minus one. Since the highest power of x with a i not equal to zero in this expression will be n minus one. Let me give you one example of a polomial and a degree of polomial. So let's say that we have a polomial p and let's put in some concrete numbers here. Let's say for a z we put in a one. For a1 let's put in two. For a3 let's put in a five. And two again. Okay. And the prime field that we're going to be working with this x mod p part. Let's say that the prime number p is equal to 7. 7 is a prime number. So the valid coefficients that we can put in here will be the numbers between 0 to p minus 1 which will be 6. This is an example of a polomial where each coefficient is a element from the prime field where p is equal to 7. Next let's ask the question what is the degree of this polomial? Well going back to the definition the degree of a polomial is the highest power of x with ai not equal to zero. In this example, what is the highest power of x where the coefficient a is not equal to zero? Well, the highest power of x where the coefficient is not equal to zero is x raised^ 3. So in this example, the degree of this polomial will be equal to 3. Another question that you might have is how do you evaluate this polomial over the prime field. So let's say that we wanted to evaluate let's say x= 2. How do we evaluate this polomial? Well, we're going to take this expression and then I'm going to plug in twos over here. And what you're going to do is evaluate this mod p where p is equal to 7. I just notice that we're using p for the polomial and p for the prime number as well. This is a little bit confusing. So I'm going to say that the prime number that we're going to be dealing with I'll rename this as q. So going back to our polomial evaluation, we need to evaluate this at mod q. There are several ways we can evaluate this expression. We can first calculate the inner part and then take mod q or we can take mod cubed of the individual terms. So either we can do this or we can do something like this. Evaluate each term mod q. In our example this prime q will be seven. Let's put in the number seven. Okay. And then we'll evaluate each term one at a time. 1 mod 7 is equal to 1. 2 * 2 mod 7. 2 * 2 is 4. So mod 7 will be equal to 4. 5 * 2 raised to the^ 2. 2 rais^ 2 is 4 * 5 that's 20. 20 mod 7 is

equal to 7 * 2 is equal to 14. 20 - 14 is equal to 6. We'll have a remainder of 6. Okay. And the last term 2 rais^ 3 is equal to 8 * 2 that is 16. 16 mod 7. 7 * 2 is 14. So 16 - 14 is equal to 2. Okay, so we evaluated each term one at a time. The last step is to add all of these up and then take mod 7 again. So this is equal to 4 + 6 is 10 + 1 11 + 2 13 mod 7 which is equal to 6 mod 7. So this was an example of evaluating this polomial over the prime field where the prime number was equal to 7 and we evaluated at x= to 2. We got back the answer was 6 mod 7. Okay. So next let's move on to n root of unity. What does this mean? W is a m root of unity if w raised to the power of n is equal to 1. Here we're going to be looking at fft using the prime field. So here I'm going to mention that this is 1 mod q where q is the prime number. Next I'm going to explain what the primitive nth root of unity is. W is a if w raised to the power of n is equal to 1 and w raised to the power of i is not equal to 1 or i greater than zero and less than n. Let's look at some examples of n root of unity and primitive n root of unity. Consider the number w = to 2 mod 5. So here the prime field that we're working with will be the prime number five. This is we're only considering the numbers between 0 to 4. Okay. Next I'm going to show you that this w is a nth root of unity and also a primitive nth root of unity. But I don't know what this n is yet. So what I'm going to do is raise 2 to the power y mod 5 several times from i = 1 to i = 8. and then we'll evaluate this mod 5. We'll try to find where this expression 2i mod 5 is equal to one. So let's start by evaluating 2 raised to the power by 2 raised to the^ 1 will be 2. 2 will be equal to 4 raise it to the^ 3 = 8 and so on all the way up to 2 rais^ 8 which is equal to 256. Now let's evaluate this mod 5. 2 raised to the^ 1 mod 5 will be 2. So 2 equal to 2. 4 4. 8 mod 5 will be equal to 3. How about 16 mod 5? Well 5 * 3 is equal to 15. 16 - 15 is equal to 1. So this is equal to 1 mod 5. How about 32? Well 5 * 6 is equal to 30. 32 - 30. We have a remainder of two. So this is 2 mod 5. 64. 5 divides 60. 64 minus 60 will have a remainder of four. 128 the number five will divide 125 and the remainder will be three. And finally 256. Again the number five will divide 255 subtract that and we'll have a remainder of one. Okay. So this is our evaluation. Now let's try to find the nth root of unity and the primitive nth root of unity. First I'm going to highlight where the ones are. So there's a one over here and as well. Okay. So now let's scroll back up to the definition. A number w is a nth root of unity if w raised to the power of n is equal to 1. So we have two ones over here. We raise 2 to the^ 4 to get 1 and of 8 to get 1 as well. This makes 2 the fourth root of unity and the eighth root of unity. 2 raised to the^ 4 is equal to 1 and 2 raised to the^ of 8 is equal to 1. Okay, how about primitive nth root of unity? A number w is a primitive nth root of unity if w raised to the power of n is equal to 1 and w raised to the power of i is not equal to 1 or i greater than zero and less than n. So let's apply this to our number two. Is 2 a primitive orth root of unity? Well 2 raised to the^ 4 will be equal to 1. So it satisfies this condition. And how about this condition for i less than n will be equal to 4. Is it not equal to one? Well, let's check our evaluations. So we need to look at 2 raised to a power by up until 4 excluding four. And we see that all of the evaluation are not equal to one. Well, this makes two the primitive fourth root of unity. How about is two the primitive eth root of unity? Well, again let's apply this definition. 2 raised to the^ of 8 is equal to 1. So 2 is a e a root of unity. Now is it a primitive eth root of unity? The other condition that needs to

satisfy is this part. So we need to look at our evaluation from i = 1 all the way up to i = 8 but less than 8. So that's 1 to 7. And we need to make sure that 2 raised to the^ i is not equal to 1. But looking at the evaluation, we can see that 2 raised to the^ 4 is equal to 1. In this case it doesn't satisfy this condition. So two is not the primitive eth root of unity. Okay that completes the definitions for polomial degree of polomial nth root of unity and the primitive nth root of unity. In the next video, I'll show you two useful properties of root unity that we're going to need to understand FFT.