donut.c without a math library

https://www.a1k0n.net/2021/01/13/optimizing-donut.html [www.a1k0n.net]

2021-01-20 05:39

tags:
c
math
programming

My little donut.c has been making the rounds again, after being featured in a couple YouTube videos (e.g., Lex Fridman and Joma Tech). If I had known how much attention this code would get over the years, I would have spent more time on it.

Re-Deriving the edwards25519 Decoding Formulas

https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-re-deriving-the/ [buttondown.email]

2020-12-21 17:03

tags:
crypto
math

A lot of my job is implementing specifications, and sometimes in a crypto spec you’ll encounter something like this and what you do is nod, copy it into a comment, break it down into a sequence of operations, and check that the result matches a test case. However, the other day I was having a bit of an identity crisis because I could not remember basic algebra, so I went and re-derived the edwards25519 point decoding formulas as a sort of homework. It turned out to be pretty useful for understanding pieces of the implementation I had been just treating as black boxes. I’m going to try to take you along for the ride, to show that there is no dark magic involved, and that we can all get to the same result as the specification with step-by-step high-school algebra.

Floating-Point Formats

http://www.quadibloc.com/comp/cp0201.htm [www.quadibloc.com]

2020-12-13 07:05

tags:
compsci
format
math
reference
retro
systems

Baby Sharks - Injecting small order points to threshold EdDSA

https://medium.com/zengo/baby-sharks-a3b9ceb4efe0 [medium.com]

2020-12-11 07:03

tags:
blockchain
crypto
math
security

We showcase one example of how an attacker can inject a low order subgroup group element in threshold EdDSA protocol secure against malicious adversaries, bypassing existing protections.

source: green

Dissecting Lemire’s nearly divisionless random

https://veryseriousblog.com/posts/dissecting-lemire [veryseriousblog.com]

2020-10-03 03:40

tags:
math
perf
programming
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)

https://www.youtube.com/watch?v=ovJcsL7vyrk [www.youtube.com]

2020-08-17 04:46

tags:
math
science
video
visualization

That may be over selling it, but cool anyway.

Is X25519 Associative? Sometimes!

https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-is-x25519-associative/ [buttondown.email]

2020-05-28 04:40

tags:
crypto
math

Extracting ROM constants from the 8087 math coprocessor's die

http://www.righto.com/2020/05/extracting-rom-constants-from-8087-math.html [www.righto.com]

2020-05-17 23:20

tags:
hardware
math
photos
retro

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.

Byrne’s Euclid

https://www.c82.net/euclid/ [www.c82.net]

2020-04-27 04:08

tags:
book
math

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

https://web.williams.edu/Mathematics/lg5/Rota.pdf [web.williams.edu]

2020-04-20 21:57

tags:
academia
essay
math
pdf

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.

source: trivium

Forecasting s-curves is hard

https://constancecrozier.com/2020/04/16/forecasting-s-curves-is-hard/ [constancecrozier.com]

2020-04-19 14:30

tags:
math
visualization

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).

source: HN

Another look at two Linux KASLR patches

https://www.kryptoslogic.com/blog/2020/03/another-look-at-two-linux-kaslr-patches/ [www.kryptoslogic.com]

2020-03-25 01:51

tags:
linux
math
random
security

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?

source: R

Landmark Computer Science Proof Cascades Through Physics and Math

https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/ [www.quantamagazine.org]

2020-03-08 04:00

tags:
compsci
math
paper
quantum

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

source: green

Building Lattice Reduction (LLL) Intuition

https://kel.bz/post/lll/ [kel.bz]

2020-01-24 07:49

tags:
crypto
dupe
math

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

https://github.com/kelbyludwig/notebooks/blob/master/The%20Hidden%20Number%20Problem.ipynb [github.com]

2020-01-24 07:47

tags:
crypto
exploit
interactive
math
programming
python
security

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

http://marginalrevolution.com/marginalrevolution/2020/01/big-datasmall-bias.html [marginalrevolution.com]

2020-01-15 18:20

tags:
math
paper

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.

source: MR

Isogeny crypto

https://ellipticnews.wordpress.com/2019/11/09/isogeny-crypto/ [ellipticnews.wordpress.com]

2019-11-11 05:24

tags:
bugfix
compsci
crypto
math
security

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.

source: green

Signed distance fields

https://jasmcole.com/2019/10/03/signed-distance-fields/ [jasmcole.com]

2019-11-04 04:39

tags:
gl
graphics
math
programming
visualization

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.

source: L

The Deadly Consequences of Rounding Errors

https://slate.com/technology/2019/10/round-floor-software-errors-stock-market-battlefield.html [slate.com]

2019-11-04 04:04

tags:
development
finance
math
programming
tech

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.

source: ML

Incenters of chocolate-iced cakes

https://blog.plover.com/math/cake.html [blog.plover.com]

2019-10-11 03:12

tags:
food
math
visualization

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?