Cryptography of Ethereum | Lesson 3

recording is on.

Awesome.

Okay. Um so welcome back. Before I start, um are there any questions on what we did uh last time? All right. So of course as as before you can uh ask during the session uh and let me recall what we did.

We took a field um f FP the field of uh residues of modul integers. Um and we took fe to be uh a polomial over the field of degree n let's say bigger than one and fe is prime prime meaning that you cannot write it as a product of two non unconstant polomials. And then we did a construction that is completely analogous to um to FP that is we we denoted it as eventually as um F p to the n and this is the collection of all polomials are that h can be obtained as a residue. of a long division mod of fe long division of a polomial a by v. So this is rx um let's say sum a i x to the i equals zero up to n minus or up to k such that k is smaller than n and the a i's are in f and on this set we saw that a plus modul and multiplication modul turns it into a field.

This is a um this is quite surprising maybe for uh seeing it for the first time. And and so FPN is a field with a P2DN elements. And moreover f namely FP can be embedded naturally in FP to the N. How? Because this polomial r you can also pick it to be um some a some constant polomial a where a is in the field.

So all the elements in the field are in fact in fp to the n and all the arithmetic that existed in fp um is is extended to fp to the n. So when you do arithmetic of let's say a and if you have b then it's the same multiplying the polomial rx= a and r and sx= b in fp to the n is the same as multiplying them as in fp namely multiplying and taking modul and then putting them as constant polomial or putting the result as constant polomials. So this is called a field extension.

And now Yes. And and now since FP is a a a sub field of FP to the N and F is a polomial over FP like any field extension. I mean if I give you a polomial over the real numbers you can consider it as a polomial over the um complex numbers because the complex numbers extend the real numbers. Um we can consider f as a polomial in fp to the n and I will I will take take another variable here x big x to disambiguate because we we used the small x for other purposes. is namely for the the the remainders polomials rx.

So now if I consider fee as a polomial in this pol over fp I I attach to it a big variable x big x but the coefficients of fe whatever they are let's say f FX is sum fi x to the i. Then f with big x is going to be sum f ii big x to the i. So I didn't do anything. It's like complete formality. Well, okay.

So now I have a polomial over fp to the n over fp. FE was a prime polomial name in particular it means that it doesn't have any roots because then you can factor if it had root h you can you could have factored this polomial in a non-trivial way however um what happens so so here in this a a new kind of weird field FP to the N. The elements are themselves polomials. And in particular, I have the polomial let me call it um alpha. Alpha X= X.

This is a polomial. So alpha is an element in the field FP to the N. and and like any element in a field and a polomial over this field I can substitute the element into the polomial. So we can do I have the the the writing of this is you have f with big x and now you substitute big x equals alpha and alpha alpha I remind you is alpha of x is equal to x. So I basically I substitute instead of big x I substitute small x.

What I get is f with small x. And this is an this needs to be like with any substitution. If you you take a polomial over a field and you substitute an element in the field into the the variable of the polomial you get as a result an element in the field. So this vx needs to be considered as an element in fp to the n. But in FP to the N we do addition and multiplication modul mod of FE this is should you can think of it as modul small X and F small X modul small X is equal to zero.

So what did I get? And now it means that this this element alpha x= x is a root of f with big x over the new field. The new extended field fp to the n. This this means that I can write fx equals x minus the root times some other polomial let's say f prime of big x and this is this is a kind of a magic it's it's a you can consider it as a as a meta trick I didn't have a poly I didn't have a root of FE in the small field and I extended it and now I have a in the bigger field I have I have a root. Um and and so this this is an insight that is very important for understanding finite fields.

Any questions on on this uh on this so far? It's a it's not a trivial uh thing to to wrap your head around. Yeah. Okay. So, let me do it because this is relevant for any field.

Let me do it with the real numbers. It's not a finite field, but everything we did is valid for any field. A and I take f small x to be the polomial x² + 1. This is prime of degree 2. Why is it uh why is it prime?

Because uh well for polomial of degree two if it doesn't have any roots uh then it cannot then it has to be prime because the only way you can factor a polomial of degree 2 into product of two things is h x minus alpha x x minus beta. So if you don't have any alpha beta where alpha and beta are roots. So this is a prime polomial. Now I do the remainders f um we called it I think f or fx fx subv. This is the set of all remainders if you do division modul of fe.

But if you do division model of fe the remainder can only be a polomial of degree at most one. So this is the set basically of um a a + x or sorry a a + x sorry a + b x. Uh so in fact I can do like this this collection of all a plus b x such that a and b are real numbers and it it could be that that b is zero or or that a is zero. This is the collection of all remainders. If you do modulo fe and now I um I look at this collection.

On this collection I have a operations addition modulo fee and multiplication modu and if I do a + b x times c. So, so now I I I consider the polomial f with big variable. Okay, f with big variable. And now I I substitute um the polomial alpha x equals x. Well, okay.

I substitute alpha x. I substitute instead of big x. I substitute alpha x I get well I get um x² + 1 and uh x² + 1 is equal to 0 modulo x2 + 1. What I got here in fact here this fx uh subf is some kind of version of the complex numbers. If you do addition and multiplication modul of onederee polomials you will see that this this guy x behaves like the like the imaginary number i.

