PSE Lectures Ep 37 - Miller's Algorithm

Transcript

yeah so let's review what we had about the the Miller algorithm um basically I take um I take two points u and v on on the curve remember the setting is that we work over algebraically closed field of characteristic p and um p is is copre to

n so we know that that N is a integers mod n times itself and and now we H we look we we want to describe the Miller algorithm in a geometric way because it will help us ER conceptualize what what the process is so I'm I'm defining the the line between u and v for for any any two points u and v that are distinct so U is is not equal to V and also non non zero

points um I I look at the the the line between u and v basically we we went through this uh this this kind of stuff in equations I mean an equation of a nonvertical line is always y I mean Yus um MX minus Bal Z right or if you want the line itself is just a polinomial so it's it's a polinomial in two

variables ER where m and b are are determined by by the the coordinates of un and V and the divisor of such a line will always I mean this is a polom right polinomial in two variables but nevertheless a polom so a polinomial always has a a pole at Infinity right because if you substitute x equals infinity and Y equals infinity you get infinity infinity or minus infinity um so so we always I mean this is goes back to what we talked about the how to

classify all the possible divisors of of a line a line viewed as a rational function so this um this fits into this pattern and and since we know that the line um passes through unv then we know it must let's say u and v are distinct and and and non zero then we know that the line has to pass through a minus U + V right that's that's what what's written here so when I look at the set of zeros of this rational function

luuv well U is is a zero of this function V is also a zero and they are distinct so it's I I put them in separate brackets and and also minus U + V is is a zero of this rational function and since I know that this is the divisor of a rational function I mean a principal divisor I know that the degree of the divisor has to be zero so I know and I also know that it has a poll it has a unique pole at at the point at Infinity so I know that the

divisor has to be u i mean brackets U plus brackets V plus brackets of minus U + V minus 30 and the reason the reason I know that is that I have to have three in in the coefficient of O because I have no other pole and the sum of the the coefficients have to be zero I mean is this H is this clear it is it a so just one question so this I mean you know that the sum has to be zero because we are kind of assuming that this

divisor is principal or or it's another yeah I mean it's not we I mean a principal divisor is is a a divisor that is obtained as the divisor of some rational function so right if I write div of luuv luuv is a rational fun function in fact I I can give you the explicit formula the it's it's a it's a rational function with one in the denominator right because it's just a polinomial it's not a quotient of polinomial so so just to to be sure so

the the line of thought is that so we are working with a divisor of a rational function hence this is a principal divisor yeah and because of that princip by defin principal is is simply a synonym to say that it is a divisor of some rational function okay and and then uh by the properties of a principal divisor you know that the sum has to be three I sorry has to be zero and because of that you know that you have this multiplicity of on this okay okay good I know two I mean let's call this D DL I know two things about D L one I

mean eventually I know the explicit form but just to just because it is a principal divisor I know that the degree of DL is zero and I know that the sum of the L is the point at Infinity I mean the degree is the sum of the coefficients so the degree is 1 + 1 + 1 minus 3 so this is indeed zero and the the sum is you just remove the brackets and you you do the sum as you do it in the litic curve okay yeah

and indeed if I do U + V plus - U + vus 3 o I get o right yes so but but I'm saying how did I know that how did they know about um about this part I mean I I want to calculate this this is kind of a reminder of of a stuff we did about the classification of divisors of of lines but it's very easy to to recall because I'm saying I have a rational function

luuv I know that it has a a I mean it has three zeros on on the line namely the the point U this is a zero of this right because this a line that passes through u and v right M I know that V is also a zero of this line um of this function and I know that minus U + V is also a zero of this of this function and this is a I mean this function is a polom of degree one polom of degree one

cannot have more than three intersection points with a with a curve of degree three I mean this is like bazo theor or I mean it's also stuff that we proved explicitly so I I know that there can be no other zero I mean there could be no other point p on E such that m l u v of P is equal to zero okay there exist no no other P are you with me or now yes yes yes

yes okay so so I I'm saying I want to to understand the divisor of luuv I I know what are the the all the zeros of L of luuv these are u v and minus U plus v and we saw that each of them has degree I mean multiplicity one so now I look at this equation I mean I don't even need to know what m and b is Right m and b depend on the coordinates of u and v but I I don't need to know what m and b are all I need to know is that this is a polom

