This video is part of an online undergraduate course about the theory of numbers and will be about quadratic reciprocity. So I'll start with an example to illustrate it. So last lecture we proved, or rather I left this as an exercise to prove, that five is a quadratic residue of p if and only if p is congruent to one or four modulo five. We're assuming p is not equal to two or five, of course, because these always go wrong. And this in turn is equivalent to p being a quadratic residue of five, because one and four are exactly the squares mod five. And this is an example of reciprocity. So reciprocity roughly means you can switch the numerator and the denominator of the Legendre symbol. So five is a quadratic residue of a prime, odd prime, if and only if the odd prime is a quadratic residue of five. Which is actually a rather strange fact. There seems to be no obvious reason why these two things should have anything whatsoever to do with each other. So let's see if that works for other primes. So the Legendre symbol for three in p is equal to plus one if and only if p is congruent to one or eleven modulo twelve. On the other hand, p is a quadratic residue of three if and only if p is congruent to one or seven mod twelve. And so these are definitely not equivalent conditions. However, we can improve this by looking instead at where the minus three is a quadratic residue of p. And this is equal to minus one p times three p by multiplicativity. And this is one if p is one or if p is one mod four. So this is equal to one if and only if p is congruent to one modulo three. So we see that five p is always equal to p five. But the analog for three is that minus three p is equal to p three. And Euler and Gauss did a lot of calculations of calculating these quadratic residue symbols. And what they found was that this identity holds if you replace five by any prime of the form one mod four. And something like this holds if you replace three by any prime of the form three mod four. So we get Euler and Gauss's law of quadratic reciprocity which says the following. It says pq is equal to qp except when it's not equal to qp. More precisely, this happens if p or q is congruent to one modulo four and pq is equal to minus qp if p and q is congruent to three modulo four. So this is often written in various slightly different forms. For example, we might write it as pq times qp is equal to minus one to the p minus one over two times q minus one over two. Because this expression here is odd exactly when p and q are three modulo four. So now I want to prove the law of quadratic reciprocity. And there's a big problem with the proof in that there's rather too much choice. There are something more than 200 different published proofs of this. And I know this because this book here, it's a really nice book about reciprocity laws. You see, here's the original quadratic reciprocity law that we just wrote down. And in one of the appendix, appendix B, he has a list of proofs classified according to who did them and what ideas the proof used. So the very first proof is due to Legendre in 1788 except Legendre's proof was incomplete because he sort of assumed Dirichlet's theorem which hadn't actually been proved at the time. So the first actual proof was found by Gauss. And the second, third, fourth, fifth and sixth proof were also found by Gauss. He found eight proofs altogether because if you look further down the page there are another couple of proofs by him down here. And people kind of inspired by Gauss finding a large number of proofs. And we have an entire page of proofs here and it goes on and on. So the next page is more proofs and there are more proofs here and more proofs here and more proofs here and ending with proof number 196 in the year 2000. So you can see that's pretty much one proof a year and this is about 20 years ago. So I guess there are maybe 220 published proofs by now. So we've got a serious problem about which of these proofs do we select. And all of the proofs have one thing in common that at some points you need to think of a rather clever non-obvious idea. There seems to be no completely straightforward proof of this law. And the proof which seems to involve the simplest non-obvious ideas, the proof that uses Gauss sums. So what is a Gauss sum and how did Gauss think of them? The Gauss sum traditionally denoted by a tau is given by we sum over all x mod p. So we're taking x equals 0, 1, up to p minus 1. And you sum the Legendre symbol where the x is a square or not mod p and you multiply it by epsilon to the x. So what is epsilon? Well, epsilon is a p-th root of 1, more precisely epsilon is equal to e to the 2 pi i over p. And so in particular 1 plus epsilon plus epsilon squared and epsilon plus epsilon to the p minus 1 is equal to 0. And now we notice that epsilon to the x is actually well defined even though x is only defined mod p. Because if you add a multiple of p to x, this doesn't change epsilon to the x because epsilon to the p is equal to 1. So Gauss sums are well defined. And if you've come across Gauss sums for the first time, your first question is probably how on earth did Gauss think of such a funny looking expression? So I'm not actually quite sure but here's one way he might have thought of it. So Gauss constructed a 17 sided polygon by ruler and compass and he did this by looking at 17th roots of unity. And we also want the group of numbers modulo 17 that are non-zero optimum multiplication. So let's write down this group. So all its elements look like this. And what Gauss needed in constructing the 17 sided polygon was he needed, among other things, he wanted a quadratic irrational that is a polynomial in zeta. And the one he used was given as follows. What you do is this is a group under multiplication. It has a unique subgroup of index 2 consisting of all squares. So we take all things that are squares modulo 17, which are these numbers here. And then he just sums over this group of order 8 of the powers of zeta. So you might put alpha equals zeta to the 1 plus zeta to the 2 plus zeta to the 4 plus zeta to the 8 plus zeta to the 9 plus zeta to the 13 plus zeta to the 15 plus zeta to the 16. Well, there's a slightly neater way of writing alpha which is to use the Gauss sum. So the Gauss sum is going to be 1 plus 2 times zeta to 1 plus 2 times zeta squared and so on because you get two copies of each square because, for example, 4 is 2 squared but it's also minus 2 squared. So we see that in fact tau is equal to 1 plus 2 alpha. So it's actually the Gauss sum is the neatest way of writing a quadratic irrational in terms of zeta. And now Gauss wanted to show that it was a quadratic irrational and the formula for tau is very neat. It just says that tau squared is equal to 17. So that's what a Gauss sum is and we'll now show how to use Gauss sums in order to prove the law of quadratic reciprocity. So I'm going to try and fit the entire proof onto one page. So we need two lemmas. The first pink lemma says that tau squared is equal to minus 1 to the p minus 1 over 2 times p. And we just recall that tau is equal to sum over x of xp times epsilon to the x. And now tau squared is got by multiplying this sum by itself. And we can multiply this sum by itself by writing a double sum where we sum over all x and y of xp times epsilon to the x times yp times epsilon to the y. And now we can rearrange this a little bit. First of all, we can just sum over x and y none zero because if x or y is zero, these terms vanish. And then the Legendre symbol is multiplicative so this becomes xyp and we get epsilon to the x plus y. And now we want to simplify this Legendre symbol because x times yp is a bit difficult to think about. So what we do is we make the following change of variable. We change x to x times y. And we can do this because y is none zero so this map has an inverse and it's a sort of acceptable change of variable. And now this sum becomes sum over xy not equal to zero of xp times epsilon to the xy plus y. And it looks a bit at first sight as if I've made a mistake because shouldn't there be a y squared in here? That should really be xy squared. Well no because you notice that y squared p is equal to one so we can drop the factor of y squared from there. And now what we want to do is sum over y. So we're going to take this bit here and just sum it over y not equal to zero and ask what is that equal to? Well that's easy to work out because if we sum over all y of epsilon to the ay this is equal to not if a is not congruent to zero. And it's equal to p if a is congruent to zero. So this sum here we have to subtract one because we're summing over none zero y and we get minus one if x plus one is not congruent to zero. And p minus one if x plus one is congruent to zero. So we can work out the sum over y. And now we're just left with the sum over x. And first of all we've got a term p here coming from x equals minus one which gives us minus one pp. And then we have to sum over all these minus ones over all x. So we've got minus xp. Well we can simplify it. This sum here is just zero because there are just as many quadratic residues as none residues. So all these terms cancel out and we're just left with this. And now by Euler's identity minus one p is just equal to minus one to the power of p minus one over two. So we've proved this identity here. So this is the first identity. And now we need a second orange identity. And the pink identity we work out tau squared for the orange identity we will work out tau to the power of q. And we're going to work out tau to the power of q modulo p using the fact that x plus y to the q is congruent to x to the q plus y to the q mod q. So we take the sum for tau and to raise it to the power of q we just need to work out raise all the terms to the power of q. So this is going to be a sum over x of xp to the power of q times epsilon to the qx. And you notice we're doing this modulo q, but we also need to allow q times polynomials in epsilon. So it should really be modulo q times all polynomials in epsilon. So both sides are going to be polynomials in epsilon and all the coefficients have to be congruent modulo q. Well we can simplify this a bit. q is odd and this is plus or minus one so we can delete this because q is odd. So one or minus one to the power of any odd number is the same. And now we're going to make a change of variable. We're going to change x to x over q in order to make this exponent nicer. So this becomes sum over all x of xp times qp times epsilon to the x. So you might think this should be a q to the minus one, not a q, but of course q to the minus one p is equal to qp because the ratio is a square. And now the sum over x here if we ignore this Jacobi symbol is just the Gaussian sum again. So this just becomes qp times tau. So that's our second lemma. Now we prove the law of quadratic reciprocity. And we start with qp and now we're going to apply the orange lemma. And notice that this is just tau to the q minus one because we just take tau to the q is equal to that and we just divide both sides by tau. And we can write this as tau squared to the power of q minus one over two, obviously. And now we're going to apply the pink lemma in order to work this out. So this is now congruent to, well tau squared is given by this expression here. So we just fill that in. It's minus one to the p minus one over two times p all to the power of q minus one over two. And now this is congruent to minus one to the p minus one over two times q minus one over two times pq. And why is that? Well it's because Euler's lemma states that this p to the q minus one over two is congruent to pq. And now if you look at this we see we've got qp is equal to this sine times pq which is exactly the law of quadratic reciprocity. I should say this makes the proof look almost trivial because the formula for tau squared we already have if we've don't been doing cyclotomy and constructing 17 sided polygons. So really there's just one line there and one line there in order to prove the law. This is really misleading. It took people like Gauss and Euler and Legendre many years before they managed to find a proof. And the first proof Gauss found was actually a lot more complicated than this. I mean he probably should have in an ideal world he would have taken his results about cyclotomy from 17 sided polygons and immediately noticed this could be used to prove the law of quadratic reciprocity. But as I said it took several more years before he was able to do this. So another way of motivating Gauss sums is that they're actually very similar to gamma functions. So I'll just explain why. So you should think of a Gauss sum as a sort of gamma function. So let's just recall what a gamma function is. Euler's gamma function which is a sort of variation of the factorial for real numbers is just the integral from law to infinity of e to the minus t, t to the s minus 1 dt. And the Gauss sum is equal to sum over all x of epsilon to the x times the Legendre symbol. And what you notice about the Gauss sum and the gamma functions they have nothing whatsoever in common at first sight. They're completely different formulas. But now let's take a closer look. So here we've got a sum over all x in the field z modulo pz. And an integral is a sort of sum. And here we're integrating over the field r or at least the positive elements of r. Okay so there's a, we're forgetting about the negative numbers but never mind. So the sum over a field should be thought of as very closely analogous to the integral over, well half a field whatever. And then this epsilon to the x, well that's something to the power of x. And this is something to the power of t. Well that's fine. These obviously now correspond. And what about the Legendre symbol? That doesn't look very much like t to the power of s minus 1. Well actually it does because you notice that xyp is equal to xpyp. And tu to the s minus 1 is equal to t to the s minus 1 times u to the s minus 1. So they are indeed both multiplicative. And you can think of these as both characters of the multiplicative group of a field if you're into representation theory. So really these are very similar and the similarity extends to identities they satisfy. So we've proved tau squared is equal to minus 1p times p for example. What's the analog for the gamma function? Well it's the reflection formula for the gamma function which says gamma of s, gamma 1 minus s is equal to pi over sine pi s. And again at first sight these two formulas don't seem to have an awful lot in common. But if you look at the proofs, the proofs are almost identical. Well they're not almost identical but they have a fair amount in common. So you remember we proved this by taking the sum at sine of the x plus y times xyp. And saying this is equal to sum over xy of xp times epsilon to the xy plus y where we changed x to x times y. And one way of proving this formula is to write this product as a sort of double integral. In the same way we write this as a double sum and we get e to the minus t minus u, t to the s minus 1u to the minus s d t du. And now we make the change of variable t goes to t u. And if we then carry out the integration over u this becomes the integral over t of 1 over t plus 1 t to the s minus 1 dt. And you notice this change of variable looks very much like that change of variable. And this bit turns out to give you the right hand side of this identity. So you can think of Gauss sums as being a sort of gamma function over finite fields. Or I guess you could also think of a gamma function as being a Gauss sum over the reals if you prefer to do things backwards. Now I'll show how to use the law of quadratic reciprocity to work out the Legendre symbol. So let's try and work out a p for say 1001 divided by 99991. And I said we could do it using Euler's method. You can work out a to the p minus 1 over 2 modulo p. And that would be a pretty unpleasant calculation to do by hand on this example although it would be fairly fast on a computer. But if you're working by hand it's much easier because as everybody who does metero arithmetic knows 1001 is 7 times 11 times 13. So we can factor it like this. And now I can work out each of these three factors very quickly using quadratic reciprocity. So for example this one turns out to be we can turn it upside down but get a minus sign because 7 and this number are both 3 mod 4. And now I can reduce this mod 7 and this becomes minus 3 7. And if I'm feeling really lazy I can use quadratic reciprocity again and say this is now plus 7 3 because 3 and 7 are both 3 mod 4. And now I can reduce 7 mod 3 again and say this is 1 3 and this is finally equal to plus 1. I can work out these two in the same way. This is plus 1 and this is plus 1. So this number here is plus 1 and we see that 1001 is a square modulo 99991. In case you're interested it's actually 38521 squared unless I've made a mistake. And you see in order to work this out let's summarize all the properties of the Legendre symbol that we need. First of all we have the easy properties ap equals bp if a is congruent to b mod p and abp is equal to ap times bp. Next we have the cases for minus 1 and 2. So this is equal to minus 1 to the p minus 1 over 2 and 2p is equal to minus 1 to the p squared minus 1 over 8. Which if you think about it is just a rather funny way of saying this is 1 if p is plus or minus 1 mod 8 and minus 1 if p is plus or minus 3 mod 8. And finally we have the quadratic reciprocity law and qp. And using these rules we can work out ap for any a and p provided we know how to factorize numbers. Because you can see by repeatedly factorizing the numerator and using these laws we can keep on reducing p and q in a way that's kind of rather reminiscent of Euler's algorithm for finding the greatest common denominator. However there's a problem that factorizing numbers can be really hard if a or if a and p have hundreds or thousands of digits. Well there's a modification of the Legendre symbol called the Jacoby or Jacoby symbol that we will talk about next lecture. Which means you can work out the Legendre symbol without having to factorize anything. As a final example I just show how to use quadratic reciprocity to test firman numbers to see if they're primes. So you remember the firman number is 2 to the 2 to the n plus 1 and we want to know is fn prime. And n might be you know maybe around 20 or something in which case this firman number will have somewhere of the order of a million digits. So there's actually no way you can check whether it's prime by trial and error. Well suppose fn is prime. Then let's look at whether 3 is a quadratic residue of fn or 3fn. Well we can use quadratic reciprocity to say this is fn3 because fn is 1 mod 4 unless n is, well if fn is 3 that's not true. But let's take fn greater than 3. If you have trouble whether checking 3 is prime you really have problems. So this uses quadratic reciprocity. And this is equal to 2 3 because fn is 2 mod 3 as you can easily check and this is equal to minus 1. So 3 is not a quadratic residue modulo fn. So 3 to the fn minus 1 over 2 is congruent to minus 1 mod fn. That's if fn is prime. And now let's try and do it the other way round. If 3 to the fn minus 1 over 2 is congruent to minus 1 mod fn. Well we look at this. This is just 3 to the 2 to the 2 to the n over 2. So this means that 3 to the 2 to the 2 to the n is congruent to 1. That means the order of 3 divides 2 to the 2 to the n. It's not very often you get a tower of 4 exponentials in a serious way. And that means the order of 3 must be a factor of this number. But the only proper factors of this number divide this and 3 to the power of this is not congruent to 1. So the order of 3 is exactly equal to 2 to the 2 to the n which is fn minus 1. Well the order divides phi of fn by Euler's theorem. And since the order is fn minus 1, the only way this can happen is that phi of fn is equal to fn minus 1. So fn is prime. So we see that fn is prime is equivalent to saying that 3 to the fn minus 1 over 2 is congruent to 1 mod fn. And as I mentioned earlier in earlier lectures, this identity here can be checked reasonably easily on a computer even if fn has about a million digits by repeatedly squaring 3. Okay, that's all for quadratic reciprocity this lecture. As I said, next lecture will be about the Jacobi or possibly Jacobi symbol.