this because x² x x² + 1 is equal to 0. It means it's the same thing as saying that x² is equal to minus1. So in fact this small x functions as a the imaginary number it's just it's just a a a new notation. Um and this is the reason that once I substitute small x I mean namely alpha x equals small x into the new polomial over the the new field. Now I have a root because x² + 1 in fact is a a x - i x + i over the complex numbers.

Okay. So, so this is maybe I hope I hope that this is a bit more uh a bit more uh clear now. But in fact, the trick the trick itself is a meta trick. It's like I I forced I forced a a um a a field that extends the new field, but it it now it has a root. It has a root of the the polomial by design.

I don't it's not a Well, okay. theorem for any polomial uh let's say FP but it's not uh again it's not restricted to FP just that we will use it for FP there exist n such that um or maybe big n such that um over fp to the n f factors or decomposes to linear factors. That is I can write f over this new extension extended field. I can write f as lambda * um x - alpha 1 up to x - alpha k where alpha 1 up to alpha k um are elements in the new field to the n and let's say K K is the degree of of F. Okay, this is it's kind of a miracle, but um in fact it's not so hard to to to prove this theorem because what do you do?

You take a a a prime factor and let's say proof sketch take prime factor of f i.e F is equal to F * um whatever F_sub_1 or F prime where FE is prime. Now you do the trick that we did. So you consider fp uh x modulo this a prime polomial field and this is your new field f uh one over this new field over f_sub_1 the small the polomial f has a root because because f has a root. So you take f and you you you extract a root out of it.

So it's like x minus this root. So over f_sub_1 you write f uh let's say f e big x equals x minus this root times some um polomial g and now you repeat now g you take a prime factor of g and you extend the field f_sub_1 into a field f_sub_2 and then g will have a root into in this uh field f_sub_2 and so on. So you you this this process terminates because the degree of the polomial is finite and h by that you you are able to extend a field up to a up to a level where all the roots of the original polomial exist in the extension. And one of the things I want to do today is to show you why is it useful for practical purposes not just for this. It may sound like some kind of grand theory.

Um so first example if I have um f(x) equals x to the n -1 then there exist some n such that x to the n -1 is equal to x - alpha 1 up to x - alpha n over fp to the n. Okay. Alpha 1 up to alpha n are denoted mu n of fp and this is called a nth roots of unity. It's roots of unity because each of them satisfy alpha to the n alpha i to the n equals 1. Okay.

If you do the calculation in the over the complex numbers what you will get over C what you will get is you you divide the circle into n different equal parts let's say to three parts and each of these points on the unit circle will be a a root of unity. This is n= 3 but over but what we did allows us to do it over prime fields. So I I take a prime prime field and and now I I can extend it into some some field in which all the roots of the polomial x to the n minus one exist. Now observe Mu so mu n fp is a group why take take two elements let's say alpha and beta are two nth roots of unity Then if I take alpha times beta I need to see that a alpha time beta is is again an nth roots of unity. So I I raise it to the power of n.

But raising it is the same as doing alpha to the n * beta to the n. And alpha is is alpha to the n is one. Beta to the n is 1. So this is 1 * 1 = 1. Similarly, if I take alpha minus one, it's also going to be an n/ roots of unity because if I raise it to the power of n, it's the same thing as doing alpha to the n and then taking inverse and alpha to the n is one and the inverse of one is one.

Um moreover say theory mu n of fp is a cyclic group and here I don't really prove but the the proof is because mu n of fp B is a subset of the multiplicative group of some extended field and the multiplicative group of um of any of any finite field is a cyclic group. This is this is kind of a big theorem. So and a sub in a subgroup of a cyclic group is cyclic. So this means m w such that mu n of fp is generated by w is called primitive. So primitive and root of unity is is some some guy such that w to the 0 w² up to w n minus one is going to be the the entire description of um the group of n which of unity.

Okay. Um question so far I I uh I should have said maybe in the beginning I know it is it may be um somewhat uh somewhat hard to digest in one go. So if it is a bit hard uh try to kind of listen to the music and you will have all the details in the book. uh to check and um and for those of you who who saw these these things a bit before I I think that uh should be possible to follow most of the details.

Yeah, I mean we already heard that people like to uh go back and rewatch some parts of the lessons. That's why we record them. So uh don't don't be worried guys if you don't understand this on the first first time. Uh but meanwhile we also had a question. and Lee was raising hand if we have a minute to take a question from him.

Yeah, then go on.

Uh yes, I was I was like confused what alpha x is.

Uh alpha here if alpha and beta are nth roots of unity.

No no no I mean the very beginning part so I get lost from that part actually. Oh

uh yeah because I don't why why is there is alpha

and uh

I didn't say that yes

alpha is is just a notation so what what I did I took um the the whole construction of this fp to the n is I mean as a set it's a set of polomials right polomials of degree less than n

right

and the the and and the operations are are a bit weird because you do addition and and and and multiplication modul but as I said it's just polomials of degree less than n and we assume n is bigger than one so I have a polomial that I denote as alpha that is simply the polomial x right

okay

okay Now I said FE is is a polomial over the original field FP but the original field FP is contained in a bigger field FP to the N. How can F is

so I can

sorry how can F is like ele element from the original uh field. I mean like phase should be a polinomial right because const I mean how f is embedded into fp to the n this is as constant polomials you take a in fp you can consider it as the polomial rx= a right it's a legitimate polomial Uh okay.

Okay. So this means and but but this is this is a general principle. Whenever you have a field extension and you have a polomial over the small field, you can consider this polomial over the big field because all the coefficients of the polomial are in the small in the the small field and you can think of the small field as as embedded into the big field. You see?