polom viewed as a rational function um has one a one point that is a poll it cannot have any other pole because it can never become Infinity every X and Y that you substitute into this polinomial will give you some finite value in the field so the only possible to get a poll namely to get I mean something that spits out Infinity is if you substitute x equals infinity and Y equals infinity I mean if you substitute the point at Infinity okay so I know that the only pole of this of this IR rational

function is O and now but in order to to pin down precisely what is the divisor of L I need to know what is the multiplicity of this pole o with respect to to L so of course course I can do uniformis but I'm saying I don't need I don't need to get into the details of uniformis because I know that the divisor has to satisfy that the coefficient of this plus the coefficient of this plus the coefficient of this plus whatever the coefficient is here has to be zero you see

yes okay so I know that the coefficient I mean the multiplicity of of O has to be minus three it's like in order for the the the divisor to satisfy that the degree of L the degree of DL is is zero okay so this is just a a recollection of how how to classify I mean how to to pin down precisely divisors of lines ER and and this is this is one typical example but we we can also do the edge cases so if I take a

u distinct from V but V equals to O then the the line that I'm I'm considering again it's useful to have a picture so I have my curve and this is a let's say U and um and here is the point at oh so I'm considering the the line between U and O the line between U and O is going to intersect the Curve in another Point namely minus

U and that's it right it's like it's not going to intersect the curve in any other any other place it's going to be a vertical line so so what I have is a this divisor here there is a mistake well it's not a mistake actually but let me just write it this is going to be so who are the who are the zeros of this um of this line I mean of course the pointed Infinity is always

this is this is going to be still a polinomial I mean this is the polom luuv in this case is of XY is going to be some x minus C because this is how a vertical line in the in the plane looks like I mean it's the set of all solutions to all zeros of the polinomial x minus C so you see um this this rational function has again it's a polom so it has a pole necessarily there is a unique

pole at the point at and and it has only two zeros on the curve U and minus U so the divisor must be bracket U plus bracket minus U this is the set of the the all zeros each of them is of Multiplicity one and then in order to to complement the the thing I have to have multiplicity to at the at the point at infinity or multiplicity minus two ER is it okay Nicholas or

no yep okay and then lastly I do the tangent line at U so the tangent line at U let's call it let's write a b um the tangent line at U this we saw so here's the picture right um and we saw that in the in the case of a tangent line um the multip I mean U is obviously a zero of of Tu right Tu is some

is some line I mean t is is again is again going to be some y - mx + m minus B for some m and b but in the case of the tangent line the the the tangent Point U has is a zero of the line of course but it is a zero of a a multiplicity too okay this again we saw but intuitively speaking this is because the the derivative vanish so if the derivative vanish it's like uh it

increases the multiplicity um now what is the other zero of Tu well I I have I have another point in which Tu intersects the curve e namely minus 2 U because how do you do a u + u u + U is you you draw the line the tangent line at U you look for the the other intersection point and you reflect so this is 2 U so if this is 2 U it means that this this point is minus 2 U and minus 2 U is is an intersection

point between the the line in the curve so it is it is a zero of the of the line and it has to have multiplicity one because you already have multiplicity too and we cannot have multiplicity more than more than three when we intersect a line in a in a degree three curve okay this is again I mean if you want the the easiest quotation is bazo theorem but we we did it Al explicitly so so I know that the coefficient here must be one the coefficient here is two and this means that the coefficient here next to the O has to be minus

three okay so I I know exactly how the divisor looks like and finally I look at the vertical line at U the vertical line at U well this actually we we discussed this is the divisor of the vertical line is bracket U plus bracket minus U minus 20 so so the vertical line at U is what we Define to be the the the line that passes through a u and minus C right so this is

here and the tangent line is is the line that passes between you and you okay so this is this is this H are we okay with the geometry okay so so now I remind you that we have a definition of um um of the whale pairing is um is this kind of thing the generic or generalized wh pairing is you need to take um a divisor DQ so you need to take two divisors DP

and DQ DP needs to be um equivalent to P minus o equivalent to P minus o meaning that the the difference of the two divisors is a principal divisor um and DQ similarly need to be need to be equivalent to Q minus o and then I take um a rational F I mean I take a rational function fdp whose divisor is n DP I I know that I can do it because p is an end torsion p and Q in fact

p and Q are end torsion points so n p minus n o and also NQ minus n o these guys are principal divisors I mean they are equivalent to zero and the reason they are principal is because well obviously the degrees add to zero and um and if and the sum of the each of these divisor is zero because NP minus n o is equal to zero since p is is an inion point so I

