PSE Lectures Ep 36 - Efficiently computable definition of Weil pairing

Transcript

so um today I want to talk about mostly about Miller algorithm I'm not sure we will finish in this session but um at most in the next next one I think um but ER to to set the stage H there is one more thing that we we need to discuss and the issue is that um you remember in in

ER for two end torsion points we defined n of of PQ to be um GQ of p+ s divided by GQ of s where s is some um some some point on the curve and it turns out that it does not depend on the choice of

s but but the the function GQ is defined by by a divisor relation ER let me just recall this and yeah so this the divisor of GQ needs to be uh the sum of um over all end torsion points

R of um bracket Q Prime + r minus bracket R where Q Prime is an n n Square torsion Point such that n q Prime is Q um but this this is not so easily computable and um in fact there is something else that appears in the construction of the well

pairing that is easily computable um um so yeah so so so that's that's not easily computable um but we can um compute um

FP a rational function on E such that the divisor of FP is um is n bracket P minus n bracket o now okay um the statement you should not ER be convinced by by just ER by just me saying it we will see ER soon enough this will be the Miller algorithm but let's say intuitively you can imagine that it's much more

feasible to try to compute FP than to compute G GQ okay so we want a definition of of the well pairing that involves a a FP instead of GQ so we want a definition that so it should be easier to compute FP and we want a

definition that um involves FP and not fq and not GQ so so what do we do um what happens is that there are several equivalent definitions of the well pairing um and this appears in the section H equivalence of definitions of of well pairing is 6.12 in the notes um

and in fact I mean we we will not we will not have time to show that the um the definitions I give are indeed equivalent to the the the original definition we saw of the well pairing um but I can I can tell you what is the the main ingredient so um basically so for a divisor D which is some sum

NP p p runs over all points um its support is um support of D it's it's a subset of the set of points on the curve and it is defined to be the set of points P such that NP is non zero in other words it's the set of

zeros of of um well yeah the set of zeros of of D Union the set of poles of d right because uh anything else is not uh so this this zero and polls really mean I mean zero are points for which the the coefficient is positive and poles are are um points for which the coefficient is is negative and um I can also do this for a rational function so for for r a rational

function um its support is um support of R is the set is again it's it's a subset of the set of all points on the curve and it's it's the set of zeros it's the set of zeros um of R Union the set of Poes of R and and now

um suppose um D is a divisor on E and R is a rational function on e um such that the support of of D is disjoined from the support of R and then we can evaluate r at

D and the way to do it so let's say d is um this finite well the sum NP bracket P it D does not need to be a principal divisor it can be an any divisor that has support that is disjoined from the support of R so the set of zeros and the set of poles the set of zeros and poles of D um does not intersect at all with the set of zeros and poles of R and and then we can do if if I want to evaluate r at a divisor D I do

a product of R evaluated at P to the power of NP where P runs over all points and you see this is a finite product because um in D there are only finitely many points p that um for which NP is non zero and R um cannot get cannot become zero or um or Infinity for any of the

points um for any of the points in the support of P so um whenever so so this term is always defined we can say that R of P whenever p is um is not in the support of D it means that NP is zero and we know that RP is is finite and non zero so I can always say that something finite and non zero to the power of zero is one and therefore this sum is a I mean sorry this product is is always well

defined ER any questions about this uh evaluation uh is this clear is this um I think this is for me the definition of D is clear but I'm just a bit confused why you wrote a little bit before support of d uh intersection with support of r r is a rational function is not divisor so what do you mean by support of R here is not clear to me yes so so this

is sorry I should have said the support of D intersection support of R is is the empty set ah okay okay so this is a this joint support ah sorry so you define the support of R just below before okay no so makes sense okay I mean the support of R and the support of D is is defined using the same principle it's like the set of zeros and the set of poles okay I mean for a divisor we don't formally say that a point is a zero or a pole right because it's not like this divisor is not necessarily a principle

divisor but we can we can just extend the definition by saying that for a divis d any point that has a nonzero coefficient right this H any point P for which NP is non zero is well is either a zero or a pole if NP is a is positive we can say that that P is a zero of D and if NP is negative we can say that P is a is a pole of D okay Nicholas