Yeah. Yeah. I can I can say like a small field is embedded into the big field. But here you define like uh 5x uh within the uh FP but FP is a small field right?

Yeah but FP to the N is a is a big field.

Ah yes okay oh yes okay yes

okay so now I want to consider FE over the big field FP to the N. Now be to disambiguate I write f with a a variable big x instead of small x because in the the definition of elements of fp to the n we use small x you you follow

yeah yeah yeah yeah

okay so now I have a new I have a it's I have a new polomial technically it's a new polomial even though the the coefficients are the same but now it has a big variable x and it is considered over the big field fp to the n.

Yes.

Okay.

And now just like with any polomial over any field if I give you an element in the field you can substitute this element instead of the variable of the polomial.

Okay.

Yes. So I just I take the big polomial fx and I substitute instead of it its variable I substitute the element in the field alpha x alpha small x.

Yeah

I I am allowed to do I have to be allowed to do it. It's like a basic operation of a polomial over a field. Right.

Yes.

Okay. What happens when I do that? It's because alpha x is simply x small x. What happens is that I get f of small x but f of small x is equal to zero in fp to the n because I do module fe. Yeah.

Okay. So I have found an element alpha x= x that is a root of this polomial f big x. So now the polomial fee that was prime and did not have any root now it has a root over the extended field it has a root and the the the analogy is you take x2 + 1 over the real numbers it's not it does not have any root but once you extend it and in fact the complex numbers are exactly the construction we did

like that all remainder polomials with modul arithmetic then the the variable x is like is like i it behaves like i because if x² + 1 is is equal to zero then x² is equal to minus1

so so you see so now so we extended and and you can repeat the theorem said that you can repeat this this thing so any polomial you can extend the the the the original field enough so that this polomial has all the roots it it can have.

Okay.

Yes. So now I do this for a specific polomial x to the n minus one and I find that h the elements of the roots of this polomial in whatever extension they you know they exist when it's completely um factors into linear linear polomials product of linear polomials this root Foods are in fact a group and moreover proposition if um the GCD of P and N is one. Namely, if P does not I mean it's the same thing as saying P does not divide N then the size of the group of N roots of unity is exactly N. Namely all the roots i.e All roots of x to the n minus one are different in a proof sketch.

Otherwise if I had two two roots of x to the n that are equal say um because it could happen right for general polomials say um uh alpha alpha 1= alpha 2 equals alpha. um in mu n then I could write x to the n minus one I could write it as x - alpha squared times some other polomial gx i.e E alpha is a root of M X to the N minus one and of the derivative the the formal derivative of X to the n minus one uh that is uh d sorry n to the n minus So this is this is in general if you have a double root then it has to be a it's I mean a double root is the same as a root that is also a root of the h derivative and so lee can you mute mute your and so a double root has to be a root of the derivative. And if n is is prime to p and um alpha cannot be zero because it has to be a root of unity. It has to be a a nth power of it has to be one.

Um and n is prime to p. So p does not divide n. So um alpha is not a root of the derivative n x to the n minus one and that's a contradiction. Um so okay so this is the group of n roots of unity. Now um I have one more piece of technology that that we need in in order to do this fast for transform and this is called lrange interpolation.

Okay. So what is this? What is this lrange interpolation business here? It is um it is instructive I think to go back to uh Uklid. So Uklid said and between any two any two points P1 = X1 Y1 P2 = X2 Y2 in the uh ukidian plane.

This is we denote it as R2 and there exist a unique line that passes through this h these points. How how do you know it? Well, okay you can I mean here for Uklid it was even without coordinates it was like an axiom but in fact um we we know with coordinates we we can turn this axiom into a a proposition that can be easily proved because a line is is has this equation y = ax + b and if I know that it passes is through P1 and P2. Then I have two equations in two variables. I have Y1 = A X1 + B.

Y2 = A X2 + B. And they are unique A and B such that these two equations are satisfied. And so if we take um F= FP. So now now I consider the the FP plane. The FP plane FP align um in the FP plane.

This is FP². is the set x y in fp² such that y = ax + b for some fixed a and b in fp. So you see this the whole if I if I'm able to define the notion in this case the notion of a line in terms of a polomial equation then it makes sense over any field I don't need to have a geometric interpretation over it. So this is a line over FP and the same the same insight of Uklid will be true for the line over FP because um here as well uh between any two points P1 and P2 two in FP² there exist one line right why because you you take the same equations P1 and P2 are now X1 X Y1 X2 Y2 but in FP square not in R square and you you write the same equations and you find out that there is there is a unique solution A and B and so you get a line you get a line by this definition. Uh is this clear this this idea?

Um I don't understand the question. Marvel uh which which calculation do you refer to?

It was a while ago. Um, and I'm not sure if Marvel is still with us. Seems like he left already. Okay. Um, so please don't be shy in raising a hand.

I just don't see the h the chat that often. Um so what I'm saying here is that this is this is in fact a a wider a wider phenomena. This is a theorem given a field um f and end points let's say p1 = x1 y1 up to pn n equals xn yn um with distinct x coordinates. There exist a unique polomial um say f of degree less than n such that f of x i is equal to y i for every i between 1 and n. And you you can treat this theorem as exactly is a generalization of the the the fact that between two points also over FP there exist exactly one polomial of degree 1 right it's like if you have n points you there exist a polomial of degree less than n a unique polomial that passes through these points and the the the proof of this theorem which I will not do but it's basically you write n equations in n variables and you find out that there exist a unique solution and these are the the unique solution is the coefficients of your desired polomial f and um moreover there is a formula um you take let's say for Any i between 1 and n you calculate a specific polomial l i0 of x.

