Draw or McClim May 7th, 2022
Patrick Stein

Someone helpfully pointed out that the functionality that I was looking for when I made my Draw Library already exists in McClim. I feel like someone else reminded me of this a year or two ago. I forgot to look into it then. But, I will definitely look into it now.

I had a block thinking of McClim as windowing/GUI and overlooking its screenshot and print functionality.

Making Sudoku Diagrams in Lisp May 1st, 2022
Patrick Stein

A few weeks ago, I was analyzing a Sudoku variant if the board were a flat torus instead of a square. I wrote a little paper about this analysis.

For that paper, I created the diagrams by taking screenshots of the f-puzzles Sudoku editor, pulling them into the GIMP image editor, cropping them all to the same dimensions, and pulling them into my document. I discovered a mistake that I had made throughout all of the images after I had already collected all of the screenshots. Rather than fixing the mistake by doing a new screenshot, I fixed things in the image editor instead of in the Sudoku editor.

It was painful.

So, I decided to make a way to declare a diagram and then render it so that it can be modified/corrected rather painlessly.

My initial cut at this was in CL-PDF. I realized, when I had finished, that I had only used a small subset of CL-PDF and that almost all of that functionality was available in Vecto (with a tiny bit of help from ZPB-TTF which Vecto uses already).

This was all the motivation that I needed to finally start on a project that I’ve been hoping to do for years now. I wrote a compatibility library that takes something very, very close to the subset of CL-PDF that I used in the diagram and renders it either using CL-PDF or Vecto so that I can have the output as either a vector image or a raster image.

Sudoku diagram rendered showing different marking, highlighting, and labelling options of the SUDOKU-DIAGRAMS library

I’d like to extend this sometime to also output to CL-SVG, but the way that fonts are handled in SVGs might make that impossible for most things one would want to do with text in a diagram.

You can find the library here: https://github.com/nklein/sudoku-diagrams

DRAW v0.2.20220430 May 1st, 2022
Patrick Stein

I have released a new Lisp library. This library provides compatibility between CL-PDF and Vecto so that I can render the same drawing either as a vector drawing or a raster drawing.

This library forms an almost drop-in replacement for a small subset of CL-PDF and implements that subset with both CL-PDF and Vecto.

The functionality at the moment is somewhat limited. But, it is enough to make the Sudoku diagrams that I was working on. I had originally created the diagrams using CL-PDF. Then, I went through and wrapped them in one line of code and changed all of the PDF: package delimiters to DRAW: and ta-da. Diagrams.

Diagram showing various triangles, rectangles, and text to demonstrate the functions DRAW supports.

This is the current test image. It demonstrates all of the capabilities available at the moment.

You can find the library here: https://github.com/nklein/draw

Ranked Choice Voting Visualization November 9th, 2013
Patrick Stein

There were 35 candidates registered for the Minneapolis mayoral race this year. Minneapolis approved ranked-choice voting in 2006. I have great respect and deep sympathy for those who had to tabulate all of those votes. And, because there is no FEC-certified software for counting this type of vote, it was a huge human effort.

The Minnesota Secretary of State’s website has information about which candidates where eliminated in which of the 33 elimination rounds in the tabulation. I scraped the data from their Excel spreadsheet, added some Vecto, and put together some worm-trail charts. I couldn’t quite use Zach’s wormtrails library because I wanted to show how an eliminated candidates votes were redistributed (to other candidates who were lower-ranked choices or to the exhausted bucket). Also, note: the tabulated data on the Minnesota Secretary of State’s website is insufficient to form an accurate proportioning in rounds when multiple candidates are eliminated. In those cases, I just assumed that all candidates whose votes were redistributed were redistributed in the same proportions to the candidates who gained votes because of the eliminations in that round.

About 450 lines of Lisp code later, I came up with images like the one below (click to see it at full-size):
Minneapolis Mayoral 2013 RCV rounds 22 through 33