y ER are now what do you think you are are you okay with this definition I think so yes thank you yeah so so you see alternatively this um if you don't want the the complication of like running over potentially infinitely many ER points we could say that Rd is the the product over all RP to the NP

where p is in the support of D okay so this ER by definition we I mean I I simply Define the the sum in in Orange sorry the product in Orange to be um to be the product in h purple okay so you and and the product in purple is always defined because of the condition that the the two ER the two things have a disjoint

support because otherwise if I don't have this condition it could be that that P is is a zero of R um I mean but it's a but if it's a zero of R so if p is in the support of D so it has some some let's say a positive coefficient um and and then I and then it could be generally that P is a zero of R if p is a zero of R then R of p is zero and I don't know how to evaluate R of p i mean zero to the the uh to some

um positive exponent and and also if P happens to be a pole of a um of R then H you know R of p is is infinity so R of P to the NP would not be a finite element in the field but in in this definition under the the green condition I can always assume I I mean I always get that R of D is an element in K it's not infinity and it's not zero in fact so it's it's an element in K that is not zero

and and using this evaluation well first I guess I I should say um this is the the main component to show um that the the two I mean the that um the definition that I will soon sketch or write is is equivalent to the original definition is is called The Well reciprocity um and this says um let R and

s well is um e over K be antic curve with a a k algebraically closed let RNs be rational functions and such that the support of R is disjoined from the support of s

then if I take R and evaluate it on the divisor of s i get the same thing as s evaluated on the divisor of r and this result it's it's a very nice symmetric property of a of elliptic curves I guess um R ands need to be nonzero rational functions and er you could I mean we we

unfortunately we do not have time to to cover ER the proof of well reciprocity but you can look in the notes there is a proof for well reciprocity um over the projective line and it's it's not a big deal to um translate the proof of the over the projective line to a general curve so this is in fact a property of um rational functions on any algebraic curve ER and um we will skip the proof of well

reciprocity and and get right to the the um the the other definition of the well pairing um and this goes as follows so um suppose m d is a degree a degree zero

divisor such that um ND is principle so for example you can take a an intorsion Point P and D to be P minus o the the the divisor D is not principal because

um Can can anybody say why why D is not a principal divisor so this is anybody remembers what what is a principal divisor so the degree and the sum should be zero yeah but um for this divisor D um what is the degree of d zero zero what is the sum of d b p so D cannot be principal right P

let's say p is non zero I should say p is not is not the zero point then D is not a zero is not a principal divisor but um so d ER not a principal divisor but ND is NP minus n o and this is this is a principal divisor right you see y are

now yes because now both are zero like the some the degree it's because I I yeah because I took P to be an in torsion point so and so then this this thing is going to be NP minus n o and NP is is assumed to be zero Co okay um so I take some a divisor of degree zero that such that ND is principal by the way we also write that ND is equivalent to zero

yes uh what do I mean here by equivalent so we can when we talked about divisors we defined an equivalence relation by saying that two divisors are equivalent if their difference is um is principal all right okay so to say that something is equivalent to the zero divisor is to say that well this something minus the zero divisor is principal which is just saying that this this divis or his principal okay yeah thank you um so I suppose D is is such a

divisor for which ND is um is principle um and let FD be ammonic rational function such that the divisor the divisor of FD is D is sorry is ND um monic here I would just say it

means that um the the leading coefficient leading coefficient of FD is one we had a we had some proposition saying that uh you don't have to remember what is the leading coefficient it's it's a bit of [Music] a irrelevant detail but we we had a proposition saying that uh um I mean a function um a function that is that has a um function that has a divisor some prescribed divisor is

completely determined by the leading coefficient so if I choose the leading coefficient to be one and I say that FD has to have a divisor um n d then FD is completely determined there's no um no ambiguity and and and now I can do the the construction I guess um so for p and Q and torsion points

um choose divisors DP and DQ and searched it one the support of DP is disjointed from the support of DQ and two um

DP is equivalent to P minus o DQ is equivalent to Q minus o and uh and actually it follows if I can if I can find such a divisor DP and DQ it would follow immediately that n DP is equivalent to zero and and

ndq is equivalent to zero as well H can anybody see why the the orange implication is true I'm not following this part was because p and Q are part of so yeah exactly so to see why the orange implication holds um I mean suppose I have a a a divisors DP and DQ each of them is equivalent to