This is a you take product of x - xj where j runs over all indices between one and n that are not i and you mod out by the product of all expressions of the form. This is now just a co just a product of coefficients x i0 minus xj where again j runs over all the indices that are not i and then the the final polomial the lrange interpolation is sum y i l i x i runs from I runs from um one up to n ah sorry up to n minus one right so here it's should also be Yeah. Okay. So, uh no here this would be n. Yes.

H the the the formula is not going to matter that much to us. It's just a I'm putting it here for uh convenience. What I need you to to understand this lrange interpolation is a very powerful tool in everything we in many many things we do in cryptography simply because we use polomials all the time one of the things that I I I don't think I will have time to um expand on but this is a polomial commitment and the lrange interpolation is is a very useful tool for working with polomial Which bring us to what I wanted to to discuss today really the the the um the application of the mathematics we did into a a some kind of algorithm. This is this is the fast transform. And here and again um think about the fact that we use polomials in cryptography all the time and we we do operations with with polomials and these operations they need to be fast as fast as we can.

So, um yeah, it may be um let's say okay I I I think maybe it's time it's a good time to take a break or maybe questions and then a break um and h start the the fast reactions from afterwards. Are there any questions about these two things about the the a group of n roots of unity and um yes so so there are other methods to interpolate apart from lrangege. LRE is particularly useful in in cryptographic applications but it's it's not by far not the only one. So this depends on um depends on your application but we for the mo vast majority of the cryptographic application we use lrange interpolation. It's the reason is the is this this this simple form um as a sum of of polomials is is very convenient for applications.

Any other questions before we take a break? Okay then. And what? Yes. Okay.

So what what efficient means will interpolate? Look what you see here. I will touch it later on. But what is the complexity? If I give you the the points P1 up to PN, what is the complexity the time complexity of calculating the Lrange interpolation?

Well, each of the LI zeros would take me O of N. H, right? Because I need to do this. I have a product of N factors and so on. and I need to I need to do n such.

So um the overall complexity is going to be of of calculating l of l of x is going to be o of n². Okay, it's h for big n it it can be substantially complex but usually what we have is we have a big prime and the the n is not that big. The prime is very big. It's like it's like maybe 300 digits. It's a interactable but but the n is not that big.

Okay. So let's take a break of 10 minutes and see you see you again after that for the fast for transform. So um the fast for transform um is in my opinion it's the most important algorithm in applied mathematics. H it is used all over the place. Of course there are different versions of it but it has a version in sound analysis and and our version will be over finite fields uh which is useful for cryptography.

In fact, it is it is so robust that it is has been generalized into various highly theoretical constructions in in pure mathemat in theoretical mathematics. Um and so I hope you you can appreciate the algorithm is very simple and we have all the all the information all the tools we that that are needed to to understand it. We might uh uh go a bit over time if we if I want to cover uh all of it. Uh so I'll try to be quick uh but still uh stop me if you if you have any questions. So the the the story here is like we we have a two representations or let's say I I start with a polomial over FP of degree less than N.

And I have two representations at least two of of F. one is a the sampling representation or maybe let's say the first one is the vector vector representation is well f is is a a can be thought of as a vector of it coefficients f0 up to fn minus one maybe some of the coefficients maybe fn minus one is zero and and so on I don't care So this this leaves in FP to the n the cartisian product of FP with itself. And what lrange interpolation tells us is that if you had this polomial and you you had a sampling a a given x which is x1 up to xn some subset of fp this is called the s sampling set it. Of course if you had the polomial then you you could you could evaluate it on all the x i's you get some y eyes i um points x1 y1 up to xn xn yn These are points um that the if I had a polomial f and I would do this sampling procedure then this polomial would would pass through these points. But conversely if you give me any two points any sorry any nup of points then by lrange interpolation there exist a unique polomial f of degree less than n as such that a f passes through these points namely f of x i is equal to y i for every i.

Okay. So, so we have these a two e two representations possible representations of a polomial f let's say f is a um maybe write it here f of x is sum f_si x to the i equ= z up to n minus one And now when we do when we deal with polinomials we have three basic operations. One of them is a you add two polomials. So um if I if I give you two polomials let's say f is sum f_subi x to the i i = z up to n minus one and g is sum g i x to the i or maybe gj j maybe it would be clearer gj x to the J equ= uh 0 up to n minus one then you can you can add these two polomials. So if you are in the vector representation I mean this pol this polomial f is just this vector f0 up to fn minus one and this is g0 up to g n minus one and you can so in the vector representation you just do h f0 plus g0 0 up to f n -1 + g n -1 and this is your vector representation of the sum of f and g when you want to add in this if I give you the polomial in the sampling representation then that is uh that is slightly different.

So in the sampling representation or um you know what let's let's just do all the all the operations. Um so we have addition, we have evaluation in the vector representation. I have a um I can write f of x as a this is called the horner rule. I think I can write it as f0 plus x f_sub_1 h + x f_sub_2 plus x fnus 2 and plus x fnus one. And if you give me a in f I can I can plug it in into this formula and evaluate the polomial in complexity um O of N.