At Appalachian Wireless, all smartphones are 50-100% off retail pricing for back-to-school. This includes all smartphones, so don't be tardy. Don't miss the bus. Get to Appalachian Wireless today. Two-year agreement required excludes outright purchase and advantage plans, while supplies last. The first day of classes in the Floyd County school system is this Wednesday and today all of the faculty and staff district-wide gathered at the Mountain Arts Center to get ready. It has become a tradition in Floyd County for all of the staff and faculty to gather at the Mountain Arts Center before the first day of classes for a district-wide pep rally. We're all one team. Nobody's more important than the other. We're all one team. That's from the top to the bottom. That's from me, down to my administrators, my teachers, my support staff, my bus drivers, cooks, maintenance, everybody. We're all a team and we do this for the students of Floyd County. And to say there was excitement in the air would be an understatement. I have never seen anything like it. There's so much energy and enthusiasm here. The mood took on a more serious tone after lunch when members of the Floyd County Sheriff's Office talked to the staff about ways to handle a school shooting scenario. We're going to present what's called a CRASE training. It's a civilian response to active shooter encounters. The message was one that educators have heard many times, but Sheriff John Hunt says this information cannot be shared enough. It's just like coaching a football team or basketball. That's why you practice. In law enforcement, that's what we do. That's why you go so long in training is that repeated over and over and over occurrence is how you get it into your system, into your mind of what you're supposed to do. And I bet you that most of them in their mind every day go through some kind of scenario, even before they come to work maybe. During the course of their work, I'm sure there's some thought that went through their mind about what if something happened, what would I do? The first AF class in Floyd County is this Wednesday. In Prestonsburg, I'm Shannon Deskins, The KB News.


