では、ねじまきによる踊る暗号解読班のためのＯＧＲ解説、始めます。
じゃ、ゴロム定規とは？
これは、どう説明したものかずっと考えてたんだけど、結局、以下のように考えてください。
みなさん、リーグ表というの、見たことあるでしょ？こういうやつ↓
| 日本 | アメリカ | 中国 | カナダ | |
|---|---|---|---|---|
| 日本 | − | ○ | ○ | ○ |
| アメリカ | × | − | ○ | ○ |
| 中国 | × | × | − | ○ |
| カナダ | × | × | × | − |
でね、国名のところに０から３の数字が入ったやつを考えてみてください。で、対戦結果の変わりに、二つの数字の差を入れてみます。
| ０ | １ | ２ | ３ | |
|---|---|---|---|---|
| ０ | − | １ | ２ | ３ |
| １ | １ | − | １ | ２ |
| ２ | ０ | １ | − | １ |
| ３ | ３ | ２ | １ | − |
すると、対戦欄の数字、かなりダブってますよね。１になる組み合わせが、３パターンもある。
で、この、二つの数字の差が、ダブらないような組み合わせを探そう！というのがＯＧＲ探索なんですよ。 下の表を見てください。
| ０ | １ | ３ | ７ | |
|---|---|---|---|---|
| ０ | − | １ | ３ | ７ |
| １ | １ | − | ２ | ６ |
| ３ | ３ | ２ | − | ４ |
| ７ | ７ | ６ | ４ | − |
これなら、全ての組み合わせの差が違いますね。このときの０・１・３・７という数字のようなものをゴロム定規というわけです。この例のように数字を四つ使う組み合わせでは、両端の数字の差が「７」になるものがいちばん短いので、最短ゴロム定規（Optimal Golomb Ruler : OGR)と呼びます。
だんだん見えてきましたね。
さて、上のリーグ表では、４つの数字のリーグ表を作りました。で、我々が参加しているＯＧＲ−２４というのは、なんと、２４もの数字のリーグ表をチェックして、ダブりがないか、今までにわかっているよりも両端の数字の差が小さいものはないか、ということをチェックしているのです。
ね。たしかに、distributed.net規模のマシンパワーが必要ですよね(^^)
最新のクライアント（Build458以上）を使うと、このＯＧＲ−２４コンテストに参加できます。今までのＲＣ５でいう送受信ブロックにあたるのが、「スタブ」です。これには、先頭の５つが固定された（残りの１９個がばらばらな）数字の組み合わせの束が入っています。この数字の組み合わせを「ノード」と言います。各ノードの中の数字の列を順番に上のリーグ表に当てはめるようにしてチェックしていくのですが、現時点で判明しているＯＧＲ−２４よりも長くなったらチェックする必要がありませんよね。そんなわけで、固定された数字が大きめのものは、中身のノードが少なめになる傾向があります。もちろん、その固定数字の並び方によっては、一概には言えないのですが、まあ、おおむねそういうことです。
中には、一般的なものの１０倍以上も大きなスタブがあったり、逆に、その１００分の１ぐらいしかないスタブもあります。極端に大きなものを引いてきてしまうと、画面上のインジケータが何時間も何日も（！）動かないように見えるほどです。これではちょっと、つまらない・・・・という声もありましたので、J's Factory 踊る暗号解読班では、スタブの大小そのものも楽しんでしまおうと、「デカスタ選手権」を開催しています。ぜひご覧下さい！