well DP is equivalent to P minus o what does it mean it mean that DP minus P minus o is principal it's equivalent to zero hence principle but um I mean if H if DP is a I mean DP minus P minus o is princip

I take n DP um so I can I can H I can kind of multiply everything here by n so so and this will will remain an equivalence I mean I do n NDP minus NP minus n o is going to be equivalent to n0 but n0 is zero so it it means that um

NDP is equivalent to NP minus n o and um NP minus n o because p is an endion point this is a principal divisor and the same goes for n for DQ is this better now yes yes I than you okay so this is like a just a uh you can you can think of it as a as a

formal issue but there is a subtlety I mean why cannot I choose um DP to be equal to P minus o and DQ to be equal to Q minus o I mean this surely if if I choose DP to be P minus o it it's it has to be equivalent to to P minus o and H DQ I can do the same so why do I I I need um I mean why can't I choose DP and DQ to be this in this simple form I think I'm I'm confused can you

repeat again what you want to know what you can do yeah I mean I want in this this the beginning of this construction is like um it says choose divisors DP and DQ that satisfy these two conditions so to satisfy the second condition I can simply choose DP DP to be P minus o but then this is not principle right it I didn't say the DP is principal um only n DP is needs to be principal which is what you showed in the previous

section yeah but why can't I choose really DP H to be equal to P minus o and DQ to be equal to Q minus o this surely it satisfied the second condition because any two divisors that are equal are necessarily equivalent okay oh the issue er do you have an idea Nicholas uh sorry I I still don't quite get what is the question exactly I DP and DQ can I choose I I mean this in

this construction um uh we say we take some two endion points p and Q and we want we say that we choose divisors DP and DQ that needs to satisfy these h two conditions now the question is can I choose DP and DQ to be simply P minus o and Q minus o this will be the the ideal scenario right uh because the you I don't think we can because the zeros are the same right exactly the support is not disjoint okay you you see this or

now what is the support of DP I think I'm missing this so support of DP is a set of two points it's p and O okay okay and this support of of DQ is q and all so they have a common they have a common element in the support which is O and that's not that so this is no no good because it would not satisfy condition number one okay so this choosing choosing a

pair of divisors um like this is a is a bit tricky but I will soon show you how you can do it and um we Define ER let me call it um a generic or general while pairing is en

n generic of p and Q is you take ah oh I didn't um sorry I'm missing something so um let fdp be ammonic um rational function such that

the divisor of f DP is n DP ER can you see can you see why there is such a function a fdp but didn't we look at uh we looked at this some time ago so I don't remember clearly but we looked at how to construct a function which has a specific devis no no we didn't how do we

still didn't didn't show a way to explicitly construct fdp but I'm I'm asking why does fdp how do I know that such fdp exist I mean it's not true that every divisor comes from a rational function yeah but NDP is principal so it comes from rational function no okay it's because NDP is principal it's equivalent to a principal divisor it means that it's principle and similarly fdq such that the divisor of fdq is n DQ

uh now Elisa do you follow yeah it's fine so I have a question so in the in the previous part right before the in the orange part is it correct that the so so you say that that since they support is this joint we cannot use um DP equals uh P minus r the formal substraction of them but we can use instead of equal we can use equivalence and then the disjoint

support is zero again so what I can do um write another color um I can take DP for example I will soon get into to like explicit details but let's say I take DP to be um p + r minus r for a a carefully chosen r then I claim that this

DP is equivalent to P minus o but now it it can I mean if I choose R carefully it can be it can have a disjoint support than um than DQ let's say I I I take DQ to be q q minus o okay okay okay and and DP I take p + r minus r why is p + r minus r equivalent to P minus o it's because um

let let's say d DP DQ is is Q minus o and D p is p + r minus r and then um DP minus P minus o is by definition it's a p + r - R minus

p plus o right yeah um or let me just write it a bit bit more formal so this um and this thing is a principal divisor because the the the degree is is zero right I have like 1 minus one minus one and one and if you sum all the points you get also zero right y nice okay so so you see

what I did here in in order to to satisfy both conditions I um I can I can take one of the DP and DQ to be this either p p minus o or Q minus o but the the other one the DP or the DQ I need to to shift by something and well I I still didn't finish the definition now you will see I guess the full picture um we Define the um in