You know, everyone always talks about, oh, the winter is coming, right? Because we like to sound like we're cool, like in the Game of Thrones thing. I've lived in the North my whole life. And let me tell you, I know the winter. Hey everyone, Dylan Schumacher, Citadel Defense. And today we're gonna talk about winterizing your kit.  A couple notes here. One, you're gonna carry more stuff in the winter. There's just, there's not a lot of way around that, okay? It's colder, you need more layers. So you have to carry more stuff. That doesn't necessarily mean it weighs a ton, but you do need probably a bigger pack. So I'm a huge fan of the yote pack, but when it comes to the winter, I'm just, I'm sorry, the yote pack isn't gonna make it. I'm gonna up my game to like a 24 hour pack, not because it's gonna sustain me for 24 hours, but because I need the room in order to be able to keep the stuff that I think is important to have when it comes to winter time. So I went out recently on a patrol and the first snowfall of the year, it was like 20, 25 degrees out, whatever. And for the most part, I was pretty squared away, but I definitely thought about it after, and I thought there are some things that I'm going to be sure that are just live in my pack until all the snow melts and it's warm again.  You're always gonna be cold, because it's cold, and you got a good chance of getting wet, and then you combine those and it gets much worse, right? So there are just some items that I think you should always have in your pack as we go into the winter. Now, this is primarily for my friends north of that Mason-Dixon line. I will be honest, I grew up in the state of Minnesota, and I am convinced that there is winter in Minnesota, maybe North Dakota, maybe parts of Montana, parts of northern Wisconsin, and then like everything else is a second rate winter. I don't live in Minnesota anymore. I moved just barely south and in South Dakota, and winter's more mild here, okay? It's just not as big of a deal. So for all my friends that are even further south, right? You're down in Nebraska or Missouri or Georgia, God help you. I'm sorry, but you know, again, my friends south of that Mason-Dixon line, you don't know what winter is. You don't know what cold is. Now, I'm not saying it doesn't get cold sometimes and maybe it gets below freezing every once in a while, someone in the south is gonna screw you, Dylan. But my point remains the same. You don't have the duration of cold, right? I'm talking about weather where it gets to zero degrees and stays that way for weeks, okay? Because I've lived through that. I've grown up in that. To me, that's what winter is, and these other things just aren't as cold. Doesn't mean they don't have their own challenges. If things are heating up to thawing during the day and then below freezing at night and it's doing that seesaw thing, that presents some really unique challenges, like not getting wet, right? That can be a real problem in the field long-term. But by and large, I don't think that, I don't consider anything outside of that deep cold to be real winter to me, but that's just my own personal bias and I'm acknowledging that at the forefront. So that's enough rambling. Let's take a look at some things that you should just have, I think, in your pack until the snow melts. Here we go. Okay, first things first. You need to dump the water bladder. I'm a big fan of water bladders. I love running water bladders. I would prefer to run a water bladder. But the hose that comes over the sleeve or whatever out of the water bladder is what freezes. Now, I know some of you guys might have some systems that are like, you know, make sure you're always drinking on it or whatever to make sure that hose doesn't freeze and hey, knock yourself out. If you got a system, don't let me ruin it for you. But again, deep cold, I have found that that thing will just freeze up the moment I'm not using it. So you gotta run a real canteen preferably, you know, as wide of a mouth as possible to help prevent these from freezing. And eventually, you know, this is gonna freeze being on the outside of your pack, right? So again, if it gets into a deep cold, you're talking about like keeping one of these next to your body so it doesn't freeze. You know, maybe stuff in some hand warmers in here. Like you're gonna have to do some other things, right? But at the bare minimum, put your water in water bottles. That's gonna help it not freeze. You could also take this pouch and invert it, right? So that when it does freeze, it freezes on the bottom of the canteen and not on the top so you could still drink it. Again, depending on how long you're gonna be out, what you're doing, you gotta do some special stuff to try to keep your water from freezing as much as possible. But bare minimum, start running canteens in the winter, okay?  It doesn't actually all necessarily go in the pack. First thing I got in here is I have a set of gaiters, okay? I have a set of waterproof gaiters. Now, again, these aren't living in my pack. These are actually gonna get wrapped around your boot. That's what happens, okay? This is where your heel goes. This goes under your boot. And then this comes around into the front of your boot like that, okay? And then this is just a waterproof lining of some sort and helps keep the water off your shins. Big fan of the gaiters, particularly again in the winter, they're gonna keep your lower legs dry, keep from getting snow, getting kicked up, dirt, mud, whatever. So I think gaiters are definitely a must have in the winter. I have mine in green, you know, I think a coyote brown or a multi-cam would be the best color, but whatever, it's what I got, you do you. I just got these off Amazon. I will drop a link in the below if you want these. Otherwise, you know, there's tons of military surplus ones out there, right? The second thing is a good pair of socks.  If I can find the link on Amazon, I'll put these in there too. But I like the over-the-calf sock because, again, if you're running a solid over-the-calf sock like this, you're running the gaiters, you're running some knee pads. You don't really need to wear long underwear pants unless it's, again, deep cold for a long time. You don't really need to do that. You can get by with just normal pants provided you have a way to keep them from getting wet, which that's a different discussion. But for insulation, we're talking about an over-the-calf sock plus some gaiters and some knee pads.   So you should be pretty warm there. But a good, solid pair of socks, whatever that means for you, I like these smart wool over-the-calf ones. Second thing is a balaclava, or in this case, I just have like a neck scarf. Okay, this is a Equix level two neck scarf thing. Big fan of this thing. Again, this will run me from 20 degrees on down. I'm gonna wear this thing. Just gives you some extra warmth. Keeps the wind off your neck. Keeps things pretty, pretty warm. So it's like a waffle top, but for your neck, okay? This is just some chintzy balaclava that I got from Amazon somewhere, just some polyester thing.  Keeps the wind off of you a little bit. Running it under a helmet is gonna be real easy because it's super skinny, okay? So that's cool to be able to do. I see that I have it inside out here. So that's nice to be able to do. But, you know, some kind of balaclava, like a lightweight, and then like a midweight, I think is a good call, okay? And these should, again, should just be in your pack so you can swap out when you're moving, stopping, resting, whatever.  Along with that, which should always be in your pack, no matter the season, honestly, is some kind of beanie cap, okay? This is my, this is just a green beanie cap that rides in my pack all year long. And it really should, it really should. This is a four seasons piece of kit, in my opinion. But a good beanie, that's definitely gonna be in your pack, probably on your head when it's winter time. The last thing is some kind of mitten.  My hands got cold, I was doing this the whole time, right? Trying to keep my hands warm. And I did make it through for a couple hours, no problem. My hands were cold, so I guess that was a problem. But I made it through, I didn't lose any fingers, they're all still here. But I did think, okay, from now on, my mittens are always riding in my pack until the snow melts. So I, these are just the Army Surplus trigger mittens, okay, you do your own flavor. But the thing I like about these is, I can run just the liner, right? With just the leather liner, this has got a waterproofing layer, so my hands aren't gonna get wet. I really like that, it's got the leather grip, okay? I can run the liner, I can run just the inner wool liner, which this is pretty warm, again. Same thing here, this will get wet, right? This is not water resistant, but this can fit inside my trigger area easily. You know, I don't have to run the whole thing. So I like the versatility of these for being able to run one or the other or both together, right, depending on how cold it is. I do have a US Army Surplus Arctic Wool Kit, right, which does not have the finger cut out. Those are for like, again, deep cold for a long time, like sub-zero cold. But for just normal everyday winter stuff, I think you're gonna be pretty good if you can run both of these. Or if you wanted to run like a regular set of combat gloves, right? And then you wanted to run that inside the liner, the winter liner here, you could do that. You got to mix and match things. So these are gonna stay in my pack, no matter what for the rest of the season.  That way, if you need to dump a glove, right, you don't lose it, because again, you don't wanna lose your gloves in the winter, that's kind of a big deal. If you're feeling in your fingers, or you start losing fingers, you are combat ineffective.   So I just have a couple sets of hand warmers that run in my pack. I didn't use them last summer when out. I may or may not use them in the future, but I'm always gonna keep a couple set of hand warmers in my pack, just because again, if I wanna stuff them in the water bottle pouch, if I wanna stuff them in my pockets, if I wanna put them inside my gloves because things are getting really cold, right? A 10 hour hand warmer is gonna help you out a lot. So there are definitely some benefits to that. So that's it. Those are just a few small items that I think you should have in your backpack or on your person till the snow melts. Hope that's helpful. Hope that gives you some ideas this winter. Get out there. Don't be afraid of the cold. You can operate and thrive in the cold and do so effectively.   You need more layers, whatever, but you can effectively fight and train to fight in the cold. Do brave deeds. End endure.


