Rock, paper, scissors, algebra

Posted on by John

Aatish Bhatia posted something interesting on Twitter: if you define multiplication on Rock, Paper, Scissors to be the winner of a match, the result is commutative but not associative.

The same is true of the extension Rock, Paper, Scissors, Lizard, Spock

Rules of rock, paper, scissors, lizard, spock.

Related post: Weakening the requirements of a group

Liminal and subliminal

Posted on by John

It occurred to me for the first time this morning that the words liminal and subliminal must be related, just after reading an article by Vicki Boykis that discusses liminal spaces.

I hear the two words in such in different contexts—architecture versus psychology—and hadn’t thought about the connection until now. If I were playing a word association game, my responses would be these.

Q: Liminal?

A: Spaces.

Q: Subliminal?

A: Message.

Etymology

I checked Etymonline to verify that the two words are indeed cognate. Both come from the Latin word limen for threshold. Something is subliminal if it is below the threshold, typically the threshold of consciousness.

Frequency

Surely the word subliminal is far more common than liminal. To verify this, I turned to Google’s Ngram Viewer. I’ve included a screenshot below, and you can find the original here.

Ngram of liminal vs subliminal

It’s not surprising that subliminal was a popular term during the career of Sigmund Freud. He published The Interpretation of Dreams in 1899 and died in 1939.

What is surprising, at least to me, is that the word liminal has been gaining popularity and passed subliminal around the turn of the century. I didn’t expect liminal to be anywhere near as common as subliminal.

Bias

Google’s Ngram data comes from books. Word frequencies in books can be very different than word frequencies in common speech or other writing as this example shows. I can’t recall ever hearing someone use liminal in conversation. Maybe civil engineers and architects hear it all the time. As I type this, my spell checker puts a red squiggly line under every instance of liminal, showing that the word is not in its default dictionary, though it does recognize subliminal.

Related posts

Cop with a mop

Posted on by John

Yesterday I was at a wedding, and a vase broke in the aisle shortly before the bridal party was to enter. Guests quickly picked up the pieces, but the vase left a pool of water on the hard floor.

A security guard ran (literally) for a mop and cheerfully picked up the water. He could have easily stood in the corner and said that mopping floors is not his job. And if he were guarding a jewelry store, it would be inappropriate for him to leave his post to get a mop. But his presence at the wedding was a formality, presumably a venue requirement, and no one was endangered by his fetching a mop. There was more danger of someone slipping on a wet floor.

I enjoy seeing anyone do their job with enthusiasm, doing more than the minimum required. Over-zealous people can cause problems, but I’d much rather deal with such problems than deal with people passively putting in their time.

R with Conda

Posted on by John

I’ve been unable to get some R libraries to install on my Linux laptop. Two libraries in particular were tseries and tidyverse. The same libraries installed just fine on Windows. (Maybe you need to install Rtools first before installing these on Windows; I don’t remember.)

I use conda all the time with Python, but I hadn’t tried it with R until this evening. Apparently it just works. The libraries I was trying to install have a lot of dependencies, and conda is very good at managing dependencies.

I removed my installation of R and reinstalled from conda:

    conda install r-base

Then I installed tseries with

    conda install r-tseries

and installed tidyverse analogously:

    conda install r-tidyverse

Just prepend r- to the name of the R library you want to install.

I haven’t used it in anger yet, but it seems that everything works just fine.

On this day

Posted on by John

This morning as a sort of experiment I decided to look back at all my blog posts written on May 30 each year. There’s nothing special about this date, so I thought it might give an eclectic cross section of things I’ve written about.

***

Last year on this day I wrote about Calendars and continued fractions, based on a connection between the two topics I found in the book Calendrical Calculations.

***

Two years ago on this day I wrote about Color theory questions. I’ve been interested in color theory off and on for a while. At one point I thought I might “get to the bottom” of it and figure everything out to my satisfaction. I’ve since decided that color theory is a bottomless well: there’s no getting to the bottom of it. I might pick it back up some day with the more modest goal of learning a little more than I currently know.

***

I didn’t write a post on May 30 in 2014, 2015, or 2016.

***