know that the need there has to be a so NDP is like n times this and this is a principal divisor so I know that the is a rational function fdp um whose divisor is NDP and similarly there is a rational function fdq whose divisor is is ndq and the the the wh the well pairing in the generic form says if you have a divisors DP and DQ that have a disjoint support and you take a rational functions fdp

fdq um that satisfy these two orange conditions then in order to evaluate the well pairing on on two points p and Q you just need to do fdp the rational function fdp evaluated at the divisor DQ and mod out or div by the rational function fdq evaluated the DQ H so so I need I need rational I mean I need divisors DP and DQ that have a disjoint

support in order to do this I um I pick a a two two points RNs um and I take DP to it's like it's like a shift by it's like a shift of this this divisor P minus o by by R so I do p p+ r minus minus r and I I take DQ to be a shift of this divisor by by the point s and in order to guarantee that these divisors have a disjoint support I pick

s well it's enough there are many ways to do it but but one of them is that you take s to be a point that is different than um than all these other four points in the the orange brackets um and then it's really like a a pedestrian task to to verify that these divisors DP and DQ have this joint support is this okay yes I think okay and so and and and of course the divisor

DP is linearly equivalent to P minus o because DP is is p + r minus r and then you do p + r minus r and you subtract from it P minus o and this is a divisor that has obviously the degrees um add add to zero because here I have minus one here I have 1 minus one one so in terms of the coefficients the sum of coefficients is

zero um and if i s if I remove the square brackets and I sum all the points I get P minus I mean p plus r minus r minus P plus o is is O so so this divisor the difference between DP and and this guy here is um is a principal divisor so so or by definition it means that DP is equivalent to P minus r this is what it means to for two divisor to be equivalent is that their difference is a principal divisor and you can check similarly that DQ is equivalent to Q

minus r so now I I'm I'm all I'm all set um I mean I know that for the DP and DQ that I chose um I can I can calculate the weight pairing by doing fdp evaluated the DQ divided by fdq evaluated the DP now fdp and fdq I still don't have any concrete um um form for them but nevertheless I I know what it means to say a a rational function evaluated at a divisor it means I mean assuming that

this rational function and the divisor have this joint support it means that for example if I want to do fdp evaluate DQ then this is fdp evaluated at the point Q times fdp evaluated at at o sorry H DQ DQ is not Q minus o but rather Q + r sorry Q Plus s um and then here

is s to the minus one this is this is what it means to do fdp evaluated at the divisor DQ right you take all the points that appear in the the divisor fq sorry in the divisor DQ and you plug them in into fdp whatever fdp is and whenever you have a a coefficient of a point I mean like in in DQ I have a coefficient one for this point and a coefficient minus one for this point so the coefficient I put in the um

in the exponent and I multiply all of it okay so when I do f um and this I abbreviate fdp to FP and I abbreviate F DQ to fq and so in order to to do the we pairing I need to do this quotient but this quotient is well the the numerator is this guy and the denominator is this guy so now what I'm left is in order to

calculate the whale pairing um I need to be able to um evaluate well to to have yeah what is the I mean to I need to be able to evaluate FP even though I don't know what what is the concrete form of FP I need to to be able to say what is FP evaluated at some general point x right this x so and of course if I can do it for FP then I can I can do I can do it for fq I mean p and Q are um some

General in torsion points and if I if I know how to do FP of X and fq of Y for any X and Y then I know how to calculate the while pairing so now um we H we want to we want a procedure to calculate FP of X for some general X and for some integer k i define a kind of an intermediate FK FK is a a rational function on E that has a

divisor of this form H and if you remember um a divisor of a h um I mean a given divisor does not define a unique rational function but if I I mean if I say that the leading coefficient is one then it defines a a unique rational function so I I pick I pick a rational function FK that is monic namely it has a leading coefficient one and the the divisor of it is is this I need need to check that this divisor in green is a um

is indeed a principal divisor but this is very easy because I look at the coefficients this is K and minus K they they cancel and here I have minus one and one so they also cancel um and if I sum all the point I mean if I remove the brackets and I sum in the elliptic curve I get KP plus KR minus KR um minus KP plus O So this cancel with this and I get O Okay so this is a principal divisor I

know that there exist a rational function f or FK that has this divis and why did I I say that these are intermediate functions it's because when when K is equal to N I look at FN what is FN it's n p + r minus n r right I mean when n is equal when K is equal to N I have n p + Rus n r minus NP but NP is