Well, I'd just like to add to what Nick and Philip have already said about the late Malcolm Molyneux who sadly died on Tuesday night. He was a marvellous friend of 40 years, an incredible clinician and investigator and a really marvellous and outstanding person. We're so sorry to have lost him. So my title is from the words of the former Secretary General of the United Nations, Kofi Annan, and I'd certainly never heard of this particular crisis of public health before I began to work in West Africa. I went from Hammersmith Hospital to a new medical school at Amadou University in Zaria in Northern Nigeria in 1970 to study Epidemic Meningococcal meningitis. This was the dry Guinea savanna of Northern Nigeria. After being there for about 18 months, I had a really life-changing experience. I was on take midnight in December 1971 when a 50-year-old house of farmer was transferred from our country branch in Malanfashi about 55 miles away. The story was that three days earlier he'd been bitten by a snake which he called gajira while farming. He noticed a medium pain in the bitten part with some swelling. He'd treated himself at home using a tried and trusted herbal remedy, but after two hours the swelling had spread up his leg and after 12 hours he had pain in the lower back and abdomen and he was passing blood per urethra. He spent a miserable next two to three days at home feeling increasingly awful. He was faint and sweaty when he tried to sit up and he finally decided to seek medical help. When I examined him on admission, he appeared virtually moribund. He had a swollen tender ankle, he was very pale, he was globin only 2.5 grams per litre, low blood pressure with a rapid pulse and he fainted on sitting up. He had a distended and tender abdomen and sure enough there was a drop of blood at his urethral meatus. Well I resuscitated him by putting him head down feet up and starting intravenous fluid and as one would with an unfamiliar medical problem I tried to get help from my medical colleagues but was most surprised that none of them seemed to know anything about snakebite which raised the question was snakebite really so rare in this area? I made then a rather naive observation. I'd taken blood for cross-matching into a glass vessel and after 30 minutes I thought funny it hasn't plotted yet so how am I going to get some serum? I knew that there was an antidote to envenoming called anti-venom but our pharmacy only had one vial from the pasta anti-venom I think from their museum it was desiccated and long expired. Well tragically this poor man died seven hours after admission before blood was available for transfusion it's an awful experience to sit with a patient and preside over a death from hemorrhagic shock and the autopsy revealed really extensive bleeding in every part of the body so this tragic case raised a whole lot of questions first of all what on earth was gajira the snake how important was snakebite in Nigeria was this just a rare one off and what could be the pathophysiology the mechanism of such disastrous envenoming which venom toxins might be involved and were there specific antidotes or anti-venoms available in Nigeria if so how effective and safe were they? Well I quickly found out which snake this was this gajira was the one of the West African carpet vipers now called ecus romani it's not a particularly impressive looking snake it's really more than about 30 or 40 centimeters in total length and it's sort of earth colored it's certainly not dramatic I then did a sort of anecdotal epidemiology survey I asked absolutely everyone I met about snakes and snakebites you can imagine what a bore I became and I discovered that in many rural areas of the north of Nigeria people had lost close relatives to snakebite in recent years it was clear that snakebite victims didn't bother to go to hospitals or dispensaries unless they could expect to get some effective treatment there such as anti-venom and this probably explains why there no one in our hospital seemed to know anything about snakebite the patients just didn't come because they quite sensibly realized that there was nothing there for them I did discover from my sort of anecdotal survey that there was a hospital a former Sudan interior mission hospital up in the northeast in Kaltungo where it was reported that half a dozen or so snakebite patients turned up most evenings very appetizing for someone looking for a suitable site to do clinical studies of snakebite this was this very attractive area of Kaltungo the village is seen by Tangali Peak there and this is the hospital a fairly simple African district hospital well on the clinical side over the next few years working for periods in Kaltungo hospital I saw a lot of patients and I learned a lot about the effects of invenoming in patients most of the victims seem to be have been bitten by carpet vipers and certainly most of the deaths reported from the area were attributable to carpet vipers so you here see here some of the clinical effects of invenoming from the local swelling and blistering to bleeding spontaneous bleeding from the gums the local effects which can end up with necrosis requiring surgical intervention debridement this boy has got a subarachnoid hemorrhage and you'll see what a predominance of children a preponderance of children there are among among these patients well with the help of laboratory colleagues in in Liverpool school of tropical medicine and elsewhere we were able to develop some idea about how the venom of the carpet viper could cause such an appalling hemorrhagic diathesis as in the fatal case that introduced me to this topic first of all the venom contains some procoagulant serine proteases which stimulate the clotting cascade eventually leading to production of fibring which is instantly broken down by the body's fibrolytic system a second antihemostatic effect are these hemorrhagin or zinc metalloprotonases which damage the endothelial lining of blood vessels so this electron microscope microscope picture this is the lumen of a small blood vessel and here is an erythrocyte spurting through the junction of two adjacent endothelial cells opened up under the effect of a snake venom hemorrhagin and this shows the composition of these metalloprotonases which I'll come back to later and the third very important antihemostatic effect of carpet viper venom is on platelets the c-type lectins activate and inhibit blood platelets so all these three mechanisms acting in concert could produce fatal hemorrhage well more recent techniques such as the application of proteomics to toxinology has revealed a much more complex structure of well all snake venoms including carpet viper venom see that on reverse phase HPLC separation there are at least 43 identifiable peaks and in this schema of the proteome or venome of carpet viper venom you see that the bulk of the venom toxins are zinc and zinc metalloprotonases of four different classes and the known effects of these metalloprotonases include damage to capillary basement membranes causing local and systemic bleeding they also damage muscle locally and systemically and they cause blistering and edema they inhibit platelet aggregation and they also have a pro-coagulant activation of factor 10 contributing to the coagulopathy well it was quite clear from our studies in kaltunga that there was something of an anti-venom crisis certainly in Nigeria and through correspondence through the west of Africa our small observational studies showed that at least one anti-venom that could be obtained on the market this one was made in South Africa the South African Institute of Medical Research was highly effective in neutralizing and reversing effects of carpet viper venom but unfortunately it was too expensive and not widely available in those days in the 70s the import of South African products was complicated by the apartheid business a new anti-venom was needed but how did one go about this well a colleague of mine at the Liverpool School of Tropical Medicine David Thiekson and I decided that we would go public on this so we wrote a letter to the Lancet entitled a crisis in snake anti-venom supply for Africa and I'm glad to say that this was seemed to be widely read and we also approached many international anti-venom manufacturers different countries Europe and so on to consider developing a new carpet viper anti-venom so how do you go about producing an anti-venom well first of all you need to catch some snakes of the right sort so this was our team of snake catchers in northern Nigeria looking for carpet vipers then you need to milk venom from the snakes and then you hyper immunize some cooperative horses with increasing doses and from their plasma you refine immunoglobulin and then it's ready for intravenous preparing the drug which is given by intravenous injection to the snake bite victim we were extremely lucky to fight to get support in Nigeria from a very sympathetic um minister of health professor Oleg Koyuransakuti who was a former professor of pediatrics extremely helpful and a senior member of the federal ministry of health Dr. Absolami Nasidi and crucially we attracted the support of two very good anti-venom producers one in the United Kingdom Microfarm who raised their anti-venoms in Welsh sheep and another in Costa Rica and with their help we designed a new anti-venom we tested it pre-clinically in the laboratory and we carried out a large non-inferiority comparative trial phase one and two to three and we then encouraged the manufacturer and distribution of two new carpet viper anti-venoms west Africa and this shows the sort of team very important to get local support this is the chief of Tangali the traditional chief Islamic chief of this area with Tangali peak in the background and colleagues from from Liverpool David Theekston and from from Nigeria and professor now professor Abdul Razak Habib who helped coordinate the trial in Nigeria well after Nigeria I went back to Oxford for a while and was then given the opportunity to start a new unit in Thailand as you've heard from Nick Day this was the Welcome Mahidong University Oxford Tropical Medicine Research Unit so I moved from snowy Oxford one winter to to Bangkok and became very interested in the occupational problems of snake bite amongst particularly rice workers in the central rice growing area of Thailand I was working in eastern Thailand actually it was the site we'd discovered to work on cerebral malaria that was the main subject of my research in in Thailand at that stage in Jantaburi when I admitted a 13 year old boy who'd been bitten while he was asleep on the floor of his house in a rural area near Jantaburi and the snake was killed and I could identify it it was a Malayan crate quite a large snake over a meter long here are the marks made by the upper and lower jaw teeth on his thigh these are the marks made by the venom fangs within three hours he was showing early signs of neurotoxicity of interruption of neuromuscular transmission caused by pre and postsynaptic neurotoxins in the venom see he's been in to go a bit dusky and cyanosed as his respiratory muscles are involved after a further hour these symptoms are worse he's clearly got facial paralysis now there's descending paralysis of muscles innervated by the cranial nerves and at this stage he's unable to open his mouth and protrude his tongue and we've intubated him when he was unable to breathe and this is at nine hours and here he is being manually ventilated he was manually ventilated for 49 hours before he could be weaned off this assisted ventilation I'm glad to say the outcome was very good here he is leaving hospital after six days but this was a tremendous surprise because no one seemed to know about this snake we decided to undertake a national survey of this to find out what sorts of snakes were biting people in different parts of Thailand and we were just using the dead snakes brought in by patients that had been bitten by these snakes at these 80 different district and provincial hospitals we collected the dead snakes over a period of about two or three years to our surprise we found that 13 out of 46 fatal cases where we had the dead snake as evidence of causation were caused by this pretty well unknown snake the Malayan crepe the same one who'd been who'd bitten that 13 year old boy the snake seemed to be virtually unknown possibly because it's an exclusively nocturnal snake and there was no antivenom available because as I said it hadn't been recognised as the important cause of snake bite the survey brought to light another problem in the central rice growing part of Thailand shown here dashed in red there were three different snakes green pit vipers rustles viper and Malayan pit viper that all caused the same clinical syndrome of combination of local swelling with bleeding and carigulopathy third and if the patient as in the majority of cases the patient wasn't able to identify the snake that had bitten them it was very difficult for the clinician to know what to do because the antivenoms available at that stage back in the 1980s were only mono specific mono specific for each of these species these antivenoms did not have cross neutralization of other viper venoms so you can see the difficulties a matter of guesswork based on inadequate evidence fortunately the results of our research became known to the excellent national manufacturer of antivenom the Tyre cross society based in the beautiful Queen Sarah Palmer Memorial Institute in Bangkok and they were encouraged to produce a polyvalent to cover the three different viper venom so rustles green pit viper and Malayan pit viper the clinician no longer had to guess he or she could use this polyvalent to cover all three and in the case of the Malayan crate they not only produced a mono specific antivenom to cover this newly recognized major cause of snake bite death in Thailand but they also combined its venom in production of a neuro polyvalent antivenom that covered other neurotoxic species such as the common cobra and the king cobra well I was very keen to go to Burma because I knew that from pre-independence days from the 1930s Burma was notorious for its very high rates of snake bite mortality do you see here in these black areas at 16 or more deaths per 100 000 inhabitants per year caused by snake bite and I got the opportunity in the early 1980s to collaborate with the Department of Medical Research in Yangon which was a short flight from Bangkok and to start a research unit combining work on snake bite and malaria in this township medical hospital Thayawadi north of Yangon so here's a fairly simple colonial hospital serving a paddy growing area see the the rice farmers highly exposed to snake bite as they particularly when they gather the crop the paddy crop bare footed and bare handed and I was supported by a very strong team from the Department of Medical Research led by its brilliant director Dr Antan Bhattu the main problem here was Russell's Viper which was believed to be responsible for almost all the bites and deaths in the central area of Burma and this is a typical patient of ours during the work we did in Thayawadi this rice farmer bitten while he bitten on the foot while he was working in the rice fields and he collapses he's brought in unconscious hypotensive and the research team here gathered around giving him anti-venom and taking baseline blood samples and here is the the worried neighbour of his giving helping us with the clinical history well some of the effects the devastating effects of Russell's Viper in venoming are illustrated now fatal cerebral hemorrhage disseminate intravascular coagulation involving deposition of fibrin in the lungs also in the anterior pituitary this is the a section of the adenobituatory causing acute and chronic panhyper pituitaryism most important development of acute kidney injury by various mechanisms including ischemia by the deposition of fibrin stayed red here in the peritubular vessels and finally a late development of the syndrome of generalized increase in capillary permeability revealed clinically by this sign of chemosis or conjunctival edema followed by hemorrhage in subsequent years I was able to pursue my interest in snake bite by working in Sri Lanka in Papua New Guinea Bangladesh and in various countries in in Latin America and I certainly confirmed the idea that snake bite is an utterly fascinating and clinically challenging problem but how important was it was it really as Kofi Annan had suggested the biggest public health crisis you've never heard heard of the problem is that estimates of snake bite morbidity and mortality tended to be based largely on hospital records and as we know in rural areas of low middle income countries snake bite deaths often occur at home and uncertified undocumented so what was urgently needed was a community based survey to try and make a stronger case that snake bite was worth taking notice of and worth considering as a disease of public health importance I was very fortunate in Oxford I've been talking to Richard Pito about my interest in in snake bite and he introduced me to Dr Prabhak Jha of the University of Toronto who had helped to develop the registrar general of India's million death study which ran from 1998 to 2014 this was this was reckoned to be the largest epidemiological survey based on community studies ever attempted and it wasn't designed for snake bite of course it was designed to look at the health burden of tobacco related diseases and malaria and various other diseases but I managed to persuade Prabhak Jha to include some questions in his in his analysis dealing with snake bite and the cause of death in this study was based on verbal autopsy which is a potentially a controversial technique this involves questioning relatives and neighbours of the deceased to identify the cause of death and it involved nearly seven thousand randomly chosen sample areas throughout the whole of India each one about a thousand people each and this covered the whole country it was independent of hospital under reporting here are the people questioning relatives and the results were really quite extraordinary deaths attributable to snake bite in India and by the way I think this attribution is likely to be reliable in the case of snake bite because snake bite is such a dramatic and memorable for mode of death that it's highly likely that relatives and neighbours will remember anyway the estimate was of 46 000 snake bite deaths in India in the year 2005 these are the 99 percent confidence intervals so snake bite caused one death for every maternal death in India and for every two HIV AIDS deaths a lot were in children and the this estimate was more than 20 times the official government of India's figure based on unrepresentative hospital data and because it was a nationwide study it was possible to see the relative burden of snake bite in different states of India and therefore deploy scarce research resources more appropriately these data helped to persuade WHO to recognise snake bite as a priority neglected tropical disease and subsequently to persuade the welcome trust and other international funding agencies to make generous provision for snake bite research the update of the million death study which was published last year suggests that the number of snake bite deaths in India is has been as high as 58 000 a year during this period amounting to 1.2 million snake bite deaths and was increasing so I believe that these data have vindicated Kofi Annan's suggestion that snake bite was the biggest public health crisis you've never heard of thank you for your attention


