Dissecting Lemire’s nearly divisionless random
The idea was simple, I’ve always felt that code readability is undervalued so I figured I’d put cold hard cash up. I announced a $1,000 pot, divided into $500, $300, and $200 prizes for the most readable implementations of Daniel Lemire’s nearly divisionless algorithm for selecting a random number from an interval. I now have winners to announce and congratulate, and they’re in this blog post, but there’s more to this story.
This equation will change how you see the world (the logistic map)
That may be over selling it, but cool anyway.
Is X25519 Associative? Sometimes!
Extracting ROM constants from the 8087 math coprocessor's die
I opened up an 8087 chip and took photos with a microscope. The photo below shows the chip’s tiny silicon die. Around the edges of the chip, tiny bond wires connect the chip to the 40 external pins. The labels show the main functional blocks, based on my reverse engineering. By examining the chip closely, various constants can be read out of the chip’s ROM, numbers such as pi that the chip uses in its calculations.
If one of the lines paſs through the centre, it is evident that it cannot be biſected by the other, which does not paſs through the centre.
I probably could have done without ye olde spelling, but nice web conversion otherwise.
Ten Lessons I Wish I Had Learned Before I Started Teaching Differential Equations
One of many mistakes of my youth was writing a textbook in ordinary differential equations. It set me back several years in my career in mathematics. However, it had a redeeming feature: it led me to realize that I had no idea what a differential equation is. The more I teach differential equations, the less I understand the mystery of differential equations.
Forecasting s-curves is hard
S-curves have only three parameters, and so it is perhaps impressive that they fit a variety of systems so well. Broadly, the three parameters describe the initial growth rate, the level-off rate, and the value at which it levels-off. Therefore, if you can estimate these three numbers, then you have the trend curve. Many of us will have learnt in school that if there are three parameters to be found, you need three data points to define the function. This would suggest that you could perfectly predict the level-off point based on only three observations (spoiler: you can’t).
Another look at two Linux KASLR patches
In the end, this random number generator was quickly removed, and that was that. But one can still wonder—is this generator secure but unanalyzed, or would it have been broken just to prove a point?
Landmark Computer Science Proof Cascades Through Physics and Math
Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.
Building Lattice Reduction (LLL) Intuition
The Lenstra–Lenstra–Lovász (LLL) algorithm is an algorithm that efficiently transforms a “bad” basis for a lattice L into a “pretty good” basis for the same lattice. This transformation of a bad basis into a better basis is known as lattice reduction, and it has useful applications. For example, there is attack against ECDSA implementations that leverage biased RNGs that can lead to private key recovery. However, my experience learning why LLL works has been pretty rough. Most material covering LLL seems targeted towards mathematicians and I had to (I guess I wanted to) spend a lot of time trying to weasel out the intuition and mechanics of the algorithm. This blog post is a semi-organized brain dump of that process. My goal is to cover LLL in such a way that slowly ratchets down the hand-waving, so feel free to read until you are happy with your level of understanding.
The Hidden Number Problem
The Hidden Number Problem (HNP) is a problem that poses the question: Are the most signficant bits of a Diffie-Hellman shared key as hard to compute as the entire secret? The original problem was defined in the paper “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan.
In this paper Boneh and Venkatesan demonstrate that a bounded number of most signifcant bits of a shared secret are as hard to compute as the entire secret itself. They also demonstrate an efficient algorithm for recovering secrets given a significant enough bit leakage. This notebook walks through some of the paper and demonstrates some of the results.
Big Data+Small Bias
Among experts it’s well understood that “big data” doesn’t solve problems of bias. But how much should one trust an estimate from a big but possibly biased data set compared to a much smaller random sample? In Statistical paradises and paradoxes in big data, Xiao-Li Meng provides some answers which are shocking, even to experts.
Rolling forward 15 years, isogeny-based cryptography is another area with many technical subtleties, but is moving into the mainstream of cryptography. Once again, not everything that can be done with discrete logarithms can necessarily be done with isogenies. It is therefore not surprising to find papers that have issues with their security.
It is probably time for an Isogenies for Cryptographers paper, but I don’t have time to write it. Instead, in this blog post I will mention several recent examples of incorrect papers. My hope is that these examples are instructional and will help prevent future mistakes. My intention is not to bring shame upon the authors.
Signed distance fields
It would be fun, I thought, to be able to specify the desired cross-sections, and have something generate the required 3D shape (if it existed) in real-time.
Dealing with all of the details of creating a mesh with the right vertices etc. sounded painful though. Fortunately, I had been reading recently about a different kind of 3D rendering technique which makes these kind of boolean operations trivial – signed distance fields.
The Deadly Consequences of Rounding Errors
In politics, stock markets, space, and the battlefield, tiny software calculation mistakes have had enormous consequences.
Sometimes those fractional cents aren’t stolen—they simply vanish. In the early 1980s, a new stock index at the Vancouver Stock Exchange tracked a steady and mysterious loss in value. An investigation revealed that floor() was being used instead of round(), with the lost fractions of cents accumulating to almost a 50 percent loss of value in 22 months. The programming mistake was finally fixed; the index closed around 500 on a Friday and reopened the following Monday at over 1,000, the lost value restored.
Incenters of chocolate-iced cakes
Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She put chocolate icing on top of the cake and on the sides, but not on the bottom. She wanted to divide the cake fairly among her 9 grandchildren so that each child would get an equal amount of the cake and the icing. How should she cut the cake?
A fast alternative to the modulo reduction
Assume that x and N are 32-bit integers, consider the 64-bit product x * N. You have that (x * N) div 2^32 is in the range, and it is a fair map.
Where Theory Meets Chalk, Dust Flies
A photo survey of the blackboards of mathematicians.
For the last year, Jessica Wynne, a photographer and professor at the Fashion Institute of Technology in New York, has been photographing mathematicians’ blackboards, finding art in the swirling gangs of symbols sketched in the heat of imagination, argument and speculation. “Do Not Erase,” a collection of these images, will be published by Princeton University Press in the fall of 2020.
Visual Information Theory
Information theory gives us precise language for describing a lot of things. How uncertain am I? How much does knowing the answer to question A tell me about the answer to question B? How similar is one set of beliefs to another? I’ve had informal versions of these ideas since I was a young child, but information theory crystallizes them into precise, powerful ideas. These ideas have an enormous variety of applications, from the compression of data, to quantum physics, to machine learning, and vast fields in between.
Unfortunately, information theory can seem kind of intimidating. I don’t think there’s any reason it should be. In fact, many core ideas can be explained completely visually!
Marty Weitzman’s Noah’s Ark Problem
Marty Weitzman passed away suddenly yesterday. He was on many people’s shortlist for the Nobel. His work is marked by high-theory applied to practical problems. The theory is always worked out in great generality and is difficult even for most economists. Weitzman wanted to be understood by more than a handful of theorists, however, and so he also went to great lengths to look for special cases or revealing metaphors. Thus, the typical Weitzman paper has a dense middle section of math but an introduction and conclusion of sparkling prose that can be understood and appreciated by anyone for its insights.
The Noah’s Ark Problem illustrates the model and is my favorite Weitzman paper.