o plus O Okay so this is equal to this and this guy I remind you this is divisor of FP so if I choose FP to be also monic then I know that FN has to be equal to FP well whatever they are okay so this is all this is all like abstract considerations they tell me that if I if I calculate the intermediate functions FK and I know how to evaluate them on a

on a general point x then eventually I will know how to evaluate FP of okay and I think the last thing we did in the last session is this proposition that says if I take so I have this FK right now I have I take a two integers A and B and I consider the divisor of f time FB times the line between AP and BP divided by the vertical line that passes through a plus

BP then something something nice happens it turns out that this divisor is is f of a plus b i mean it's the same as the divisor of F A plus b and again since we can assume all the time that in the the original constructions we chose um functions that are that have leading coefficient one then equality between divisors of functions really implies equality of of functions so so I will have equality of of these

two rational functions in in Orange okay and this was this is a a very simple calculation I mean I don't want to repeat it h but it's it's very straightforward you you just need to remember that the divisor of a product is the sum of divisors and the divisor of a quotient is the the difference of divisors and we have a a a description of of divisors of each of the each of the elements in the product H so we we can do the calculation ER is this okay this was a

long recap but I I want you to be like fully on board okay so now the next LMA ah or maybe corer yeah this is corer um the f k squ

times the the tangent line at KP this is for any K and the tangent line at k divided by the vertical line at 2 KP is equal to the f2k and the reason is very simple I mean just look at what we did ER you put a proof take a equals B b equal K

in in the the previous proposition right if I take aals bals k then I have like FK FK if if a is equal to B then the line through a and BP I mean a is equal to B so this is the line between AP and and AP this is the same as the the tangent line at AT AP or but a is equal to K so the tangent line at KP and here I have V K plus KP okay and this is the divisor of F K plus K so f2k

ER and then maybe I think now it's the last proposition last LMA L LMA before the the algorithm um if I take F1 I want to evaluate the the divisor of F1 the then I claim that this is the same as the divisor of the vertical line at p+ r divided by the line between P and R and uh this is another another

straightforward calculation um let's do a FS1 by definition is a function that has a um p+ R minus P plus O Okay this I can I can show you um yeah so just just uh substitute k

equals 1 here you get p + r minus r minus P plus r um and the right hand side is equal well what is the divisor of v p+ r um it's p+ r R remember the vertical line through a p+ r has two zeros a p+ r and minus p+ r and it has a a one pole of the of degree that must be two so minus 20 this is the divisor of a vertical line at p+ R and

from that I need to substract the divisor of LP plus of of LP R but the divisor of LPR I mean I I know I know it as well it has p as a zero it has r as a zero and it has minus p + r is a third zero this is the the ordinary line between P and R um and of course it must have a poll of degree three so this is minus um three or um and okay and now I just h i just

do the calculation it's a it's exactly p+ R um these two this is the divisor of l p and um and now okay so this cancels sorry this this stays but this cancels with this um this minus 2 cancels with this H minus minus- 3 o but I have some

remaining O So plus o and and then minus P minus r so this is in indeed equal to the left hand side uh is it okay this is a like it's a simple calculation so I guess now is a good time to take a break ER and then ER we come back we do the I describe the

algorithm and um and I prove the correctness and the and do the complexity of good okay e

e e okay so

um so so let's let's go back to uh the actual algorithm and remember ER just the setup I mean we have two points and um we have a a rational function that we know exist abstractly um in in

it it needs to satisfy that the divisor of FP is this n p + r minus n r where um R is some some point on the curve H so so now I I write the binary ER expand of of n the binary expansion is like Su I equal 1 sorry zero up to some t t t is approximately log log

n and this is two 2 to the i n i i i mean for example Nal 3 what will be the the the expansion I have um 3 is equal to um I mean n N1 n0 equal to 1 times h 2 to the 0 plus h 2 to the 1 times N1 and N1 here is going to be equal to one as well okay

so this this is the the standard binary expansion so the ni are 01 H and and T is approximately log n and and now um the input so we have we have the inputs H and the output is going to be um FP evaluated at

Q and this I call X so step one I set X or X1 rather to be the vertical line at p+ R evaluated at Q divided by the line between P and R and again evaluated at Q second

step I let X be equal to X1 H then I let Z equals p and now I start a I start a loop so four um T equals sorry I equals T minus and up to zero I do a a for