Right? You see that using this formula you have n operations. Um so if you give me if you give me f in vector representation using the horner rule using this formula I can um in the vector representation I can do it in O of N also addition I can do in O of N but multiplication of F and G it takes me O of N² I don't I don't want to spend time to write the formula again but if you look at the formula it's very easy to see that it's it's a n square complexity now when I say complexity I really mean for simplicity is like the the number of um field operations either addition or multiplication I count each addition multiplication I count count as a one unit of time and when I I write all I mean This could be um 3 n² or it could be uh you know 5 n square or all of them I I call them n² it's like the the order of magnitude is um is n square but when I go to um to the something representation so here um let's say what do I need to do in order to evaluate in sampling representation if the element in the field that I want to evaluate the polomial does not belong to the sampling set then I need to to use lranch interpolation in order in order to construct the polomial. Um and constructing the polomial we with with lrange interpolation we said it would take me n² and after I construct it then I I evaluate the the resulting polomial I evaluate it in a it would take me o of n. So all in all this is this is order of magnitude is n square operations.

Um but if I want to let's say add I have two polomials f and g and let's suppose that in their sampling representation um they have the same xcoordinate. So f in the sampling representation is x1 y1 up to xn yn and g in the sampling representation is x1 z1 up to xn zn. Then if you want the sampling representation of f + g then you can simply do x1 y1 + z1 xn z yn + z n. And I claim that this is going to be the sampling representation of f plus g because when you substitute in f plus in f plus g, you substitute x i. This is the same as saying f of x i plus g of x i.

And assuming that e um we had sampling representation then f of x i is y i and g of x i is z i and so I get that f + g evaluated at x i is y i plus z i. So so this this thing in yellow is the sampling representation of f and g f plus g. So you see I did it in O of N. This is O of N and multiplication. I do the same but I need to I need to make sure that the degree of F and the degree of G are small enough so that F * G is not going to exceed degree N.

So um if f and g are of degree less than n /2 then given the the same sampling representation of f and g I can do the same trick I do x1 y1 * z1 1 up to x n y n * z n. And this is a a the sampling representation. This is going to correspond to the the sampling representation of f * g. Because when you do f * g and you evaluate it on x i what you get is f of x i * g of x i which is y i * z i. Okay.

So the multiplication here I did in O of N assuming that the xcoordinate of the sampling representations of f and g are the same. Okay. So now I have this this kind of weird a um a tradeoff um that if I do in vector or in sampling representation I have add a valal or yeah let's say add eval and multiply I then the complexity in each of these things as vector this is O of N evaluation also takes me O of N but multiplication takes me O of N² in sampling adding and multiplying takes me O of N but evaluation in the worst case I mean if I need to evaluate outside the sampling said this is all of n² and so what what do I want? I want a way to move from vector to sampling representation and back. This a the way to move it is called the discrete fiery transform.

And I want to move from sampling to vector or or vector to sampling representation in less than than n². And if I can do it then all my operations I will never need to to to waste n square complexity on my operation because if I want to I can just move to the the representation that takes um in which this operation takes o of n moving to this representation takes me less than than n² then I you know I'm I'm in business. So that's a so so the algorithm FFT um algo to um calculate DFT this transformation in in fact O of N log N Okay. So, that's that's the purpose of what what we're trying to do. Um, questions so far.

Yes. F0 is the constant. Yes. Um, okay. So, h how do I if FFT is an algorithm.

It is an algorithm that is called a a divide and conquer. And divide and conquer algorithms they they have three stages. Divide, conquer, and combine. Okay. So how do I um how do I e do the division the division here?

So let's say e I'm going to explain now how to move from vector representation to a a sampling representation um and and we'll do the other direction later on. So um say from vector to sampling I start with a with a polomial f um of degree less than n but it is given in vector representation. So I I will write it like this f vector and this is f0 f_sub_1 up to fn minus one and I need to do the divide. of divide I take the the even co the even coefficients. So I write f even vector.

This is all all the guy all the guys in even places. F0 f_sub_2 up to mf n minus 2. So here I I forgot to say this is a um I'm going to describe a divide and conquer algorithm and in divide and conquer we always we divide the things into two and then we divide it again kind of recursively. So it is useful that the size of the input that we start with would would be a power of two. So um n I assume that n is a power of two.

It's not a big it's not a big deal because if you if you have polomials that are of degree not a power of two you can pad their coefficients I mean their vector representation with zero until they become vectors um of size a power of two and since we we take um we do calculations in FP and we do it e when the degree is is a power of two. I need to assume that p is not equal to two. Okay. So these these these are two assumptions. The the first assumption is not strict.

I mean I could have done it with n that is not a power of two but I cannot have p equals to two. But that's okay. We anyway we pick usually primes that are very very large. They are not there are not two. So um at the divide stage I divide f the vector f into the even the even guys and the odd guys.

So this is f_sub_1 f_sub_3 up to f n minus one right n minus one is is odd because n is even and I observe Yes, I amum I observe. So the these guys they live in f um less than n /2. These are vectors of size n over less than n /2. Oh, in fact exa sorry exactly n /2 and as a result each of them corresponds to a polomial. What is the polomial that fe corresponds to?

