distributed.net OGR Project

Currently the OGR code is based on the GARSP 5.13 code of the original OGR-21 effort. There is a new version (GARSP 6.00) available with some further optimizations, but I have not merged that code in yet.

Because the upcoming DES contests are consuming the rest of the distributed.net resources at the moment, we will not see the OGR project start until some time after DES-III has been completed.

What are Golomb Rulers anyway?

A Golomb ruler is a way to place marks along a line such that each pair of marks measures a unique linear distance. Here is a Golomb ruler with five marks:

| |     |         |   |
0 1     4         9   11

The number below the mark is the distance from the left edge. The length of this ruler is 11, and it happens to be one of the two shortest such rulers with five marks. The other ruler has marks at positions 0, 3, 4, 9, and 11. (The mirror images of these two rulers, 0, 2, 7, 10, 11 and 0, 2, 7, 8, 11, are also optimal Golomb rulers. Usually just one of each mirror-image pair is mentioned.)

You can check that the above ruler is indeed Golomb by writing out a table of all the pairs of marks and their respective distances:

Mark1  Mark2  Distance
-----  -----  --------
  0      1       1
  0      4       4
  0      9       9
  0      11      11
  1      4       3
  1      9       8
  1      11      10
  4      9       5
  4      11      7
  9      11      2

Note that there are no duplicated distances in the third column. There is also no distance 6, but that is okay because Golomb rulers don't have to measure each distance, only distinct distances.

The goal of "optimizing" Golomb rulers is to get them as short as possible, while not duplicating any measured distances. The two 5-mark rulers above are optimal.

Golomb rulers are usually characterized by their differences, rather than absolute distances as in the above diagram. So the above ruler would be 1-3-5-2 (sometimes this is written as 0-1-3-5-2 but the leading zero is often dropped).

The current best known 21-mark ruler is the following:


James B. Shearer has compiled a list of all the best known Golomb rulers up to 150 marks. If you're comparing rulers, note that the 21-mark ruler listed on James' page is the mirror image of the one above.

How the OGR Search Works

The approach used by the OGR search code is a depth-first recursive tree traversal. The following is a description of an exhaustive tree traversal with no optimizations.

At each stage, a new mark is added some distance past the end of the ruler. If this mark causes a duplicate distance to be measured, the mark is moved to the right by one unit and it is checked again. If the mark moves too far to the right, such that we can't possibly fit the next marks in the remaining length (remember we already know the length of the best-known ruler), then the search backtracks to the previous level. If the newly placed mark satisfies the Golomb-ness requirements, the search proceeds to the next mark along the ruler.

The most important optimization is in the placing of the "next" mark. Through clever manipulation of bitmaps representing tables of distances, we do not need to actually check each new mark position. Rather, the bitmaps tell us where new marks can be placed that already satisfy the Golomb-ness requirements.

The other important optimization is the decision about whether the current ruler is too long or not. By detecting that the ruler so far cannot possibly be part of a ruler shorter than the current best known, we can eliminate a lot of unnecessary searching.

OGR and RC5/DES Compared

The process of searching for an Optimal Golomb Ruler differs somewhat from searching for an encryption key. The following table compares various aspects of the two projects.

Encryption KeyOptimal Golomb Ruler
The key is unknown, but is known to exist. A best-known ruler is already known for any given length. There is no guarantee that a better one will be found.
Each unit of work, the key block, is a fixed number of keys. Each unit of work, the ruler stub, contains a variable number of "nodes" that must be checked.
An encryption key takes exactly the same number of CPU cycles to check, every time. The OGR "node" count is the number of leaf nodes encountered in the tree traversal. The amount of CPU cycles per node is not constant.
A given computer will always check the same number of keys/sec (disregarding variations due to other work the CPU might be doing). A given computer's number of nodes/sec performance will vary slightly depending on the current stub being worked on.
The keyspace only needs to be searched until the key is found. We know there is only one correct key. The ruler-space must be searched completely. Although we may find a shorter Golomb ruler partway through, there may be still shorter ones not found yet.
There are cash prizes for finding the correct encryption key. There is (currently) no prize for finding a new Optimal Golomb Ruler.

Greg Hewgill <greg@hewgill.com>