general wh pairing of a p and Q as en n generic of p and Q is f DP evaluated at DQ divided by fdq evaluated at DP okay where this this thing I remind

you um fdp what when you you have a rational function and you want to evaluate it in a divisor let's say DQ if if DQ is Q minus O then I I assume that fdq is um a um Russ sorry so this is f fdp I assume fdp is a rational

function whose divisor is is is NDP so it's the support of fdp is disjoined from the support of of DQ this is because the the by assumption the support of DP is disjointed from the support of DQ and the support of of fdp is the same as the support of U of DP so this is is then going to be F DP evaluated at Q times F DP evaluated at o to the minus one

okay uh any question about this definition this this is like a it's a bit abstract but um I think it's very useful to haveen we will soon um get into more concrete choices and I will show you how to how to choose this DP and DQ um easily but I think it's useful to to Really phrase it in the in the most General way because it has a it has a nice symmetry to it and you don't see the Symmetry if

you um if you if you go to the the concrete definitions is this a statement the last line you wrote Because I don't quite why how you came up with this why is it time fdp of Z the inverse of it where does this because what does it mean to fdp is a rational function and DQ is a divisor right and let's suppose that DQ is Q minus o equal to Q minus o okay so I'm just like repeating what does it mean to take a rational function

and evaluate it on on a divisor this is your definition this is just like we going to say that evaluating rational function on divisor is this way I mean the the general definition is um if D is sum NP bracket P then then and R is some rational function then R evaluated at D is R of P well it's the product R of P to the NP where P runs over the support of

d h so the minus one comes from here the NP because it's zero so it's minus Z so it's one okay that's what I do okay thanks do you see this are now you see why the green ER the green thing is h i mean yes thanks for the clarification on the like what you just said because I was also missing the minus one yeah yeah so this this is exactly how it goes but but the the the generic definition of the whale pairing as as here in the The Orange Box it it is very convenient for a um kind

of theoretical manipulation because it it's symmetric and um I guess after the break we we will H we will make a a few choices of a DP and DQ and then we we will be able to apply the the Miller algorithm the Miller algorithm will calculate I mean if you think of it fdp let's say if if DQ is is Q minus O then fdq needs to be a function such that the

divisor of fdq is n DQ and let's put it here the divisor of fdq needs to be n DQ and for this choice of DQ it's going to be NQ minus n o and this is what I said in the beginning of this session that a functions like this we can I mean we can compute with the Miller algorithm so

um I mean I guess it's it's a bit more it could be a bit more clear now that using this a a a generic definition of um The Well pairing you you have we have a better shot of calculating it now one thing I want to say before the break how um how is it going to be I mean how how do people prove that the generic well pairing is equivalent to the the well pairing definition that we saw in the the previous sessions we use well

reciprocity because here I can I mean I can instead instead of fdp evaluated the DQ I mean I have a function ER well okay so let me not spare the details but uh but basically um let's say e theum and for any PN q n PQ is equal to n generic p and

Q and the proof is is an application of we reciprocity okay uh so let's uh let's take a break and come back to the midd Alor

e e e

e e e

e e e

e e e

e e e

e e e

e e e okay uh

so before I go to the Miller algorithm I think it's it's um it's nice to know a bit of the the story around it ER ENT um essentially Miller Miller was able to come up with an algorithm to to compute FP evaluated at Q let's say for

um FP that has a divisor NP minus n o and he he sent it to to a lot of journals he thought that it's an interesting I mean he he can comput it in a in an efficient way ER basically and ER log I think log n um log n of um additions of points on the elliptic curve and each addition of the point of the elliptic curve is not too complicated So So eventually it's a it runs in polinomial

time and he sent it to many journals and got rejected and the the rejection reason was that there is no application So eventually the the paper was published in 2004 ER where it took him like six or seven years ER to to get it published and and now with with zero knowledge snarks and and the rest of it pairing based cryptography Miller algorithm is the most Central computational tool I mean the only way basically that we know how to

compute pairings efficiently is is using the Miller algorithm so it's a it's kind of a a nice well I mean important important thing to know when when people tell you that something has no application it it can be a just overlooked and uh and I think the the cryptography Community is now more aware of a such phenomena and and more open to to new things that do not have immediate

