データの並び順で別のデータを表す方法

拙作「梅・竹・桜」のヘルプに、こんなことが書いてあります。

(256色)画像のパレットの順番を入れ替えることで、そこに約210byteのデータを隠せる。

どういうことかを、4つのデータを使って説明します。

4つのデータ(0,1,2,3)を順番に並べる並べ方は、次に挙げる24通りで、そのそれぞれに00からの連番を振ります。

 0 = 0,1,2,3
 1 = 0,1,3,2
 2 = 0,2,1,3
 3 = 0,2,3,1
 4 = 0,3,1,2
 5 = 0,3,2,1
 6 = 1,0,2,3
 7 = 1,0,3,2
 8 = 1,2,0,3
 9 = 1,2,3,0
10 = 1,3,0,2
11 = 1,3,2,0
12 = 2,0,1,3
13 = 2,0,3,1
14 = 2,1,0,3
15 = 2,1,3,0
16 = 2,3,0,1
17 = 2,3,1,0
18 = 3,0,1,2
19 = 3,0,2,1
20 = 3,1,0,2
21 = 3,1,2,0
22 = 3,2,0,1
23 = 3,2,1,0

これが並び順とデータの対応表になります。

これを踏まえて1つの例を挙げます。

ある時、当選が4本あるクジ引きが行われ、佐藤さん、鈴木さん、高橋さん、田中さんの4人が当選しました。
そして、当選者一覧として次のように発表が行われました。

高橋、佐藤、鈴木、田中

0 = 佐藤、1 = 鈴木、2 = 高橋、3 = 田中
と事前に決めておけば、上の当選者一覧は 2,0,1,3 となり、先の対応表から 12 というデータが得られます。
当選者一覧という本来のデータに 12 という別のデータが隠されていると言えるのです。

このように、データの並び順に意味が無いデータは、その並び順を使って別のデータを表すことができます。

どのくらいのデータを表すことができるかと言えば、データの個数がN個で log2(N!) ビット のデータが表せます（log2は底が2の対数。!は階乗）。
画像データの256色パレットの場合、log2(256!) ≒ 1684 bit ≒ 210 byte のデータが隠せることになります。

と、ここまでは分かっていたのですが、実現方法が思い付きませんでした。

あれから８年半。

ようやく実現方法に至りました。

---

【定義】

ダミーのデータ（上記例での当選者に相当）の個数をN個とし、D0 = {d0[0], d0[1], ..., d0[N-1]}と表す。

全ての i, j (i ≠ j) において d0[i] ≠ d0[j] が成り立つものとする。

隠したいデータを M とする。
M は log2(N!) ビット以下のデータである。

---

【データの隠し方】

M を整数と見なし、次の計算をする。

m[0] = M
p[i] = m[i] ÷ (N - i - 1)! の商
m[i+1] = m[i] ÷ (N - i - 1)! の余り
(i = 0, 1, ..., N-1)

p[i] は、0 ≦ p[i] ＜ N - i を満たす整数になる。

x[0] = d0[p[0]]

D0 から x[0] を取り除いたものを D1 とする。
D1 = {d1[0], d1[1], ..., d1[N-2]}
　　　　| d1[i] = d0[i] (i < p[0])
　　　　| d1[i] = d0[i + 1] (i >= p[0])

x[1] = d1[p[1]]

D1 から x[1] を取り除いたものを D2 とする。
D2 = {d2[0], d2[1], ..., d2[N-3]}
　　　　| d2[i] = d1[i] (i < p[1])
　　　　| d2[i] = d1[i + 1] (i >= p[1])

同様に繰り返して

X = {x[0], x[1], ..., x[N-1]}
が最終的に出力するデータとなる。

---

【データの取り出し方】

a[0] = 0

x[0] が D0 の中の何番目のデータなのかを探す。
(d0[p[0]] = x[0] を満たす p[0] を探す)

次を計算する。
a[1] = a[0] + p[0]×(N - 1)!

D0 から x[0] を取り除いたデータ D1 から、x[1] が何番目なのか探す。
(d1[p[1]] = x[1] を満たす p[1] を探す)

次を計算する。
a[2] = a[1] + p[1]×(N - 2)!

この操作を繰り返す。
a[i + 1] = a[i] + p[i]×(N - i - 1)!

そして、
M = a[N]
が隠してあったデータ。

---

今考えると、非常に単純な仕組みです。
なぜ思い付かなかったのかな ＞ 当時の自分。
たぶん、多倍長整数演算という発想が無かったんだろうな。

上の方法だと階乗が結構出てきますが、p[i] を p[0] からじゃなくて p[N - 1] から計算したら、階乗計算が必要なくなるんじゃないかと言ってみるテスト。

今日の一冊
	秘密室ボン 作者: 清涼院 流水 出版社/メーカー: 講談社 発売日: 2002/12 メディア: 新書