Loop and in this for loop I have um let's say 4.1 um I take X to be x square times Z evaluated at Q divided by the vertical line at 2 Z evaluated at Q 4.2 um I set Z to be equal to 2 Z so I I

double I double the point and and then 4.3 I do an if so if n i is equal to one then um I I further set this is 4.3.1 I further set a x to be X time X1 times the the line between Z and P evaluated at Q

Q divided by the vertical line at the point z+ P evaluated at Q and um 4.3.2 I set a z to be z+ B okay and that's it that's uh so let's say and if and in for okay

so ah and and of course I return I return X okay so um the main proposition um this algorithm is um complexity log n of um

um points addition in in and upon termination um Z is equal to NP which is equal to O because p is an end torsion point and M N X is equal to FP okay

okay so this is the the statement the the first part of the statement I mean namely the complexity this is really easy because um all I need to do I mean I have some constant steps and then what matters for the complexity is a um what is the size of the for Loop and H what is the the number of um operations I need to do in each iteration of the for Loop so the

size of the for Loop is log n right the size of the the for Loop is is T and T is approximately log n i mean it's like Plus minus one or something like that um and what what do I need to do in each of the the iteration of the for Loop well I need to do this x is is is some number right and I need to evaluate what is the the tangent line at Z tangent line is some polinomial polinomial and I substitute in this polinomial I

substitute the coordinate of Q so that's that's not expensive and also V2 z q once I know V2 Z I mean once I calculate the polinomial V2 Z then I need to evaluate it in Q what do I need to in order to to calculate the the polinomial V2 Z I need to know what is 2 Z once once I know the coordinates of 2 z i calc I have a formula for the the vertical line at at 2 Z so I need here I need to do one point addition then here I need to do also another Point addition and here I will here here I I need to do another

Point addition and here another Point addition so Al together it's like a four four points Point addition in the in the case that I get into the if Loop uh and so this is this is really four times log N Point addition at at worst case so so the complexity is complexity is very clear ER is this okay it's okay for the

complexity I'm not sure I understand why is it done like this like it's a basically a double and add algorithm in some sort but I yeah why is it complete with yeah yeah yeah no I mean I didn't prove completeness yet but I'm saying complexity okay y so so now um um for for completeness um if if T is equal to zero T I remind you T is the the the the number of of n

i in the binary expansion expansion of n so if T is equal to zero then then n is either zero or one if n is zero I have nothing to do if n is one H then it's also it's it's very clear I mean um because I don't get into the for Loop right so if n is equal to if n is equal to one t is equal to and let me write it in a different color so if if T is equal to zero and um n is

equal to one this this means really that n0 is equal to one um then I don't do the the for Loop because the for Loop starts from T minus so so I have a I have a nullified for Loop what is X1 X1 remember we had a LMA so this is V of p+ r divided by um by l p p p r and let's look at the LMA vp+ R ided by LP R is

fub1 right I mean they have the same div resource and we assume that both of them are harmonic so equality of divisors really implies equality of rational functions so these two rational functions are are equal and in particular if I evaluate one of them I mean if I evaluate both of them at Q I get the same thing so in order to get vp+ r divided by l p+ r evaluated at Q This is F1 of Q okay so and so if n is equal to 1 I get that

X1 is equal to fub1 of Q which is by definition I mean n is equal to one right so this is FN of Q and FN we we saw that this is FP of Q okay and X is equal to X1 and Z is equal to P so upon termination if n is equal to one I get what I want now um what about n equals I mean t t bigger than

one so are we we clear here actually and before I erase and now you you follow yes I think yeah I mean all I'm saying here for the N equal one case I'm using the Lemma this byemma this is byemma uh X1 is going to be F1 of Q and F1 is I mean since since this is FN of Q and FN of Q we had a this is by by construction by Design FN of Q is FP of

Q okay and and that's that's what I want the output to be now what if a a t is equal to one so if a a t is equal to one then I have a a of course a n is um n0 plus h 2 * N1 H so so

n let's say n is bigger than one because n equals 1 we already covered and it could be um up to three right so so n is either equal to two or or equal to three um the the N1 N1 is non zero right because the in the the binary expansion I assume that NT is non zero otherwise this would not be until T it would be until some some earlier index so um so so n is is either two or three um