application yeah I have anation question can you explain when we write FP and when me write fdp yes so so fdp so fdp is is a function such that the divisor of fdp is n DP and DP needs to be a divisor that is equivalent to P minus O So NDP is going to be equivalent to NP minus n o but only equivalent means that if you subtract

the two divisors you get a a principal divisor you get you I mean right okay so fdp is a bit more General but but for DP that is equal to P minus o fdp is is exactly is exactly FP okay okay now um what we're going to do is is a is a geometric construction so

um uh geometric construction and we we go back to lines so suppose I have two points u and v on the curve the line between u and v um is is a rational

function such that the divisor of L UV is a u + V M plus minus U + V well sorry I need some more space and the divisor of u v

is U plus V plus minus U + V minus 30 um so um here I assume that h u is not equal to V and H both u and v are not the zero point and then the divisor of I mean

luuv it's like the line of the I mean the line that passes through a u and v so if if this is U and this is V then H somewhere here is going to be minus U + V because U + V is taking the intersection and reflecting it this this is U + V so so so this this guy is is minus U plus v and if I take the green

line if u and v are generic I mean they they're not the zero point and they're not equal to each other then what is the divisor of this line well I need to I need to count the number of zeros and the number of poles so how how many zeros does does this line have it has a zero at U it has a zero at V and it has a zero at minus U plus V all of them I mean because it's a line and and the elliptic curve is is a degree three curve um it can only have at most three zeros so all of them have to have degree or multiplicity

one and and then since I know that this is a a rational function I know that the there has to be a polar of Multiplicity three and this this poll has to be has to be the the point at Infinity right I mean that's that's kind of the the consideration that we we did in a while ago um now for for the case that U is is not equal to V V but V is equal to

zero H this the divisor of LV is going to be um U Plus minus U wait [Music] um I guess for U equal to

V sorry yeah so for U not equal to V not equal to V but V is equal to zero what I get is the divisor of luuv is a

u plus o h plus erus u + 0 is is minus U minus 3 so this is equal to U plusus U minus 2 okay and then H so this is a h u u not equal to V but V is is equal

to zero and similarly if if H If U is equal to zero then you get the same but with v ER the tangent line um at U is a rational function um t u such that the divisor of

Tu is equal to m 2 U plusus 2 U minus 3 o and the picture here is H is similar let's say I have um I have some U here

then I draw the line um that is tangent to H to U and this line um what happens it it intersects I mean this is 2 U and this is minus 2 U so this line intersects the curve in minus 2 U now because it's a tangent line this we we discussed um U is going to be a a zero of degree 2 this H this can be shown with uniformize

and so on it's a um it's kind of a property of the tangent line and so I I know what are the possible zeros the possible zeros are U and minus 2 U at U I have degree two so it means that at minus 2 U I have to have degree um degree one and then since it's a rational function I know that I have to have a pole of degree degree three and this pole has to be at at o because it cannot be at any other at any other point H is this okay this tangent line

and a a horizontal line I guess can you explain once again what uh like for now uh since the geometri construction I feel like we introduced two lines L and T that's it yes yes and let me introduce the third one I I mean I'm still H in but why is it horizontal it's not horizontal it's like horizontal ER I mean it's not vertical it's not it's

not going to touch the point at Infinity okay okay um yeah I guess horizontal or you can call it something else but let's say nonvertical nonvertical and the vertical line uh so let V be the vertical line um at

u h and let's let's draw the picture again I have you and I take the vertical line at U so here is going to be minus U and there is it's going to intersect the point at Infinity I mean it's going to intersect the curve also at the point at Infinity um so so new this new U um has a

divisor that [Music] has U minus u o um and then minus 30 so I might as well minus 30 so I can just write it is U plus minus U minus 20 yes sorry I think you mentioned it again and we already for it again but where does this minus three come again

so I have to have degree this is a rational function right yeah so the divisor has to have degree zero y if I put I mean I I checked the degree before I just took efficient okay sounds good okay so I have to and and and whatever I put I mean whatever point I put next to the three it has to be um it has to be a pole right yep now the only way to put this vertical line um yeah I mean the only way to get the pole is is at the point at Infinity

yeah I guess here it's that's it's a bit let me just write it like this yeah I guess I gave some euristic explanation but if you calculate um the vertical line you get u +us uus 2 so okay so now