On this day in 2013, I wrote a riff on a quote from Matt Briggs to the effect that there are no outliers, only measurements that don’t fit with your theory.

***

In 2012 on this day I posted Writing software for someone else. Most of what I’ve read about software development does not make the distinction between writing software for yourself and writing software for someone else, or at least does not emphasize the distinction.

When computer science students become professional programmers, they have to learn empathy. Or at least ideally they learn empathy. They go from completing homework assignments to writing programs that other people will work on and that other people will use. They learn “best practices,” best in this new context.

I made the opposite transition a few months after writing that post when I left MD Anderson Cancer Center to go out on my own. It took a while for me to decide what works best for me, mostly writing software for my own use. Sometimes I deliver software to clients, but more often I deliver reports that require me to write software that the client isn’t directly interested in.

***

My post for May 30, 2011 was just a quote from Richard Feynman speculating that in the long run, the development of Maxwell’s equations will be seen as the most important event of the 19th century.

***

In 2010 on this day I posted a quote from Paul Buchheit about the effect of suddenly acquiring wealth. For most people it would not be a good thing.

***

The post for May 30 in 2009 was called Killing too much of a tumor. You can actually make a tumor more harmful by killing off portions that were suppressing its growth. Reminds me now of how in war you want to leave enough of the enemy’s command in tact that they have the ability to surrender.

***

Finally, on this day in 2008 I announced that I’d started a web site at reproducibleresearch.org. I later gave the URL to people who had started a similar site with the same name, but ending in .org.

Promoting reproducible research seemed like a somewhat quixotic project at the time, but fortunately it has gained traction since then.

***

Is there a common theme in these posts? They are all about things that interest me, but that’s necessarily the case since they’re on my blog. One thing that surprises me is that the posts are not particularly mathematical. I would have expected that a quasi-random sample of posts would have turned up more math. But I did write about cancer and software development more when I worked in a cancer center and managed software developers.

Sum of all Spheres

Posted on by John

I ran across a video this afternoon that explains that the sum of volumes of all even-dimensional unit spheres equals eπ.

Why is that? Define vol(n) to be the volume of the unit sphere in dimension n. Then

\mathrm{vol}(n) = \frac{\pi^{n/2}}{\Gamma\left(\frac{n}{2} + 1\right)}

and so the sum of the volumes of all even dimensional spheres is

\sum_{k=0}^\infty \mathrm{vol}(2k) = \sum_{k=0}^\infty \frac{\pi^k}{k!} = \exp(\pi)

But what if you wanted to sum the volumes of all odd dimensional unit spheres? Or all dimensions, even and odd?

The answers to all these questions are easy in terms of the Mittag-Leffler function that I blogged about a while back. This function is defined as

E_{\alpha, \beta}(x) = \sum_{k=0}^\infty \frac{x^k}{\Gamma(\alpha k+\beta)}

and reduces to the exponential function when α = β = 1.

The sum of the volumes of all unit spheres of all dimensions is E1/2, 1(√π). And from the post mentioned above,

E_{1/2, 1}(x) = \exp(x^2) \, \mbox{erfc}(-x)

where erfc is the complementary error function. So the sum of all volumes of spheres is exp(π) erfc(-√π).

Now erfc(-√π) ≈ 1.9878 and so this says the sum of the volumes of spheres of all dimensions is about twice the sum of the even dimensional spheres alone. And so the sum of the odd dimensional unit sphere volumes is almost the same as the sum of the even dimensional ones.

By the way, you could easily answer other questions about sums of sphere volumes in terms of the Mittag-Leffler function. For example, if you want to add up the volumes in all dimensions that are a multiple of 3, you get E3/2, 1(π3/2).

Related posts

Inside the AES S-box

Posted on by John

The AES (Advanced Encryption Standard) algorithm takes in blocks of 128 or more bits [1] and applies a sequence of substitutions and permutations. The substitutions employ an “S-box”, named the Rijndael S-box after its designers [2], an invertible nonlinear transformation that works on 8 bits at a time.

There are 256 = 16 × 16 possible 8-bit numbers, and so the S-box can be represented as a 16 by 16 table mapping inputs to outputs. You can find the tables representing the S-box and its inverse in this text file in org-mode format.