That's it's a bit tricky because um FE as a polomial now I have only n /2 coefficients. So the polomial it would correspond to is a polomial of degree n /2 and it would look like um sum f of 2 i x to the i = 0 up to n / 2 minus one. Okay, this is if you translate from vector from such a vector into a polomial then you know you multiply you have this free coefficient you multiply the first coefficient with x1 x to the 1. So this is f_sub_2 * x to the 1 and and so on. So in general you have f_sub_2 to the i x to the i.

And similarly if you do the um translation of fo Then you get um f 2 to the i + 1. Yeah. + 1 uh x to the i goes from zero up to n / 2 - one. This is these two things are polomials of degree less than n /2 in the variable x. And um so this is this is the divide this is the divide part.

conquer. Um well, what do I need to do? So, I need in order to to go through um a the sampling representation, I need to evaluate f on the the sampling set X. Um so instead of evaluating on the set x namely to get fx1 up to fxn. These are the the y1 up to yn.

I will evaluate fo and fo on x². X square is the set is the sampling set where you square all all of the elements and but this this needs to be continued right because I will need to do some recursive So to be continued. Um if but if I if I am able to evaluate the polomial f x and fo x on the set x² then what I can do in the combined stage? I can do a um I observe that f of x is in fact f even of x² plus x fo of x² and this I leave you as an exercise it's a very easy exercise calculation in particular for every I f of x i is equal to f e of x i² plus x i fo of x i². So you see using this formula in yellow if I want to get f of x i because I want the sampling representation of of f um it it is it is equal I can equally well just do a fee evaluated on x i² and fo evaluated on x on x i square as well and then I sum I you know I do the the h the formula here on the on the right and I know that I get f of x i.

So if I was able to do the conquer stage to evaluate f of e and f of o on this set this strange set x² all the squares of the the original sampling set then I'm in business. I can I can calculate f of x i. Okay. So how does the so let's expand on the conquer the conquer stage. What I do I said I I do recursive steps right.

So I start with my polomial f I divided into fe and fo. These are two polomials. If you want I can I would put x but I I think I think it's nicer like this. And fe I also divide into fe and f and f odd of this of fe of this big fee. And I I keep going until I reach the last stage of division into FE and FO.

What is this last stage? This last stage is when the degree of FE and FO are uh one. So here the degree of F is N. Here the degree of F and FO is N / two. And here in the last stage of my conquering um adventure I I I get fe and foss that are of degree one.

Now how many stages do I have? I have a um this the the height of this of this tree is log of n is d equals log of n right because n is uh 2 to the d. Okay. So I have these stages. Now what happens?

So at the at at the last state this is the um this is step n number here above it is step number d minus one. What do I have in step number? So okay so how many polomials of degree one do I have in step number D? I have n polomials. So in step D um we have n polomials and degree 1 polomials and we need to evaluate in step E to evaluate these polomials on a a set X M 2 to the D which is Xn, right?

every every level every step that I go in in in the recussion tree I need the the conquering the conquering method is telling me that I need to evaluate the fee and the foss that I get on the sampling set square so each time I I do square this is I have d uh dep so it's x to the n So now if the size of x to the n is approximate is is of the the the order of magnitude of n. Then simply the complexity step D will take well I need to evaluate n degree 1 polomials on a set of size n this is n² so I I'm not gaining anything from this I mean we we are in this business because we want a way to move from from vector to sampling representation in less than n². Otherwise all the operations we care about we we can only do them in in n square times. Um but on the other hand was there any question I heard some uh is this clear? I I feel that I might have okay in the conquer step if we have already split them into even and and odd in level one how can we split them further into even and odd?

Well because you take fe the the splitting is happening on the vector level. So you always you take the polomial you convert it into a vector and you take the even and odd coordinates of the vector. So if you know I I took FE now I have the FE vector and now this is the this is the odd coordinate and this is the even coordinate. Okay. So I can split it into even and odd coordinates and get a polomials f even and f odd according to this split.

Is this clear? Um Ashton?

Yeah. So, so the even and odd as in even odd indices, right? Not just even odd.

Exactly. Exactly. The even and odd is is referring to the indices in the vector representation. This is why I I want to distinguish between the polomial and the vector. Got it.

Thank you. Sorry.

No, I just said thank you.

Okay. Yeah. So, so look we we are kind of stuck because I mean assuming that the the set of the sampling set even if I raise it to square and so on is not getting smaller then simply the simply the the last step of my my I mean my algorithm of my conquering stage would already take me n square so I mean it's not worth it however If um we find x such that x to the 2 to the k for any k between uh one and d x to the 2 to the k is is kind of a shrinking set. That is the number of elements of x to the 2 to the k is going to be n over 2 to the k really shrinking. If you ra you it's like you have a set x you raise it to to you raise all the elements in it by two take the square of all the elements in it and you get a set of of size n / two.

Okay, it's a a very special property. It's kind of shrinking. Then I claim that now we're in business because in step D what we have we need to evaluate. We need to evaluate n polomials degree one. It's just degree one polomial.

So you just plug in the the value x on a set of size x to the n. It has size n / n which is one. So only on one element. So this is complexity O of N in step D minus one. If if I go I go up the recussion uh tree.