The white worm-trail through the center is the exhausted pile. Unfortunately, the eliminated candidates in the first 25 or so rounds had so few votes that I’d have to render these images wall-sized for you to get any idea what proportion of their votes went where. In the final few rounds, you can see some detail even with a semi-reasonable file size. I suppose I should see if I can wrangle the data from the St. Paul race which only had six candidates (and thus fewer than six rounds of counting).

Here is the chart broken up into three sections to make it a bit more manageable:
Minneapolis Mayoral 2013 RCV rounds 1 through 11 Minneapolis Mayoral 2013 RCV rounds 11 through 22 Minneapolis Mayoral 2013 RCV rounds 22 through 33

Here is a link to all rounds in one big file. And, here is the source code: rcv.lisp.

Note for Lisp folks: I don’t like the above code. I like short functions, but I also like using flet or labels to make functions that are still within lexical scope of a whole mess of variables. Anyone else come to a good resolution between those two things? Is bundling data in structs and classes really the right thing or a sea of global specials?

Visualizing Galois Fields May 17th, 2012
Patrick Stein

Galois fields are used in a number of different ways. For example, the AES encryption standard uses them.

Arithmetic in Galois Fields

The Galois fields of size 2^n for various n are convenient in computer applications because of how nicely they fit into bytes or words on the machine. The Galois field GF(2^n) has 2^n elements. These elements are represented as polynomials of degree less than n with all coefficients either 0 or 1. So, to encode an element of GF(2^n) as a number, you need an n-bit binary number.

For example, let us consider the Galois field GF(2^3). It has 2^3 = 8 elements. They are (as binary integers) 000, 001, 010, 011, 100, 101, 110, and 111. The element 110, for example, stands for the polynomial x^2 + x. The element 011 stands for the polynomial x + 1.

The coefficients add together just like the integers-modulo-2 add. In group theory terms, the coefficients are from \mathbb{Z}/2\mathbb{Z}. That means that 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 0. In computer terms, a + b is simply a XOR b. That means, to get the integer representation of the sum of two elements, we simply have to do the bitwise-XOR of their integer representations. Every processor that I’ve ever seen has built-in instructions to do this. Most computer languages support bitwise-XOR operations. In Lisp, the bitwise-XOR of a and b is (logxor a b).

Multiplication is somewhat trickier. Here, we have to multiply the polynomials together. For example, (x + 1) \cdot x = x^2 + x. But, if we did (x^2 + x) \cdot x, we’d end up with x^3 + x^2. We wanted everything to be polynomials of degree less than n and our n is 3. So, what do we do?

What we do, is we take some polynomial of degree n that cannot be written as the product of two polynomials of less than degree n. For our example, let’s use x^3 + x + 1 (which is 1011 in our binary scheme). Now, we need to take our products modulo this polynomial.

You may not have divided polynomials by other polynomials before. It’s a perfectly possible thing to do. When we divide a positive integer a by another positive integer b (with b bigger than 1), we get some answer strictly smaller than a with a remainder strictly smaller than b. When we divide a polynomial of degree m by a polynomial of degree n (with n greater than zero), we get an answer that is a polynomial of degree strictly less than m and a remainder that is a polynomial of degree strictly less than n.

Dividing proceeds much as long division of integers does. For example, if we take the polynomial (with integer coefficients) x^3 + 2x + 5 and divide it by the polynomial x + 3, we start by writing it as:

x + 3 \overline{\left) x^3 + 0x^2 + 2x + 5\right.}
We notice that to get (x+3) \cdot q(x) to start with x^3, we need q(x) to start with x^2. We then proceed to subtract (x+3) \cdot x^2 and then figure out that we need a -3x for the next term, and so on. We end up with x^2 - 3x + 11 with a remainder of -28 (a degree zero polynomial).