I I we already calculated that in after the first iteration X1 is going to be F1 of e of Q um and now in the second the Second Step X is going to be F1 of Q as well um Z is going to be p and now I enter the for Loop the for Loop is it has only one iteration H in this iteration I I well I say that X is x² times times this

time this um tangent line at Z modul vertical line at 2 Z so what is this so 4.1 ER e x is going to be F1 Q squar times um tangent line at Z divided by vertical line at to Z and on that evaluated at Q but we had another

LMA that this is equal to F of 1 + 1 Q so F2 of Q you remember this this we had a LMA without the Q but the LMA is more General it tells you that that two two rational functions are equal so let me just show you the Lemma you see this is a or the the it was a corer from from LMA okay this is for any k um is this clear four

4.1 is clear yes yes okay and now 4.2 um Z I know what is z z is p so now Z is equal to 2 p and now I get into the for Loop H the for Loop let's assume I mean okay if the for Loop is it has one iteration H and this one iteration is I mean whether n zero is a is is zero or one so let's let's say I don't do the

the E loop I mean I don't do the the iteration it means that H n n0 equals to zero I don't do the the if iteration then I I return F2 of q but if n0 is is zero it means that n is two so I return F2 of Q um F2 of Q which is FN of Q which is FP of Q as as I as I wanted and in did I also

return Z to be two uh 2 p which is which is another another part of the statement and now let's suppose that n 0 is equal to one which means of course that n is equal to three so if n0 is equal to one um I do get into into the if Loop into the if statement and what I do in the if statement is I take X and I put it so is 4 3

1 um I um I put the value of x to be equal to x * X1 times this quotient line between z z and P and vertical line of Z Plus P both evaluated at Q so what what is X what is X here x is F1 what is X1 X1 is also F1 so I get fub1 square Q times this H this line I mean this line between zp and between Z and P and divide by the

it sorry but um it's yeah it's it's going to be F Square F1 sorry so so because X is F2 so X is F2 of Q X is I mean X before is F2 of Q so now X is going to be FS2 of Q time fub1 of Q times this line a line between z z and P evaluated at Q divided by the vertical line at z+ P evaluated at

Q but we had a LMA by the LMA this is F3 of Q right this I remind you the Lemma or the again the corer of the the Lemma okay why the cor is useful here because we're not using the same yes it's not the cor it's it's the the dma okay okay so it's it's yeah here a a and are different um so so I get F3 q and and then in 4.32 I I put Z to be 3 Z 3

p and that's it I I end I end the if the if statement and I end the for Loop and I return X so again I returned what I needed to return you see and ER and you can prove by by simple induction that the the whole algorithm Works ER I think it's it's not it's not very enlightening to uh to do it it's AIT bit of a formal game H but what what you need to understand is that I mean in the the the the kind of all the steps

before before the for Loop um I I I just I just get like all the time the same thing I mean I get h x x and X1 to be I mean fub1 of Q and Z to be 2p and then in in the in the for loop I either I increase the I mean X is going to be F FN I mean X is going to be f um FK of of Q for some K and when I do this step 4.1 I increase I mean if x was

F K of Q then it's going to be now FK + one by the LMA and depending of whether ni I is equal to one or not I I do it one more time okay so either I increase X from FK of Q to FK + one of Q and then if n i is equal to to one then I increase X to be from FK of Q to f k + 2 of Q and since I started with x equal fub1 of Q then I know that that I get F FN of

basically can you could you re show the Lima again because I'm stying to see why so I followed your orange explanation I'm just trying to see why the Z is important to update what where world do the Z play here and I'm not the Z because the Z is going to be used when I do the the line I mean the I take the ver I me see the F2 F F1 becomes S3 and this but the the Z part I'm I'm a bit struggling maybe yeah so so you see what is happening here I mean z is equal to um I

mean in order to use the the Lemma not the LMA it's the proposition you see that the proposition requires that in the L's I have a a a comma BP and in the v i have a plus BP okay so so I need to know that the Zed really fits into the I mean here let's say here I go from FK of Q to FK + one of q but this depends on on Zed to be to be of a particular value I mean

here Zed needs to be two to P in order in order to use the proposition yes so and so so the Z is kind of a demi variable that you you keep throughout the the algorithm in order to use the lemon or the the proposition basically ER but all we're doing here is we have this Lemma that allows us to to go from FK of Q to f k + one of Q and we we just set set the stage so that we do um