This post will look in detail at how the entries of that table are filled. A high-level description of the design is as follows. For an 8-bit number x,

  1. Invert in GF(28)
  2. Multiply by a matrix L
  3. Add a constant c.

Next we dive into what each of these steps mean. And at the end we’ll work an example in detail.

My source is The Block Cipher Companion by Knudsen and Robshaw.

Inversion in GF(28)

Steps 1 and 3 take the inverse of a number as a member of the finite field GF(28), a finite field with 28 elements.

The number of elements in a finite field determines the field, up to isomorphism. That is, in a sense there is only one field with 28 = 256 elements. In fact there are 30 different fields with 256 elements (see this post for where that number came from). The 30 fields are isomorphic, but when we’re doing actual calculations, rather than abstract theory, we need to specify which representation we’re using.

Finite fields can be specified as polynomials modulo an irreducible polynomial. To carry out our calculations we need to specify a particular irreducible 8th degree polynomial with binary coefficients. The one that AES uses is

p(x) = x8 + x4 + x3 + x + 1.

So by taking the inverse in GF(28) we mean to take an 8-bit number y, interpret it as a polynomial with binary coefficients, and find another 8-bit number x-1 such that when we multiply them as polynomials, and take the remainder after dividing by p(x) we get the polynomial 1.

There’s one wrinkle in this procedure: only 255 of the 256 elements of GF(28) have an inverse. There is no inverse for 0, but for our purposes we’ll take the inverse of 0 to be 0.

Multiplication by L

The matrix L we need here is the 8 by 8 binary matrix whose entries are

        10001111
        11000111
        11100011
        11110001
        11111000
        01111100
        00111110
        00011111

When we say to multiply x-1 by L we mean to think of x-1 as a vector over the field of two elements, and carry out matrix multiplication in that context.

Additive constant

The constant that we add is 0x63. The reason an additive constant was chosen was so that a zero input would not map to a zero output. Note that “addition” here is vector addition, and is carried out over the field of two elements, just as the multiplication above. This amounts to XOR of the bits.

Manual calculation example

To make everything above more concrete, we’ll calculate one entry of the table by hand.

Lets start with input y = 0x11 = 0b10001. We represent y as the polynomial f(x) = x4 + 1 and look for a polynomial g(x) such that the remainder when f(x) g(x) is divided by p(x) defined above is 1.

The process of finding g is complicated—maybe I’ll blog about it in the future—but I claim

g(x) = x7 + x5 + x4 + x2

which means the inverse of y in GF(28), represented in binary, is 0b10110100 = 0xB4. You can find a table of inverses here.

Next we multiply the matrix L by the vector made from the bits of y-1. However, there is a gotcha here. When Knudsen and Robshaw say to multiply the bits of y-1 by L, they assume the bits are arranged from least significant to most significant. Since the bits of y-1 are 10110100, we multiply L by the vector

[0, 0, 1, 0, 1, 1, 0, 1].

This multiplication gives us the vector

[1, 0, 0, 0, 0, 1, 1, 1].

Next we add the vector formed from the bits of 0x63, again from least significant to most significant. That means we lay out 0x63 = 0b01100011 as

[1, 1, 0, 0, 0, 1, 1, 0].

This gives us the result

[0, 1, 0, 0, 0, 0, 0, 1].

Reading the bits from least significant to most, this gives 0x82.

In sum, we’ve verified that the AES S-box takes 0x11 to 0x82, as stated in the table.

Related posts

[1] The Rijndael block cipher operates on blocks whose size is a multiple of 32 bits. The AES standard adopted Rijndael with block sizes 128, 192, and 256.

[2] “Rijndael” is a play on the designers of the cipher, Vincent Rijmen and Joan Daemen.

Random sampling from a file

Posted on by John

I recently learned about the Linux command line utility shuf from browsing The Art of Command Line. This could be useful for random sampling.

Given just a file name, shuf randomly permutes the lines of the file.

With the option -n you can specify how many lines to return. So it’s doing sampling without replacement. For example,

    shuf -n 10 foo.txt