\begin{array}{ccrcrcrcr}& & & & x^2 & - & 3x & + & 11 \\& \multicolumn{8}{l}{\hrulefill} \\(x+3) & ) & x^3 & + & 0x^2 & + & 2x & + & 5 \\& & x^3 & + & 3x^2 & & & & \\& & \multicolumn{3}{l}{\hrulefill} & & & & \\& & & - & 3x^2 & + & 2x & & \\& & & - & 3x^2 & - & 9x & & \\& & & \multicolumn{4}{l}{\hrulefill} & & \\& & & & & & 11x & + & 5 \\& & & & & & 11x & + & 33 \\& & & & & & \multicolumn{3}{l}{\hrulefill} \\& & & & & & & - & 28\end{array}
For the example we cited earlier we had x^3 + x^2 which we needed to take modulo x^3 + x + 1. Well, dividing x^3 + x^2 by x^3 + x + 1, we see that it goes in one time with a remainder of x^2 + x + 1. [Note: addition and subtraction are the same in GF(2^n).]

\begin{array}{ccrcrcrcr}& & & & & & & & 1 \\& \multicolumn{8}{l}{\hrulefill} \\(x^3+x+1) & ) & x^3 & + & x^2 & + & 0x & + & 0 \\& & x^3 & + & 0x^2 & + & x & + & 1 \\& & \multicolumn{7}{l}{\hrulefill} \\& & & & x^2 & + & x & + & 1\\\end{array}
For a reasonable way to accomplish this in the special case of our integer representations of polynomials in GF(2^n), see this article about Finite Field Arithmetic and Reed Solomon Codes. In (tail-call style) Lisp, that algorithm for GF(2^8) might look something like this to multiply a times b modulo m:

(flet ((next-a (a)
(ash a -1))
(next-b (b)
(let ((overflow (plusp (logand b #x80))))
(if overflow
(mod (logxor (ash b 1) m) #x100)
(ash b 1)))))
(labels ((mult (a b r)
(cond
((zerop a) r)
((oddp a) (mult (next-a a) (next-b b) (logxor r b)))
(t (mult (next-a a) (next-b b) r)))))
(mult a b 0)))

How is the Galois field structured?

The additive structure is simple. Using our 8-bit representations of elements of GF(2^8), we can create an image where the pixel in the i-th row and j-th column is the sum (in the Galois field) of i and j (written as binary numbers). That looks like this:

Just before the above-mentioned article hit reddit, I got to wondering if the structure of the Galois field was affected at all by the choice of polynomial you used as the modulus. So, I put together some code to try out all of the polynomials of order 8.

Remember way back at the beginning of multiplication, I said that the modulus polynomial had to be one which couldn’t be written as the product of two polynomials of smaller degree? If you allow that, then you have two non-zero polynomials that when multiplied together will equal your modulus polynomial. Just like with integers, if you’ve got an exact multiple of the modulus, the remainder is zero. We don’t want to be able to multiply together two non-zero elements to get zero. Such elements would be called zero divisors.

Zero divisors would make these just be Galois rings instead of Galois fields. Another way of saying this is that in a field, the non-zero elements form a group under multiplication. If they don’t, but multiplication is still associative and distributes over addition, we call it a ring instead of a field.

Galois rings might be interesting in their own right, but they’re not good for AES-type encryption. In AES-type encryption, we’re trying to mix around the bits of the message. If our mixing takes us to zero, we can never undo that mixing—there is nothing we can multiply or divide by to get back what we mixed in.

So, we need a polynomial that cannot be factored into two smaller polynomials. Such a polynomial is said to be irreducible. We can just start building an image for the multiplication for a given modulus and bail out if it has two non-zero elements that multiply together to get zero. So, I did this for all elements which when written in our binary notation form odd numbers between (and including) 100000001 and 111111111 (shown as binary). These are the only numbers which could possibly represent irreducible polynomials of degree 8. The even numbers are easy to throw out because they can be written as x times a degree 7 polynomial.

The ones that worked were: 100011011, 100011101, 100101011, 100101101, 100111001, 100111111, 101001101, 101011111, 101100011, 101100101, 101101001, 101110001, 101110111, 101111011, 110000111, 110001011, 110001101, 110011111, 110100011, 110101001, 110110001, 110111101, 111000011, 111001111, 111010111, 111011101, 111100111, 111110011, 111110101, and 111111001. That first one that worked (100011011) is the one used in AES. Its multiplication table looks like:

Here’s it is again on the left with the multiplication table when 110011111 is the modulus on the right:

 
So, the addition image provides some insight into how addition works. The multiplication tables, at least for me, provide very little insight into anything. They don’t even make a good stereo pair.

To say two of the multiplication tables have the same structure, means there is some way to map back and forth between them so that the multiplication still works. If we have table X and table Y, then we need an invertible function f such that f(a \cdot_X b) = f(a) \cdot_Y f(b) for all a and b in the table X.

What’s next?

If there is an invertible map between two multiplication tables and there is some element a in the first table, you can take successive powers of it: a, a^2, a^3, \ldots. There are only 2^n elements in GF(2^n) no matter which polynomial we pick. So, somewhere in there, you have to start repeating. In fact, you have to get back to a. There is some smallest, positive integer k so that a^{k+1} \equiv a in GF(2^n). If we pick a = 0, then we simply have that k = 1. For non-zero a, we are even better off because a^k \equiv 1.

So, what if I took the powers of each element of GF(2^n) in turn? For each number, I would get a sequence of its powers. If I throw away the order of that sequence and just consider it a set, then I would end up with a subset of GF(2^n) for each a in GF(2^n). How many different subsets will I end up with? Will there be a different subset for each a?

I mentioned earlier that the non-zero elements of GF(2^n) form what’s called a group. The subset created by the powers of any fixed a forms what’s called a subgroup. A subgroup is a subset of a group such that given any two members of that subset, their product (in the whole group) is also a member of the subset. As it turns out, for groups with a finite number of elements, the number of items in a subgroup has to divide evenly into the number of elements in the whole group.

The element zero in GF(2^n) forms the subset containing only zero. The non-zero elements of GF(2^n) form a group of 2^n - 1 elements. The number 2^n - 1 is odd (for all n \ge 1). So, immediately, we know that all of the subsets we generate are going to have an odd number of items in them. For GF(2^8), there are 255 non-zero elements. The numbers that divide 255 are: 1, 3, 5, 15, 17, 51, 85, and 255.

It turns out that the non-zero elements of GF(2^n) form what’s called a cyclic group. That means that there is at least one element a whose subset is all 2^n - 1 of the non-zero elements. If take one of those a‘s in GF(2^8) whose subset is all 255 of the elements, we can quickly see that the powers of a^3 form a subset containing 85 elements, the powers of a^5 form a subset containing 51 elements, …, the powers of a^{85} form a subset containing 3 elements, and the powers of a^{255} form a subset containing 1 element. Further, if both a and b have all 255 elements in their subset, then a^k and b^k will have the same number of elements in their subsets for all k. We would still have to check to make sure that if a^i + a^j = a^k that b^i + b^j = b^k to verify the whole field structure is the same.

This means there are only 8 different subset of GF(2^8)‘s non-zero elements which form subgroups. Pictorially, if we placed the powers of a around a circle so that a^0 = 1 was at the top and the powers progressed around the circle and then drew a polygon connecting consecutive points, then consecutive points in the a^3 sequence and consecutive points in the a^5 sequence, etc…. we’d end up with this:

If we don’t reorder them and just leave them in the numerical order of their binary representation, the result isn’t as aesthetically pleasing as the previous picture. Here are the same two we used before 100011011 (on the left) and 110011111 (on the right). They are easier to look at. They do not lend much more insight nor make a better stereo pair.

 
*shrug* Here’s the source file that I used to generate all of these images with Vecto and ZPNG: group.lisp

RSS Feeds

l