exactly n n updates for X from F1 of Q up to F FN of Q and the way to do it I mean s to do it efficiently you you you do the binary expansion of course it's not the only way to do it that's cool yeah okay so this uh this is clear yeah and you see that this is very efficient right it's like a I mean additions or addition of points on elliptic curve is not is not so

easy um but it's not super expensive I mean you you probably know better than me I mean you you work with it also uh since we we don't have much time left uh uh because we probably not going to enter a new topic now unless you have but I wanted to ask like because this is the mider Loop right yeah Miller yeah sometimes it's called the Miller Loop yeah and uh in Miller loop I know you can also batch multiple pairs of points together it's just an extension of this algorithm basically where you have different pairs of p and Q and maybe you you gain some optimization by keeping the same Z or something I don't

know because I know that all the API I used before were able to batch pairs of points so to compute uh directly the the final pairing about each e p and Q times e and s times e t and u but this is a I mean okay first I should say there are like multiple versions of the Miller algorithm in the in the literature um the the version I'm I'm presenting is first of it doesn't H compute the pairing in itself yeah we need to get the the final root of unity at the end

this but yeah I mean so okay I mean the short answer I don't I don't know of the top of my head how to do it in bch I I can believe that it's possible um basically the as you can see the backbone of the whole the whole algorithm is these observations that are given here in this right um one so if you have a version of this proposition for multiple points some kind of bch version then I imagine you could do the the bch version of the

algorithm um but the in the literature you may find um Miller algorithms that calculate um in literature ER you can find the something like for example you take FP such that the divisor of FP is precisely NP minus n o okay and you you you want to calculate

FP of Q so we did a more General version right we we had like a this divisor was translated with n p+ NR but you may find in the literature that R is equal to O and then and then it can simplify but but it would push the it would push the weight because eventually you would need to evaluate um the whale pairing so it would push the some weight of computation to to another

place um yeah uh what else is this answering your question nichas yeah yeah yeah thanks I mean I have plenty of question now that we reach the paing stage yeah but in practice we also use points on the not torsion points so how do we because right now p and p and Q this is all in practice you always you basically um you take the point you take the curve basically you have um an embedding degree um let's say embedding degree

what's the usual notation D I don't know of e means that um I mean e is defined over some f p or fq and embedding degree d means that a if I take e of f p to the D and I take the end torsion points here I already get the full end torsion

points okay and how do you get the F tion tion point so you see I mean we know that e e e k er sorry e n this is K okay this K is like the the base field over which the the equation of the elliptic curve is defined and E bracket n um the set of all um of all n t points in the algebraic closure

right you remember this this is the definition of the the end torsion points but what is what is e of of the algebraic closure e of the algebraic closure is simply the union of all e of the of the extensions m p that's APK now this is a finite set and this and let's say here K is bigger or equal to one and this is a a union of infinitely many set a finite

set that is included in a in a chain this is a chain right this is like e of f p to the K is contained in E of F A P to the I don't know 2K right this this thing is a chain so I have a finite set that is contained in an infinite chain it means that it has to be contained in some finite stage of chain and the embedding degree is the minimal the minimal place in this chain for

which I I I get all the intorsion points you see this is how you you pass from um from this I mean the algebraic closure is is good for theoretical um considerations but eventually in practice we need to have a finite like a finite set so we we choose elliptic curves that has a a a a small embedding degree and yes go go good I thought you finished yeah so um okay so

then I have e e of N and um what do okay I guess I need to to prepare a little bit before I say solid in that let me let me look what I wrote yeah but but go ahead if you have another question it's a followup question to what you explain so you I understand now that instead of considering points in the full algebra closure we can only consider point on the El curve based on FP to the D but still my question remains is that when

we do pairing in practice our inputs points are in the perir Define over e of FP not over e of fbd and so how do we no so things that's we just we just consider the extension like we just put zeros to the over coordinate or something like this like no no no I mean so um we take a prime so we take a uh some Er let me let me just look for something I mean if the yeah I mean this is like we want to

extract a a type two pairing from this so we we write let's say e of fqfp um the number of points is is some is some H * R where R is Prime and now we look at H at at e r okay and we we are guaranteed that e is

contained in E of FP to the D where D is the embedding degree okay and we we simply look at E I mean e e is going to be in fact so e r is going to be ZR times ZR and in fact we look at a at a sub group G1 is a a subgroup of of ZR I mean of er which is isomorphic to