Thank you for the introduction. So I want to start with a few words of motivation. And in the last decade or so, or 1.5 decades, latest-based crypto has become very popular. And if you search for reasons of why that is, people usually say you'll see a combination of the same reasons, which is usually a combination of the following. On the one hand, lettuces are very powerful. They allow us to construct things that we don't know how to do otherwise, for example, for your momorphic encryption and IBEs and things like that. Furthermore, they are at least up to this point believed to be post-quantum secure. Finally, they also enjoy some very strong guarantees in terms of average case security, which stems from worst case to average case reductions. And they also allow for simple and efficient implementations because in the end, it's just usually matrix vector multiplications over relatively small integers.  Well, there's a caveat here. And this caveat is the discrete Gaussian sampling, which is an operation that is part of many lattice-based crypto schemes. And when it comes to discrete Gaussian sampling, I would say you can have either simple or efficient, but not really both. And this is what our work addresses. Before going into detail about how we do that and what we do exactly, I want to quickly define what the discrete Gaussian sampling is. So discrete Gaussian sampling is our algorithm that samples from a specific distribution. And this distribution is a discrete Gaussian. First, we define the Gaussian function as e to the minus p x squared. That is the standard Gaussian function. And you can define a scaled and shifted version of it by defining or giving a parameter c and a noise parameter s. So c is called the center. S is usually the noise parameter. And you just shift and scale the distribution, the function. And the discrete Gaussian is then simply a distribution that is proportional to this Gaussian function but restricted to a discrete set. In our case, it's going to be mostly the integers, but you can have other sets there. And I've visualized this distribution here, like these are your elements, right, on the x-axis. And every dot corresponds to the probability of each of these elements. And you get your typical bulk curve here. Note that the center does not have to be an integer even if the distribution is restricted to the integers. And in fact, you can view discrete Gaussian sampling as a rounding procedure that rounds the center to a nearby integer corresponding to these probabilities. Now, where do we encounter the discrete Gaussian in that space crypto? Well, it usually comes to us in one of two settings. And one setting, which we call the fixed setting, the parameters of the distribution are fixed. So the center S and the noise parameters, the center C and the noise parameter S are fixed once and for all throughout the system. And this is used in most LWE-based schemes where the center is zero. If you are familiar with LWE, learning with errors problems, the errors usually follow this distribution, the center discrete Gaussian with a fixed parameter S. Now, in the other setting, which we call the generic setting, both parameters, the center and the noise parameter, can be variable. So they vary per query. So when I asked for, when I asked the algorithm for a sample, I specify the center and the noise parameter and I want to get back a sample from that specific distribution. Yeah, from this distribution that is defined by this C and this S. And the most prominent application of that, of that setting is lattice trapdoor sampling. And lattice trapdoor sampling are very popular in more advanced schemes of lattice-based crypto, usually for encryptions in the, for CCA secure encryptions or signature secure in the standard model or IBE schemes, etc. So this is where lattice trapdoor sampling comes in most of the time. And we have actually quite a few algorithms for the fixed setting. So in the fixed setting, there are several algorithms that achieve different time memory trade-offs. And they usually achieve that by doing pre-computation based on this, the center and noise parameter, which are fixed, right? They are fixed. So you can do pre-computation and you can store information about this. And the most efficient algorithms, for example, they store all the probabilities for every element in your support of this distribution in a table. And then your sampling just becomes some sort of randomized lookup into that table, right? And so they store information that is linear in the noise parameter. So this is good for small distributions. As the distributions grow wide, this becomes impractical. But there are different algorithms that achieve different trade-offs. In the variable or the generic setting, we don't really have that up to this point. And you can see kind of why, because if you don't know the center and the noise parameter of your distribution, then what are you going to pre-compute, right? And in our work now, what we actually do is we reduce the generic setting to the fixed setting. So we'll exploit algorithm for the fixed setting in order to generate samples from arbitrary distributions. And before I go more into detail about how we achieve this, I want to go over the structure of the algorithm and tell you about why we think that is a good idea. So the high-level overview of the algorithm is going to be that we start with two fixed samplers. Here, we're taking samplers over 2Z with a center 0 and 1. Alternatively, you can think about them as being samplers over Z with a center 0 and 1-1-2. It doesn't really make a difference. And these don't get input. They just produce samples from their fixed distribution. And then our algorithm is, oh wait, no, yes, sorry. Our algorithm just takes these samples, gets us input the center and the noise parameter, and then cleverly combines these samples from the fixed distribution in a way to produce the correct distribution. And why do we think this is a good idea? Well, on the one hand, we can ensure that the noise parameter of these fixed distributions is going to be relatively small, or actually quite small, it's just a constant. And so we can take advantage of the most efficient algorithms for the fixed setting, these are fixed distributions, without spending too much memory. And so this is going to make our algorithm quite efficient. Furthermore, we are not restricted to two samplers. If we have more memories to spend, we can add more samplers, and this will make our combination phase actually much more efficient. So this is where we get a time memory trade-off for the setting of generic sampling. That's actually the first of its kind. Furthermore, we see that these samplers don't get any input. They are completely independent of the C and the S. This means you can split the algorithm up into an offline and an online phase. The offline phase simply produces these samples. You can pre-compute them or store them somewhere, and then the online phase just combines these samples together and using very simple arithmetic. And so the online phase of our algorithm is actually extremely fast. And so this allows you to split this algorithm and, for example, just do pre-computation and store it on a device. For example, if you have a small device, you can just store your samples there. Or, for example, you have a web server that has idle times where you can just produce them and the web server is not doing anything else. Or you can actually separate the algorithms in two separate systems, where this is done, for example, in a hardware module that is specialized to the setting. And we have algorithms that run really fast in hardware for the fixed setting, not so much for the generic setting. And if you do this in parallel, well, then, again, the offline phase is basically for free. And last but not least, this we insure actually, or our algorithm naturally ensures that every output sample of our sampler uses the same amount of base samples. So the input for every query that we give to our sampler, the number of base samples that it consumes is exactly the same amount. And actually, the number of steps is naturally the same amount. So the online phase of our algorithm is sort of naturally constant time. And if you implement the arithmetic operations in the sampler in constant time, you immediately get a constant time online phase and then separating out the offline phase or sampling these in large batches will give you very easily a constant time algorithm without paying a large penalty in efficiency. And that is actually quite unusual for discrete Gaussian sampling, which has been traditionally hard to do in constant time. And yeah, so there you have it. That's the three adjectives that we claim the paper is our sampler is generic. It can be implemented very efficiently. And it can also be implemented in constant time without much, much overhead, hardly any overhead actually. So now I want to talk a bit more about how we actually achieve this and where these time memory tradeoffs and this offline online phase comes from. So our main tool is going to be convolution.  And they all kind of have the same the same flavor. You start out with two or more base distribution. These are fixed. The one and D two and you produce a sample from each of them. And then convolution theorems tell you that you can combine them in specific ways to generate a different distribution. So if you combine the samples from these distributions, your output is going to be a different distribution. And you can see how this like might help us, right? If we have like fixed distributions, if we combine them in the right ways, we get out different distributions. Now, getting out the correct distribution that we actually want is not trivial, but you actually requires a lot of work. Otherwise, this wouldn't be a crypto presentation. But so it's not entirely new, this idea. So it has been used before in the fixed setting. We call that the most efficient algorithms require storage, linear and the noise parameters. So if you have a fixed distribution that has a large noise parameter, you can use this convolution to reduce the memory overhead to produce samples from a from a smaller distribution and then combine them into a big one. And that has been used before. We generalize this idea a little and analyzes in the more general setting. And we use a similar technique to make sure that our base center have small noise, right? And so this shows that we have some leverage with regards to the noise parameter. What I want to focus on in this talk, though, is the second parameter, how we handle how we handle different different centers that we get as input. And for that, we call that the goal of or the view of discrete Gaussian sampling is that you get a center and you try to round it to a nearby integer. But instead of doing that in one step, what we're going to do is we're going to round the center step by step to a coarser and coarser grid until it is in the like an element in the integer. And this is going to be the output sample. And each individual step, we're going to make sure that this every individual step is being rounded by a discrete Gaussian. And then the convolution theorems are actually going to tell us that the final result is actually also going to be a discrete Gaussian with the correct center. So I know this is a little vague, but I unfortunately don't really have time to go much more into detail. This is just to give you a sense of how the algorithm works. And so now the question is how do we do every individual step just using our fixed number of base samples, just using two base samples. And well, the idea is we assume that C, like our center that we're giving the parameter, is an element in Z over 2 to the k. So it has a k bit binary expansion. And our goal is for this step to round it to a center in Z over 2 to the k minus 1. So we want to round just the last bit by a discrete Gaussian. And we do this by sampling our base, or drawing a sample from our base sampler with center defined by the bit, the last bit in the center. And we draw the sample, and then we add the center back to it and scale it by 2 to the k. Now note that x is actually a sample in 2Z. So it's not actually in Z, it's in 2Z. And so x plus bk over 2 to the k, the last bit of the new x is actually going to be also bk. Because x is an even number, so bk is 0, x remains even, if bk is 1, x is a not integer. And then if I scale it by 2 to the k, the last bit is going to be exactly bk. And so if we subtract it from C, the last bit of C is going to be 0. So C is actually now going to be in 2 to the k minus 1, which was exactly the goal. And this is actually a valid discrete Gaussian rounding. And so we do this step by step, and until our C is actually going to be an element in Z, and we get exactly a discrete Gaussian with the correct center. OK, now where do our time memory trade-offs come from? Well, it mostly comes from the fact that you don't have to express C in binary, you can express it in different bases. So for example, if you express it in with regards to base 8, for example, then this means you have a third of the digits. Like every three bits are going to be transformed into one digit in base 8. And then you can round every digit individually, and you're only going to make a third of the steps. But now you need samples not over 2Z, but you need it from 8Z, and more so, you need it for every possible coset of 8Z. So you need 8Z with centers in 0, 1, 2, up to 7. So you need seven samples, eight samples, which you need more memory to store these efficient samples, but your combining algorithm is going to run in the third of the time. So there is a time memory trade-off. The constant time algorithm essentially stems from the fact that no matter which center we get, we need the same number of steps. And this comes from the idea that we can assume that the center has a finite bit expression, no matter which base you use. And the fundamental idea of why we can assume that is that we don't actually need to necessarily produce the correct output distribution, but it's OK if you just approximate the output distribution, the ideal discrete Gaussian. And most algorithms actually do that. Most algorithms don't produce the exact distributions that will produce an approximate distribution. And this is usually good enough. But good enough, you have to kind of quantify, right? So there are several tools out there to quantify the security to approximation trade-off. And the most classical one is the statistical distance, which has been classically used to evaluate how close you need to be to the discrete Gaussian or to preserve security. And the statistical distance is actually a very nice tool to use in the analysis, because it has a simple definition. You can get easy bounds on it. And it is a metric, which makes it very easy to analyze even more complex algorithms that involve a lot of steps that can lose distance to the ideal distribution. So this is very nice. But more recently, the KL divergent has becoming more popular, or other divergences actually. I'm choosing the KL divergent as a more popular tool, but other ones are possible. And KL divergent, as the name says, is not a metric. So it's a little harder to use. But if you do use that, you get actually a much stronger security proof out of it. And one of the killer arguments for the KL divergent is that in many settings, you can get away with just computing with, for example, 50-bit floating point numbers, and you get more than 100-bit security out of it, like a bit level of more than 100 bits. And that is, if you think about current hardware or more, if you think about current computer architectures, that is a very strong argument for using the KL divergent, because that gives you an order of magnitude speed up versus multi arbitrary bit precision numbers, which you would require for 100 bits of security if you were using the statistical distance in order to analyze your distribution. And so we wanted a nice tool to analyze our algorithms, and we also wanted strong security. So what we did, we were hoping to try to get something the best of both worlds. And we ended up defining our own metric, because we didn't find one that suited our needs. And this one has a pretty simple definition. It's just the infinity norm of the difference of the lux of the two distributions. And as it turns out, this is a metric. You can see that because it's just the version of the infinity matrix, or it's an infinity norm of a function of the difference vectors. And then you also get the strong security bound. Actually, we show that in the paper. So showing that this is a metric is actually not that hard. Showing that it has strong security properties is actually a little bit more involved. And we do that in the paper. And then we use this max log distance in order to show that our algorithm actually achieves good approximation even for floating point numbers. And you get strong bounds on the max log distance, because in the regime where they are very small, it's essentially equivalent to the relative error, which is exactly what floating point numbers give you. So if you have a 50-bit floating point number, then you exactly get an approximation error or relative error of 2 to the minus 50. And then your ML distance is also going to be pretty much 2 to the minus 50. OK. This is all I actually planned for. But I have a few more minutes, so allow me a couple of remarks. First, in a follow-up work, actually Thomas Place showed that by relating this max log distance to different divergentines, like runny divergence, that our algorithm actually has much stronger security properties even if you restrict the bit security definition a little bit. And also, if you're interested in our algorithm and more in a practical sense, we do have a reference implementation on my website, Google My Name and UCSD. And you'll find it. OK, now I'm happy to take any questions. Thank you.