would select 10 lines from foo.txt.

Actually, it would select at most 10 lines. You can’t select 10 lines without replacement from a file with less than 10 lines. If you ask for an impossible number of lines, the -n option is ignored.

You can also sample with replacement using the -r option. In that case you can select more lines than are in the file since lines may be reused. For example, you could run

    shuf -r -n 10 foo.txt

to select 10 lines drawn with replacement from foo.txt, regardless of how many lines foo.txt has. For example, when I ran the command above on a file containing

    alpha
    beta
    gamma

I got the output

    beta
    gamma
    gamma
    beta
    alpha
    alpha
    gamma
    gamma
    beta

I don’t know how shuf seeds its random generator. Maybe from the system time. But if you run it twice you will get different results. Probably.

Related

Between now and quantum

Posted on by John

The National Security Agency has stated clearly that they believe this is the time to start moving to quantum-resistant encryption. Even the most optimistic enthusiasts for quantum computing believe that practical quantum computers are years away, but so is the standardization of post-quantum encryption methods.

The NSA has also made some suggestions for what to do in the mean time [1]. Last year the agency replaced its Suite B cryptography recommendations with the CNSA: Commercial National Security Algorithm Suite.

In a nutshell: use well-established methods for now but with longer keys.

In a little larger nutshell, the recommendations are:

  • SHA-384 for secure hashing
  • AES-256 for symmetric encryption
  • RSA with 3072 bit keys for digital signatures and for key exchange
  • Diffie Hellman (DH) with 3072 bit keys for key exchange
  • Elliptic curve P-384, both for key exchange (ECDH) and for digital signatures (ECDSA)

Each of these represents a 50% or 100% increase in key length:

  • from 128 to 256 for AES
  • from 256 to 384 for hashing and ECC
  • from 2048 to 3072 for RSA and DH.

If these are just stopgap measures, why not jump straight to quantum-resistant methods? There are quantum-resistant encryption methods available, but most of them haven’t been studied that long. As Koblitz and Menezes put it,

… most quantum-resistant systems that have been proposed are complicated, have criteria for parameter selection that are not completely clear, and in some cases (such as NTRU) have a history of successful attacks on earlier versions.

Some methods do have a long history but have other drawbacks. Robert McEliece’s encryption method, for example, dates back to 1978 and has held up well, but it requires a megabyte key to achieve 128-bit security. There is a variation on McEliece’s method that has radically smaller keys, but it’s only been around for six years. In short, the dust hasn’t settled regarding post-quantum encryption methods.

Related posts

[1] People are naturally suspicious of algorithm recommendations coming from the NSA. Wouldn’t the agency like for everyone to use encryption methods that it could break? Of course. But the agency also wants US companies and government agencies to use encryption methods that foreign agencies cannot break.

There’s little downside to using established methods with longer keys. However, key length may not the weakest link. If you’re vulnerable to timing attacks, for example, doubling your key length may create a false sense of security.

Cosmic rays flipping bits

Posted on by John

A cosmic ray striking computer memory at just the right time can flip a bit, turning a 0 into a 1 or vice versa. While I knew that cosmic ray bit flips were a theoretical possibility, I didn’t know until recently that there had been documented instances on the ground [1].

Radiolab did an episode on the case of a cosmic bit flip changing the vote tally in a Belgian election in 2003. The error was caught because one candidate got more votes than was logically possible. A recount showed that the person in question got 4096 more votes in the first count than the second count. The difference of exactly 212 votes was a clue that there had been a bit flip. All the other counts remained unchanged when they reran the tally.

It’s interesting that the cosmic ray-induced error was discovered presumably because the software quality was high. All software is subject to cosmic bit flipping, but most of it is so buggy that you couldn’t rule out other sources of error.

Cosmic bit flipping is becoming more common because processors have become smaller and more energy efficient: the less energy it takes for a program to set a bit intentionally, the less energy it takes for radiation to set a bit accidentally.

Related post: Six sigma events

[1] Spacecraft are especially susceptible to bit flipping from cosmic rays because they are out from under the radiation shield we enjoy on Earth’s surface.