So what happens in step D minus one I have um instead of n polomials I have um n /2 n /2 polomials. So here it was n maybe in yellow here it was n pol polomials here I have n / two polomials they are also degree one because if you look at it once I if you you take one of them let's say f um I will call it here f okay it's like or fbar but fbar is equal. F bar is equal to F bar of X is equal to FE of X² plus X of FO of X². And assuming that you already did step D, you have these values F of X², FO of X² for any X in the sampling set. So, so to calculate fbar is I mean fbar is also just a linear a degree one polomial if you express it with the previous data of calculation that you obtained from step d okay just x times some some coefficient plus some free coefficient f of and so in step d minus one need to evaluate n /2 degree 1 polomials on a set x to the n to the 2 d minus one which is a a um a set of size by assumption n over um two to the d minus one and this is this is equal to two.

So I have n / two degree 1 polomials I need to evaluate it on a set of of size two. Okay, that complexity is O of N. of n / 2 * 2 o of n and so and so on. So for any step I will have complexity O of N here I don't know where to write it O of N here O of N here and and so on and so once I once I climb back the recursive tree in order to calculate F with all the previous information F will be just a a degree 1 polomial with a um expressed with the coefficient um F and FO and so it will take me also a a O of N to to calculate to evaluate F on all the H sampling set since the the size this the height of the tree is is log N. I get complexity overall complexity O of N log N.

Okay. So now the big question is how to find the the set X and I claim or before before I do that any questions on this uh like assuming so so what I make what I did here is assuming that we have a set X with this shrinking property then I can find an algorithm in N log N to evaluate to do from go from vector to sampling representation. Yes, exactly. The splitting. So the way the algorithm works is you split, you split in the vector representation and then you split again, you split again until you get to the bottom.

And when you get to the bottom, you start to evaluate. And once you evaluate, you go up, you go up the tree. Okay. Until you can evaluate f um f on the original sampling set x. Erh.

Any other questions? This is kind of a a a I mean we're we're doing a fast track of it. But I claim we you know such an x. take x to be the set of n roots of unity over the prime field fp. Um we know that this is this is a cyclic group.

So this this is you take some primitive root of unity and you can write this set of roots as um w0 which is one w up to w to the n minus one. Okay this is the set this is the set of n roots of it's not exactly in fp. So my I I need to I need to go to a big enough extension in order to have this sampling set that h that that has the the shrinking property I'm looking for. But why would it have the shrinking property? Look at x square.

X² is W 0² which is 1 W1 squar. So this is W square up to um let's put it this way. up to a a w to the n minus 2 and then I have w to the n but w to the n because w is a a root of unity w to the n is one and then I have w to the n + 2 but w to the n +2 is just w to the n * W ^ square and W to the N is 1. So this is W ^² and I repeat until W 2 NUS 2. But W 2NUS 2 is going to be equal to W to the NUS 2.

So you see what what what happened in so x square is is just I I might as well stop writing a at this point because I I just repeat myself. So I can write it as as w to the 0 w² up to w to the n minus 2. Okay. This is a set of size n /2. Moreover, I take any guy in this set x², let's say w to the 2 k and I raise it to the power of n /2, what do I get?

I get w to the um k * n which is the same as w to the n to the to the k which which is one because w to the n was originally one. So in fact what I got here x² x² is the the set of n / two roots of unity. It's a it's a beautiful uh it's a beautiful phenomena. It's like I I I found a set. This set is so special that once I I raise it to the power of two, I get um I get the the the set the roots the n /2 roots of unity.

Okay. So, so now I basically I I finished I finished the algorithm because I have the the set with the shrinking property that I want and um and uh it's I mean I I described the algorithm to do it in n login.

Nice.

Now, yes, now we we're not I'm sorry. I uh I I want to continue if maybe a few more minutes, maybe 10 more minutes to describe because there is a question of how do I turn from a um sampling representation into vector representation? How do I do that in in n log n? What do I need to invent a new algorithm? So the answer is that I I don't need a new algorithm.

I just write my algorithm in a a matrix form. Um um converse direction maybe um from sampling to vector So here I first observe that if you give me the vector representation and you give me this um uh root of unity primitive root of unity w then I can write um let me write it like one one and here it's going to be w uh w² up to w n minus one and at the bottom of the thing I have w to the n minus one w to the 2 n - one up to w to the n -1² okay this is a matrix h it's it's called well if I multiply this matrix I mean these are if you wish What you have here is um this is x1 sorry here you have x1 x1² up to x1 to the n minus one and here you have x2 Sorry, we have ah the ah yes. So this is a apologies. So this is um x1 0 up x1 1 n -1 okay x2 0 x2 1 x2 n -1 and and so on. And if you multiply it by f0 up to fn minus one, you do the matrix vert vector calculation, you will find out that you you will get a vector that is f of x1 f of x2 up to f of x n.

And that's the same as a y1 up to yn. Okay. So in fact the e the the the the passage from a um vector to sampling representation can be done by matrix ve vector calculation. Of course mat this is an n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n byn matrix and um to do a n byn matrix times a vector in a naive way would take you n square operations. Um this this matrix is called the Vandermon matrix of the sampling set X.

The sampling set X is just all the powers of W. So this is W0 W up to W N minus one. Okay. And what we described is a way to um so this let me write this guy as f vector transpose and this guy as y vector transpose. And what we described I mean we simply the the the passage from vector to to sampling is this matrix operation vx * f_t and then you you calculate you get the yt and vx this is sometimes actually um h in this case that you choose a w this is called vw W sometimes.

So VW let me write it here. And we described an algorithm to calculate this guy in O of N log N for any W any W that is a primitive root of unity. N primitive nth root of unity and any vector F. We described an n log n algorithm to calculate the the multiplication. Now there is a proposition that says that um the inverse of the matrix W of the matrix V is simply 1 / N with a a the Vandermon matrix of W to the uh to the minus one.