Going on everyone Sam here with late in sports cars been 23 Bowman draft baseball Super Jumbo six box case number three random team style look again at your random results As always you can find these on the website under the results tab as well as the link in it chat So good luck here everybody Kyle's actually a Miami Heat fan Miami Heat fan is Is Kyle? Now he's a it met what you magic rays bucks and lightning. Yeah, all the Florida teams dude this guy really This guy now 13 I know I saw that 13 to go on the Ten box Tuesday a lot of Bowman. Oh It's nine boxes of Bowman from different years in ten box plus a box of definitive So a lot of potential in that 13 to go well over halfway now I'm in there we go. I'm in on that chaos Got Jeffrey H with a one-in-one spot. Thank you Jeffrey down to eight Luke M with a certified spot and Warren W Also with a certified spot. So thank you guys appreciate that eight to go on one-on-one basketball now Again teams on sale and NT football as well biggest teams luckily Pittsburgh Pittsburgh Atlanta and the Jets are the biggest teams still left in NT They're all on sale already as well. It doesn't mean what you think it means Box code You should come out face Like it says It's a code real worried real worried of the Brain trust of the two of you That's right. Paul a lot of fun last night for sure. I'm That is a jet Williams jet the met bird. Oh, wow. It's hard. Oh Yeah, dude I know sorry Shane.  Yeah, he's the He had the most ever right Joe Redfield season. I think it was a straight kicks one of the two Think it might have been in a row. He had the most Jesus now he's saying Face red droopy eyes hand pink waving face orange frowning. I got you can't Funny guys Sam don't know what that means, but I got you can't there Legal stole my body legal did steal his box number. Dang. That's kind of messed up. You boosted it. It's kind of messed up sick bird Yeah, never Bertot was a little brother's one who bit the turtle in half 99 Brady Smith, huh? Yeah, when where it was outside some for a house. There's a video him in the Titans, he was a bit of turtle in one 99 Drew Gilbert. That's odd Four night current time for a night cruise all over the place.  Nicholas S with the Rockies and a couple of jumbo Cases Yeah, they haven't they've probably lost a bunch. So they're probably very Disappointed in their in their performances So yeah, they're not ready to get wrecked quite yet K-repped by us here in person bots that is Hunter Holland to at 199 the Reds Printing plate is a d-back. It is Christopher Toran. Nice. Nice one there one of one printing plate again for the Where's that plate action? Absolutely. Oh, he's in on that Valdez don't head no Diaz Yeah, all right Luke Schlegger looks Gordon out climbing as on Zonatella first base auto for the Red Sox base and Steve Young bucks. I'm in on that. That would be pretty cool. Actually, it's always weird seeing the Steve Young with cream orange creams to cool It's a little yeah, Todd's not like a jump scare first not the best It's like seeing Brett far with that Probably one of the few bucks fans that do not like the creams, man. I'm really out Wow Johnny Farmello. Wow Wow, wow, wow Hunter Owen to 150 That is I'm I'm surprised on that. I'm not gonna be honest with you. I don't like the don't like the creams, man Deon Jorge to 499. I respect it. I get it especially if it's your own team I feel like you're more entitled to an opinion on it, but I like them Juanipa Blake Mitchell and Olson Alberto Rios. We got a sparkle of K. Denton 271. That's fair Paul. It's on that rocks It's fair Peter M with the gnats in the eight gnats in mixer angels and definitive Thank You Zoe's Peter Patrick with a 10 box football spot in Thomas B with a 10 box baseball down to 11 11 ago 10 box baseball ladies and gents 11 ago almost that single digit erronees Go on 10 box very nice appreciate that eight to go on one-on-one So one away from being over halfway sold out on one-on-one tiered ranking style. That is Pretty electric if you ask me pretty electric. It is Luis Juanipa Old school Bucks jersey and logo the old school logo is kind of lame The guy with the knife in his mouth. That's that's kind of odd. I don't like that one at all But I like I like the cream jerseys. I think they're clean Paul Wilson Foster Jacob Barry. Sorry Mac Horvath first base auto-save in sabayos Know what part of the box you were in there Run over there, man. You pay attention Now not until not until optic comes out again, we won't be doing them electricity electricity man, I just bought a trail on birds Did Did I did Lance for the certified spot? Thank you Lance Appreciate you guys guys are killing it right now appreciate that very much I got eight to go on one-on-one. Oops eight to go on one-on-one as well Let me drop you guys a link to that eight to go on one and one BKB Jeffrey H picking up wow bunch of spots. Thank you Jeffrey make a triple case tomorrow He's guardians and a couple of mixers as well. Jeffrey. Thank you as always buddy Keep it going. Jeffrey's first in queue with personal stay. I believe he has four Four bowman trap choice boxes thought it'd be fun again. Personals will start as soon as group breaks are over Obviously depending on when that is the reality 250 is flamboyant who knows Boom Ister Jorge McGraw Abner holiday and no auto sick Well, we'll keep a Keep a close eye. How many more we missed if any so we're at one right now. Sorry about that guys Shane What show are you at? Strat so rich for this batch of auto for McGraw Platinum auto nice deal any auto pretty color real damn. Wow. It's a nice stuff Very solid. Hi Shane. Love it. I've got some nice golden cards coming in this week Mari's thought of my RPI from exquisite.  That's so cool.  That's dope canler That's dope That's dope One like I wouldn't like fibers barely missed out on a dam on Andrew Jones. Damn That's a candler card right there Blake Mitchell Sparkle Gavin Cross Kevin sim to 150 true blue Peter M with the inks and definitive and three in the gilded mixer I think on that's on Thursday Yeah, thank you beer. Excuse me Jeremy W with a certified spot. Thank you buddy. Oops. I did the wrong the wrong pile for sorry. We're gonna see the auto first No suspense. Sorry. No suspense Maui Huna Good ham first base auto is CJ K this oh dang shame I Keri Iverson Garnett triple auto with Sam J right to fit it. Damn. Yeah What's it got? So I must have a good little payday on those so I have to imagine Makes out for the missing out on them for sure. Yeah Yeah, there's only new stuff too. So do you have any cards you regret selling green ret louder to 99 Nice one there on the transformative talent like not necessarily because like oh, they went way up in value But like cards you just like that. Yeah, you got a good price mine will always be Oh three upper deck Upper deck something on card Ken Griffey, Jr. I missed that. That's the only one that I'm like if I could go back and undo it I would undo it. I would undo that sale because I got I mean I got like triple my money on it, but I Remember packaging up. I was like, ah damn man. That was when I missed for sure Max Clark and a Sparkle of Ryan Clifford that is Vaterano to 199 They just have a pretty good sale on my Hero Wyatt Chris Clark Trey Morgan Rainenberg Keshel, do know Kate Denton first refracted at 499 for the Rockies Basin base on my I had a Josh Allen at the Jaguar. Is that Josh on a cracked ice? Contenders auto nice. I just sold that recently. He's a beast. Yeah, he's so good dude. I Sold it. There's a guy in Jacksonville actually the biggest Jags collector. I know dude. He's like I Mean any card you could think of of a huge Jags card. He's wild like I think his his goal I think he's got like six of them. It's to get all ten of the ETN gold rookies from prison.  Thank you Evan ten on ten bucks ladies and gents. Yeah, that's fair Shane Even if not your main PC still I'm gonna get rid of really cool cards. It's off sketch in a triple. Yeah, I feel that I feel that for sure Yeah, the two things I really never sell That is Christopher Torring to 125 first one is gifts of any sort any gift from anybody I never sell it I think that's just kind of messed up. I think that's like bad karma But if you if somebody ever gives me a gift it is like immediately I keep it no matter what it is Max Clark to 499 gold for Christmas Oh, what brick a gold? Then I might sell it. It's a brick of gold. I might sell it. You just got to keep it Put it on your mantle If you give me a brick of gold for Christmas, I will keep it in your honor Let's go Xander move Jason Woodward Jack Mahoney Cono Halloran Kate Morris Savakul Jake Cunningham type heat first base auto nice one I know be a very big brick, but The Lego brick of Lego brick of gold there you go and Then I'll be like any Raven like great. I'll never sell Any Ray any Ed Reed any T sizzle any flacco any bullware any Saragusa Nauta. Oh my god. It's all my boys Bold ins Yeah, no, that's what I'm sad just it's just a bad look if you sell a gift in life And I guess kind of messed up Justin Reimer to 250. I do have a couple of Kyle ballers But just for like fun. We're back the Ravens Draft There you go Shane I'm out of here. Get in there. Hey Shawn wall and my hea. So I'll keep on playing Mitchell first base auto Come out of here Colt Emerson glass right louder. It's Jake dude. He's go home. Oh, yeah, where's Jake? There's Donnie. There's Donnie. Hello, Donnie That sounds like an inside job It's on see Brian a tiny job. Yeah, I've seen that movie. How do you have? Wow? Christian napsick first base auto actually kind of surprising. Yeah, I like a good heist movie. Okay, so Yeah Yep Well that one. Yeah, I wish it was a lot of Oh nice Yeah, dude, what else you got? Pc time with Donnie. Yeah Yeah, I think so. Yeah Little silver James Cook nice field level Parsons nice. That's dope. Yeah, that looks cool I don't have any Isaac Bruce. I like it Terry Connery for the PC. Yeah older Cunningham. I'll have anything go be Dean. Nice That's sweet. That's really cool. That's that's really nice. I like it. That Michael looks pretty good. It's awesome. Yeah, nice Very good.  Hell yeah, Pat Ricard plays both sides of the ball, dude Jackson cherry oak gold draft picks and pros prospects Very nice, Richard J with a spot in certified Evan L with a spot a couple of spots in definitive breaks as well Brady Blaine's men shoe Him and getting hurt classic Rofan Brayden Taylor gold wave 250. There you go Tampa. I just went there at race Raise going to miles age good stuff miles. Let's go miles. Oh race. Hell. Yeah. Go race Expect much out of him anymore Be honest with you did Ricky Bradfield sparkle of Hacey's bias It's actually not a bad idea to do like staff member PC highlights Yeah, we'll get the inside the vault thing with a rich rich's PC once. Yeah, that was cool 499 Hans Montero We need the real cards. Yeah I doubt it. Jamar face was just a start. Oh, yeah Matt Shaw Homer Bush Jr. First base auto for the Padres. I'll bring some heaters for y'all I'll bring in a Bring in a keto briefcase. Oh, yeah Some tricks up my sleeve still Loved and seen yet You know time of small We're wasting all this paper for Right, I know Right over Paul Paul Pierce Yeah, that's a timeless moment. It's totally a timeless moment Ten to go ten bucks Tuesday, some people don't need some Paul Mills out timeless moments. That's what we need you can find one It's all you got to do is pull up a mid-range jumper. Boom. There you go. That's it, dude That is a time for some mid-range jump timeless moment is Just a random any random mid-range jumper from Paul Mills after here as a hawk I'll be good with a guy Paul Pierce NT auto attend nice. They go Shane. Oh nice Great and Taylor and a Adrian and Adrian Santana sparkle So we traveling for work Shane. Just knew there was a show where you were going brought some stuff with you Forester Adrian Santana first refractor out of 499 for the race Just want to race This is even splitter donate Tommy Troy and Noble Meyer green Rainer Arias tonight on the paper I Jacob Gonzalez first base other there is again Classic Jacob Gonzalez today Set up the show traveling this week of Jacksonville till tomorrow nice through your chain. No, I got you Shane Sam knows all about it. Mm-hmm All about it ever bank. Oh, yeah There's to 75 Rock Regio Like that ever bank is a winner the winner One time everyone there was the Raiders and Jags games, so I went out. I know I'm not It's not gonna win either right now to change not the same man going in and it's coming out Yes, that's a has families Raiders fans. Gotcha One of those games sort of Cox first base on it was on a day that day. Yeah, it was a warm one in Jacksonville Jacksonville day games To be in there, dude Get me out of the pool. Yeah, I'm out out so out on the pool. It's unreal Can't even stress to you how much how out I am. I'm very into the pool. Oh my god. That's so gross, dude Jackson bow me sir to 125 be on the whole game till I don't appear make a throw to the pool There's 499 Colson Montgomery steak Sam. Let's go to your bacon raffa-lays for boneless chicken breast something else No, I couldn't keep reading the entrees sides and desserts for 90 bucks and oh my first Yeah, it's gonna say give that to yourself. Anybody want to get me in Sam's mom. I think we are we are We're open to the air very very very open the idea very open the idea very in Ten to go on ten bucks Tuesday baseball everybody ten bucks Tuesday baseball ten to go ten tog oh One-on-one tiered is down to eight now. So almost Basically halfway sold out, which is awesome seven spots have come on in for that. There's a lunar glow Jake Cunningham Keddo drew Hackenburg to 250 on the purple nice one there for the Bravo Space and Base five To go and had one dude get a mix scan after the 225 if you come out Trout little boy on it. I try to convince you is doing you a favor. There you go. Yeah, you still Shane you still have that You still have that doomerville because that is a Raven great right there. I Love me smell this doomerville. He's still I still got that you still got that shame I know he insults that guy Lucas Gordon Still got that might be interested in that. I do love me some doom He's a beast in Baltimore for a few years Sullivan Wyatt Langford on the variation auto nice one there to 99. That's dope. That's Rangers Going to Nicholas M. Good stuff. Nicholas get that into a Mac for you buddy Time was moments dual suspension Trayman and John I do no, no, I'll buy it off you I'll buy it off you for sure Shane I Think I still have your email you email you after this break Chase Davis to 125 Let's go Shane. Oh, yeah, dude.  You need to set up broken some sales here I'm saying man Gavin cross the 499. Let's go Shane Dude, let me some doom, bro Yeah, that'll be that will be PC for sure Nibbins Paula Bush Max Anderson first base auto Well Jake Hey Jumbo. Oh, are you a man jumbo? All you know is a Weird that he's not yeah, I know He's not showing up right now. I'm shocked this Justice j4j j4j. I'm out of here You know it's jumbo Diaz. He just goes high Hi, it's true. Hello jumbo. Very very nice guy. Yeah Go ahead I Don't know why it gets banned to be honest, right? Like Lucas cord into 499. It's a mystery. Why is 24 jumbo even a thing? It's a great code code word J4j j4j you got a 24 First base auto Kendall George up Maya Jeremiah. He asked if you're recovered from the power surge on Saturday yet or not No, no, so gotta do laundry from it God just sitting there for the last five days. God. Good Lord kidding Kidding it was close though Power surge Jake Jakey surges out is a Kyfer Lord to at 250 Jakey surges he probably shouldn't search the power like that Jake Hackenberg to 50 is going to the Braves. I didn't do that. I didn't do that. Yeah, it was Donnie was top loading the router That's what happens. Yeah. Yeah. Yeah, you're trying to make the router. Yeah And the plastic just front it. Yeah Colton led better first base auto Nice one there. I have a good one for him, but I don't know if it's Better better better I would probably err on the side of waiting for a BRB screen Matt Shaw and Rainer rs. I'm a spark like in the stand though Yeah, it's been helpful to be honest keeping all the boxes out of the way Garrett Forrester refractor first auto before 99 for the pirates Here we go, I think he drives a super I would hope so Last box is great. Good luck everybody That's it that box lesson right there. Oh, what that box out the same like that. Yeah, look at it, dude It's got mess it up. It's a fist mark right there. That's all that's all the rage of just jumbo. Yeah Everyone that's all over the place I walked into you see she was the table that was out there at one point Bofa Dylan Chris Jaden and I happens a lot. Ah, dude. It's like I had to deal with it Some LBs right there.  Yeah, dude like a barn I think what she's figured out how much it would cost to ship both of Seven salt ebon Stick a stamp on it. I think you probably get both of the plain white envelope I probably get both out the door for like 64 cents It'll be label it'll be for us tomorrow. Yes for us to me. Is there any fanatics live tomorrow or no? Mmm, I don't think so. I don't think there is there. I think the only there's Thursday, we're doing it With me and for us and then I know I don't know don't know if we're still doing it, right? Supposed to on Saturday Paul Wilson to 499 refractor first auto. I know Thursday. We're doing it. Yeah Thursday for sure Maybe Saturday Yeah tomorrow morning is me and for us. It's the first. I haven't been on a Wednesday morning in Long The Zanzanatello and tomorrow Johnson 54 Bowman flag variation Yes, you can blame for it. So if you don't get any brewers, yes, you can please do please do actually How to work? Remember, I think we have some flask legia at the end of them. Yes flask legia at Bowman A couple serial numbers They'll be fun The key show to 199 will be feeling for dinner tonight boys Right Right pump it First base auto Paul schemes a lousy one there congrats on that to pirates You should get your t-bone and grill it up tonight Jake get you an Omaha steak. Oh, yeah, I got you. I Got you Sound of somebody who does not have me The exact sound Why we have schemes everywhere a lot of schemes today behind the scenes everywhere all schemes for sure schemes everywhere Chase Davis and Jack one injured I'd show you the Holiday remix No, thank you Lindsey AJ Ewing James Wood first base auto cam Fisher for the Stroze To turn tables in a microphone Right behind you dog right behind you dog Tell me about a PT cruiser. I just got a 20 bomb with a freakin lock. We get it 20 bomb Lockwood They may have a microphone Wow Skeens and like first sounds like a law firm that is Brooks Lee to at 99 Skeens and Langford attorneys that law. Yeah, that is Hunter Hawes to 199 gradient teal pink paper Teddy McGraw first base auto for the Mariners Now Lockwood is a weapon in Call of Duty. Yeah, it's like a meme from tiktok. It's like a semi-automatic sniper Jamie P with a 10 box football and a choice spot. Thank you buddy. How'd you know I work for Skeens and Langford? Skeens and Langford got me $200,000 Yeah, thank you. It's our thank you Paul and Wyatt. Thank you Paul There's two 99 Brooks Lee Rainer Arias to 54 is the Mar Johnson to 75 rock Regio 50 drew Hackenburg and Jackson at Cheerio to turn tables and a microphone First base auto of Teddy McGraw cam Fisher Colton led better Kendall George Max Anderson noble Meyer Jonah Cox Jacob Gonzales Homer Bush Christian Napsick Blake Mitchell Tai Pete CJ Kfis Maui a Huna Sabin Sabayos Nizan Zonatello Joe Redfield to 499 Paul Wilson Garrett Forrester Adrienne Santana Tommy Troy Kate Denton to 199 is Devin Saltibon to 250 Drew Hackenburg 150 Kevin Sim 71 Kate that and one-on-one printing plate of Christopher Torrin Thorin got a Paul Skeens first base auto Hey, Wyatt Langford image variation to 99 and then a gold wave brain For the race This auto in the product. Yes. Yes Right we got Trey the Ray and Bray the Ray now. Hey go that'll do it for the break everybody. Thanks again for the fill up next TC TC chrome black