ZR okay so you always you always live in this R torsion point where R is a prime and you do the and this is you you use the the the well pairing of degree R right ah so we are we are alling that we use in practice are actually AR Point like all the points are already AR points by default because they of ah okay okay okay and this this age is called the co-actor yeah and what you want I mean the security of this of the whole thing

really depends on R and not on H so so you want H to be as minimal as possible Right but this this this is like the design of of pairing friendly curves what you I I imagine what you need in practice is something like you already have the the pairing friendly curve so somebody designed a an elliptic curve that has a small age co-actor and you just need to know the prime and then you need to know how to how to extract a a z z ZR a subgroup from the the erer torsion points but

that's it's usually very easy because H the the r torsion points are ZR time ZR so you have a you basically have two canonical subgroups of of Si size Z are um I think usually they are taken as some like kernel of the fenus map this again we didn't talk about it but ER yeah that's that's roughly the the way you do it and now there is a this issue of twists but again I feel we are like yeah

unfortunately we don't have a lot of time but um the the twists are a a another another way to increase the efficiency and so usually the embedding degree is a is is smaller than 20 so we are working in I mean the security look we have I mean in this case we have ER it's going from ER times e r into um f p to the D in fact it's it's going to be the the

the roots of unity the r roots of unity in FP to the D um so the security of the the of the pairing depends on on two things a a one is the the difficulty to do the elliptic curve discrete logarithm problem in ER or in E basically and two is to do the discrete logorithm um in a FP to the D and you want to you in order to to

gain maximum security you want that the difficulty of these these two is is is approximately I mean similar and so that's there's an inherent tradeoff between performance and security because basically we want R to be very high I guess but then it impacts performance both both also the impacts performance yeah I mean and the and the impact performance uh yeah yeah so to be very high because otherwise it's easier to factorize oh yeah yes yes but the the advantage of elliptic curves

is that it doesn't need to be astronomically High because the discrete logarithm problem in in elliptic curves is quite hard it's not like a it's not anywhere near the discrete logarithm problem in a in like integers modul prime or something it's it's much harder so so you can choose a prime to be not Astron astronomically high but just just High ER okay so I didn't say how to extract G2 but G2 yeah G2 is going to be

um in this case G2 you're going to do um er um intersection with the igen vectors or igen values of the the Q forus map this is one H one iCal choice but again we we didn't talk about so I apologize but that's that's the constraints we are we are given but

I just want to to indicate that um what you do in practice is not very different from what we did I mean you need to have a um like a nonsymmetric pairing so for for this you need the the Tate pairing or one of the others the ETA pairing and so on and and there you have a canonical way G1 by the way is can be chosen canonically um to be intersection the the

one values of the b m okay that's like just the slogans I guess for for now but um but you the point is you have canonical ways to to choose the G1 and the G2 and I mean assuming you you you pick some pairing friendly elliptic curve you you have some guarantees um on various stuff and including security um if you want to find the generator that's also not a problem so um so for example to find

so to find a a generator of a G1 uh again G1 is isomorphic to the cylic group of order R where R is a Prime so it is it is a it is generated by some unique I mean not unique but it is you can write it as generated by one element and um so again rewrite the number of points on e as H * R

and um we you find the point P such that HP is non zero if HP is non then since HP is zero and R is prime HP is uh a

point of order R so if you find the point P such that HP is non zero and HP belongs to G1 then you you found the generator to G to G1 okay so this is just sporadic stuff on kind of the the the more applied applied properties of pairings uh but yeah I I guess I guess we should end here uh other questions or maybe requests for

next time no I mean um as terms of request I'm happy to go either on another pairings or maybe go into this Twisted sexist 12 because Twisted curve whatever these things anything that can fit into ours yeah yeah I'm I'm afraid we we cannot do it we have one more session left ER what I can do I can I can present the Tate pairing but without the proof um and maybe talk a little bit about the fenus map and then the fenus

map once you know the properties of the forben but you can all read it in the book it's it's like I think it's a written pretty well um so basically once you know the properties of the fenus map you can do the Tate pairing and this I mean and using using the stuff I describe now it gives you um an asymmetric pairing which is pretty efficient um yeah okay so I will I will think about what to do next time I I guess I will prepare a little bit about it but uh

the the the twists I mean the twist I think are too complicated to to fit in in this tiny session we have left H so that we will have to to skip but uh we can talk about it when we meet uh all right so that's it for today thank you thank you very much bye bye have a nice day