And I I will not prove it but it's it's a it's a very basic calculation. So what you get is that I mean just now transform this green equation into the yellow equation looking this way. H f_t is equal to v -1 w y t and this is the same as saying f the vector f transpose is equal to v um to 1 / n vus one I and we have an algorithm to compute this guy in O of N log N because we just described a how to how to compute a a a Vandermon matrix with respect to a primitive root of unity times a vector in n log N operations. So I can color. So if you give me the sampling representation namely you give me w and you give me y then I take w minus one.

It's it's also a primitive root of unity and I calculate in n just the same algorithm I calculate and I get to the the vector representation f. So we have a exactly what we wanted. Erh, I hope I hope that this this was useful. Um, but I I'm happy to take any questions and requests. Um, for the next time what I want to start talking about is elliptic curves, but I am open to to other other requests.

Other questions? I mean, I I know I did it fast, so um so clearly there must be some questions. Yeah,

it's been a lot. I'm sure there might be some. Let's give it a few more minutes maybe for people to to come up with something. Um and we can we can conclude it after anyone has any thoughts feel free to raise your hand or if you just have any comments. Yes.

Yeah. I have a question with uh uh calculation for the overall complexity of the FFT and uh you write like uh uh over uh two * 2 and uh uh can you explain that part?

Yeah. Here.

Yeah. Yeah. Um so why so I I go to step a let's start with step d I have I have n polomials f and foss I you know I I call them by abuse of notation fee and fo but you know if you write it nicely you should uh distinguish the fee and foss in each level and each branch but I have in step d I have n such guys right and I needed to evaluate it on a set I mean to evaluate each of them each of them f this let's say this f here is some polomial fe x is like a a + bx okay it's a polomial of degree 1 and now I need to evaluate it on a set of sides one only on x1. So this this takes me um I mean to to do to evaluate a polomial like this takes me two operations right or actually three because I have x1 a I need to multiply it by b and then to to add to the result I need to add a. So this is three operations and I have n h polomials like this.

So this is three three n operations. This is O of N. This so far you you understand the the complexity. Why is there a three operations? I think there is like one time and one multiplication and one addition, right?

It's two, right? Oh, it's like individually it's one for a No, you're right. You you're right. This is two operations. Yes.

Sorry.

Two operations. I need to I need to multiply and then add to to the result I need to add the so so the overall complexity in step D is 2 to the N and that's we call it complexity N now I go with the information that I gathered from step D I go to step D minus one step D minus one I have this guy F let's call it F okay it's kind of abuse of notation. It's not the original f but it's like the in kind of a local view. This is the f we care about and the f we care about it satisfy this formula. This formula star here f of x is equal to f of e and this is with these f of e f and fo here they satisfy the formula h f of x equals f f of x² plus x * fo of x² in particular now you have a sampling set here you have a sampling set h in fact um x to the the d minus one is going to be a sampling set of size two x1 and x2 okay right because we had a in step d we had a sampling set of size one now we go up a step we have a sampling set of double the size so I I write it x1 and x2 again it's kind of abused because x1 and x2 to appear somewhere else.

Um, and so if I I take this this equation here and I substitute. So now I need to evaluate this f on this these guys x1 and x2, right? But of course this one this x x1 squared is equal to x2 squared is equal to the x that appear in or is equal to x I don't know zero that appear in the in the stepd sampling set. So in order to evaluate f on on this x1 and x2 I by this formula I can eval it's it's enough to do a f x1 squared fo of x1 square but this I calculated in the previous in step d right

yeah yes

you follow and then what I need is like is I I need to do a basically again two operations. I mean I have this I have from the previous step. This I have to from the previous step and I need to do x1 * this plus the the f uh the fee of x1². Okay. So this is again this is two a um it's basically a um a a one operations I mean it's two operations it does not depend on n so so I have right I have a um but but this is only to evaluate x1 how many x's do I have in my sampling set in step d minus one I have two x's in my sampling set.

So this is this is the reason for these two for these two right I have n /2 oper n /2 polomials of degree one like this and each of them I need to evaluate um on two points x1 and x2 and evaluation of a polomial of degree one on a point is is all of one right but I have two points these two points they they you know when I go up the stages to d minus 2 and d and and so on. This this will grow. This this this is depending on n. Okay. But it's a

I say I say that I say that now. Okay.

Yes. Yes. Yes. Because you need to evaluate like fx1 and fx2. Actually that's the thing that both part you will need.

Yes. Okay. So you see so what I end up is that in every stage I have complexity n o of n and and uh and then the the overall is of n login.

Okay. Okay. Okay. Thanks a lot.

Okay. Any other questions before uh we finish? All right. So I hope to see as many as you of you in the next time we will start talking about elliptic curves. Heading towards the BLS signatures which is a famous uh uh protocol for cryptographic signatures used in uh in blockchains all over the places.

Yes, the security of console slayer basically. That's amazing. Finally getting to the the ECC. Thank you so much Matan and uh for everyone I just want to remind uh we'll have recording uh up probably tomorrow but also uh tomorrow we have another session on the ZK and link consensus and then another one on Wednesday so this week we have two more sessions don't miss them and thank you so much for making it all the way till the end we are at two hours 15 minutes here so it's really great thank you so much matan