um observe H for U I have a a tu which is the the tangent line at U is the same as the the horizontal line of U and U and if I take the vertical line at U it's the same as taking the horizontal line of U and minus

U okay so this is this is by construction it's like a and and now this Construction for a a p and Q and torsion points in RNs two points on the curve such that s is

not an element of the set r p+ R um p + r minus q and R minus Q consider the divisor and

DP to be h p + r minus r and DQ to be Q + S minus s H the basic claim is that these divisors have disjoint support support of DP intersection support of

DQ is the empty set and this is a routine check but let's let's do it I mean if s does not belong to the um orange set so what are the what are the um I mean the support of DP is p+ R and R and the support of DQ is a q +

S and S now um R cannot be um cannot be equal to S because s does not belong I mean s does not belong to the the orange set so this these two are are different R can also not I mean let's let's do it like this s cannot be equal to R because s does not belong to the set then q+ s cannot be equal to r as well

because um s is not equal to R minus Q so this is this is equivalent to say that Q + S is not equal to R so I have inequality here now s cannot be equivalent to p+ R this is this is basically this this relation and S so s cannot be equivalent to p+ R and uh n s cannot be wait okay we said s cannot be equivalent to r

s cannot be equivalent to p+ r q + S cannot be equivalent to r equal to R and Q Plus s cannot be equal to h p+ r because if Q + S is equal to p + r h this is the same as saying that s is equal to p + r R minus q and we we took by condition that s is not equal to p+ R minus Q okay so it's a that's the end of the

proof is this clear let's say small issue okay so so now I Define um The Well pairing ah and of course H clearly DP is equivalent to P minus o and DQ is equivalent to Q minus o right because uh for example I do the DP case DP is p plus p+ r this we we

basically showed before but let me do it again p + r minus r and I subtract from that h p minus O then I get I get a divisor that has a degree and degree and sum zero so this is principal principal means that it's equivalent to zero uh so so this is the same as saying that H the DP is equivalent to P minus o ER and now I can use the the generic

definition of the whale pairing ah and and of course um we take F DP uh such that the divisor of fdp is NDP and H fdq such that the D of fdq is n DQ

and we know that the the definition of the generic qu pairing is that it is evaluating one rational function by the other divisor and and taking the portion so n of the generic well pairing is f DP evaluated the DQ divided by fdq evaluated at DP but this we can

um I mean fdp um we yes so um so let's let me take ER we took DP and and DQ right so fdp and fdq I I can I know what um what the form is um this is

NDP is equal to n n p + r minus n bracket R so fdp I can take it I take it Monique and er let me call it well okay um fdq needs to be n q +

S minus n s um so let me call it um I I I do a little bit of use of notation I call it FP and I call the fdq I call fq and then the the definition of the generic way pairing I I can simply write it as um I I take fdp or FP and I evaluate it at

DQ but what is DQ DQ is like a p + r minus r so this is p + r divided by FP at R this is the the numerator and all this I divide by fq evaluated at sorry here I apologize for it this is FP evaluated at DQ is FP at Q + S divided by FP at s and here this is fq

at um p+ r divided by um fq at r okay so so this is what we need to calculate and let us describe an iterative procedure

to and to calculate um FP of X for um X in e h um and this this iterative procedure so for for K in Zed I let um FK be monic such that the divisor of FK is

a k p + r minus k r minus KP plus o sorry so FK needs to be a monic function such that the divisor is k p +

r minus KR minus bracket KP plus o so if I take m k equals n then FN is equal to FP right because FN is going to be a function the divisor of FN is going to to be n p r p+

r minus n r and and these two things cancel out because p is an ENT point so so NP is going to be zero uh so so I know that the divisor of FN is equal to the divisor of FP and since both of them are chosen to have leading coefficient one they they must be equal ER is this clear I I understand why the KP disappeared when k equal to

why is the zero disappear because I have a I mean it doesn't disappear it becomes a minus o right ah okay that's right yes makes sense ER AR now you follow Lisa uh I'm kind of following on the technical technicalities but yeah okay let's assume I'm f um I can I can repeat we will not finish the Miller algorithm today so I mean I can repeat I will repeat next

time anyway um but basically you see I'm I'm I'm I'm still in the the reduction ER steps I mean I'm saying I want to calculate FP ER eventually I want to calculate FP evaluated at X if I can do FP evaluated at X then can I mean for any X then I I can choose X to be Q Plus s or I can choose X to be S and if I can do it for FP I can do it for fq right it's a it's completely I mean if I have an algorithm for FP I have one for

fq right yeah so H whatever we were doing before we got this orange formula we were modify um the formula to get the orange formula yeah I mean I was so what we we did before the orange formula is um we we chose um you see we chose DP and DQ ER in such a way that they would fit to the generic definition of the word parent

right that is they they need to they need to have this joint support and they need to satisfy this need to be equivalent to P minus o and and Q minus o right and then we say okay so what is um um the generic well pairing you take fdp such that the divisor of fdp is is n * DP n n * DP is this okay and you take a a a um a rational function fdq whose divisor is this here here should be

brackets right right its divisor needs to be n n times DQ so this is this and and then you you you calculate so um I mean now I call fdp I call FP and fdq I call fq so you see from the orange formula that we need to calculate FP at a basically at a general point right okay so now I'm going to say um I'm going to define a sequence of functions FK such that when when K is equal to N I get

FP and I will show you how to evaluate the the functions FK at a generic point x I will do it iteratively okay and once I do this I I'm finished but first I I want to I mean one of the steps is some relation between the FKS H before I I do that or now are you with us yes okay so so the proposition is the following H for A and B in

Zed if I take the divisor of fa time FB times the line at AP I mean the line between AP and BP divided by the vertical line at a + b p i get the divisor of f A+ B okay it's a very nice uh nice relation

between ER the various FS FKS and um I mean using this the the lines and the well the line and the vertic the horizontal and the vertical lines so let's let's see how it go and the proof is very it's very easy you just unravel I take the the left hand side and I calculate the divisor the divisor of a product of functions is um is the sum of divisors and the divisor of a quotient of function is is is the difference of the

divisors and I know what is the divisor of fa what is the divisor of FB and I also know what is the divisor of the a horizontal and vertical lines so I can calculate I do this is a p+ r minus a r this is the divisor of fa H then from that to that I add a b p+

r minus b r this is FB H then I need to add the divisor of the line between AP and BP the divisor of the horizontal line between AP and BP is AP plus BP um plus

minus a + b p because this is a a p plus plus BP is is a plus BP um yeah but I forgot the O's so here and okay so so the divisor of fa is not exactly what I wrote but rather um minus a plus

o the divisor of of FB I need to substract minus BP and add o and then the divisor of of the the horizontal line between AP and BP um I have minus 30 let me write it here minus 3 ER and and then I need to substract the divisor of the vertical line at the point A Plus

BP and and that is um the is A + B P so let me just write it like this do minus here um plus minus A+ b p and Min - 2 okay and and now I just h i just

collect everything so I collect everything I get a + b p+ r minus a r minus BR r uh minus a + b p um plus o and this is H if you just

rearrange this is a plus b p + r minus a + b r minus a + b p that's all and if you look at it this is exactly the divisor of F A plus b which is the the right hand

side okay so it's a it's a bit of a it's a bookkeeping basically um there is no uh no hard effect to to wonder about ER is the proof okay by left hand side you mean what is on the left in the formula right yeah yeah I mean when I do the I start from the left hand side because that's the the thing I

I need to really um rearrange but do you follow Lisa ER I mean I guess you don't have to follow exactly the the details of the rearrangement of the terms but do you do you see the the main principle that drives it uh I don't know I see a divisor F away I see divisor F of B I know what are the divisors of L and how it is called on the

bottom yeah here I should say the divisor of fa is is this guy and the divisor of FB is this guy and then we have H the divisor of l a BP right and the last one is minus the divisor this is minus the divisor of va a plus p p no everything is f okay yes and then

you just check you you just rearrange the terms and and you get F A plus b ER ah okay so Nicholas had to leave so let's H and unless you have questions ER we should stop here and and next time we will I'm pretty sure we will finish the the mill algorithm okay so this of course this fact is is going to be used this this proposition is going to be used to prove that the M algorithm is correct I mean at the end of the day you get the output is what you what you

expect okay but it's it's going to be very easy I think yeah so um have a have a nice weekend have a nice weekend thank you weekend bye thank you bye for