読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

アリスとボブは妥協する

手始めに、ちょっと妥協すると大きな効果が得られるという例をお見せして、全体の入門と致しましょう。何を妥協するのかというと、アルゴリズムがいつでも正しい答えを出すということを、稀に間違った答えを出しても構わないとする、もしくは、稀にアルゴリズムの動作が非常に遅くなる、などです。ここで皆様には、「そんなふざけた話があるか!」とお叱りを受けるかもしれません。しかし、「少しは妥協する」ことの利益を平均して見た場合、「全く妥協しない」場合に比べて大きく勝るのであれば、ある程度は妥協した方が良い場合もあるのではないでしょうか?アルゴリズムが失敗したときにそこまで極端なデメリット(例えば、人が死ぬ、会社が潰れるほどの損失を負うなど)がない場合は、常時のメリットが全体を通して支配的になると考えられます。それならば、「少しは妥協する」という選択をするのも悪くはないでしょう。これが今回掲げるテーマです。

また、今回扱う内容は、ランダムの力を借りることで、それほど複雑なことをしなくても上手く働くものが作れることの例にもなっています。これは、いわば情報科学における一種の思想とも言えましょう。そんなことを言って、ランダムというこちらからは制御できないものを利用するなどと、そんな大層なことができるのか?と思われるかもしれませんが、ランダム性に利用価値があることは、実はそれほど意外なことではないのです。これについては別の項目で触れることにします。

2人が持ってるデータは等しい?

アリスとボブ*1は、ある大きなデータのコピーをそれぞれ持っているとします。2人は「自分の持っているデータは相手のものと完全に同じだろうか?どこかで改変などが発生してないだろうか?」と心配になりました。そこで2人はメールのやり取りでそれを確かめようと考えます。しかし、全てのデータを送ってチェックするのはあまりにも非効率であるため、どうにか少ない通信量で済ませられないかと2人は思いました。さて、2人はどうしたら少ない通信量で互いのデータが完全に同じであることを確かめられるでしょうか?

現実的な問題としては、例えば、インターネット上から巨大なデータをダウンロードしたとき、それが元のデータとちゃんと一致しているかどうかを確かめたいというものがあります。通信路においては誤りが発生することがありますし、時には何者かの攻撃によってデータを改変される可能性もあるためです。大量のデータの通信には、送信者、受信者、通信路のいずれにも大きな負荷がかかりますから、チェックに要する通信量を少なく抑えたいというのは当然の要求でしょう。

それでは、アリスとボブがどうやってこの問題を解決したかを見て行きましょう。(注意:今回説明する方法はあくまで情報科学の考え方を説明するのためのものであって、現実で用いることを想定してはいません。具体的には、敵対者による人為的な改変には対応できません。現実的にはハッシュ値というものを照合することでデータの改変の有無のチェックを行います。)

アリスはサイコロを振る

この問題を解決するために、アリス(A)とボブ(B)は次のような方法をとりました。チェック対象のデータは n ビットの0と1の列とし、アリスのものを a_1 a_2 \dots a_n、ボブのものを a_1 a_2 \dots a_n で表します。また、(非負)整数はすべて2進表記で表されるものとします。

  1. A: 適当な大きさの素数 p を選ぶ。
  2. A: 整数 r \in \{ 0, 1, 2, \dots, p - 1 \} をランダムに選ぶ。
  3. A: S_A := \sum_{k = 1}^n a_k r^k \;\mathrm{mod}\; p を計算する。ここで、a \;\mathrm{mod}\; pap で割ったときの余りを表す。
  4. A: 3つの数の組 (p, r, S_A) をボブに送る。
  5. B: アリスと同様に、S_B := \sum_{k = 1}^n b_k r^k \;\mathrm{mod}\; p を計算する。
  6. B: S_A = S_B ならば、両者のデータは一致している、そうでなければ一致していないと判断し、結果をアリスに伝える。

ステップ2で、アリスが整数 r を選ぶために乱数を使う(サイコロを振る)ところが、この方法の鍵です。*2

f:id:azapen6:20121224225335j:plain

この方法を考えたところで、問題は3つあります。まずは、そもそもこの方法が上手くいくのか?もしそうならば、素数 p はどの程度の大きさにとるべきか?そして、以上の手続きを少ない計算量で実現できるか?です。

素数 p の大きさは、当然ですがチェックすべきデータのビット数 n よりずっと少ないビット数で表される程度の数であるべきです。例えば、\log n *3ビットの定数倍程度が望ましいでしょうか。もしくは、pn のある多項式で抑えられるとも言えます。仮に pm \ll n ビットで表されるとすると、r, S_A < p なので、rS_A も高々 m ビットで表されることになります。よって、アリスがボブにチェックのために送るデータの長さはおよそ 3m ビットとなります。(細かいことを言うと、3つ組の数を表現するための方法をちゃんと決めてやる必要があります。成分の切れ目を表すために実際のビット数は 3m より少し多くなります。適当な方法を用いると、3m + O(\log m) ビットで表すことができます。)

計算量で特に問題となる部分は、アリスが素数 p を選ぶところと、和 A および B の中に出てくるべき乗 r^k および \mathrm{mod}\; p の計算でしょう。n は非常に大きい数なので、これらの計算に n^2 の時間を要するなどは論外です。和 A および B の項を1つ加えるごとの計算量が m多項式回のビット演算で抑えられる程度ならば、(m の大きさによりますが)現実的に実行できると考えられます。さて、先に答えを言ってしまいますが、その計算は適切な方法を用いれば、ちゃんと現実的な計算量で実行できます。と言ったところで、計算量の問題についてはこれ以上立ち入らないことにします。*4

ひとまず今回は、上の方法が上手くいくために十分な、素数 p の大きさを決定します。

有限体上の多項式の零点の数

今回説明する中で最も高度と思われる概念は「有限体」というものです。これは、大雑把に言えば、四則演算が入った数の集合で、かつ、その要素数が有限であるものです。ここでは、先ほどの素数 p の大きさを決定するために、「d多項式は、高々 d 個の零点しか持たない」という高校で習うような事実を使います。ただ、高校までの数学と違うのは、それを有限体という普通でない(?)数の世界で考えているという点です。

数学において、「体(たい)」とは、0を含む集合であり、その中で足し算、引き算、掛け算、および、0を除いた要素による割り算が自由にでき、足し算と掛け算に関する交換法則、結合法則、および、分配法則が成り立つもののことを言います。例えば、有理数、実数、複素数は体ですが、整数は体ではありません。というのも、整数の世界では1を2で割ったものにあたる要素が存在しないためです。有限体とは、体であって要素数が有限であるもののことです。

我々が考える有限体は、それらの中でも最も簡単な「素数 p による剰余体 \mathcal{F}_p」というものです。何やら難しいことを言っているようですが、要するには素数 p による割り算の余りの集合 \{ 0, 1, \dots, p - 1 \} のことです。この中で足し算、引き算、掛け算、および、0を除いた数による割り算が自由にできるから、剰余「体」と呼んで有限体の仲間に入れているのです。

では、それらの演算がどうやって定義されるかということを見ていきましょう。整数上の演算との区別のため、体上の演算は上に点をつけて \dot{+} などで表します。a, b \in \{ 0, 1, \dots, p - 1 \} として、それらの演算の結果が 右の集合の中に収まっていることが言えればいいわけです。

足し算と掛け算については、そのまま計算して素数 p で割った余りを返すだけです。

a \dot{+} b := (a + b) \;\mathrm{mod}\; p

a \dot{\times} b := (a \times b) \;\mathrm{mod}\; p

で定義された演算の結果が \{ 0, 1, \dots, p - 1 \} に収まっていること、および、交換法則が成り立つことは明らかでしょう。結合法則と分配法則の証明は省略します。

引き算については、次の定義を用いて足し算に帰着します。

a \dot{-} b := a \dot{+} (-b)

ここで、-b

b \dot{+} (-b) = 0

を満たす数です。これは足し算の定義から分かるように

-b = p - b

となります。

割り算についても引き算と同様に、掛け算に帰着して定義します。すなわち、b \neq 0 のとき、

a \dot{/} b := a \dot{\times} b^{-1}

です。ここで b^{-1}b の逆数で、

b \dot{\times} b^{-1} = 1

を満たす数です。しかしながら、このような数が存在することは自明ではありません。

ここで p素数であることが効いてきます。実は、p素数であることは、b \in \{ 1, \dots, p - 1 \} のすべてに対して逆数が存在することの必要十分条件なのです。実際に逆数を見つけるには、拡張ユークリッド互除法というアルゴリズムを用いますが、ここでは省略します。

かくして、b \in \{ 0, 1, \dots, p - 1 \} に四則演算が備わったので、これを \mathcal{F}_p と書いて、有限体と見なします。上では定義のためにあえて演算に別の記号を使いましたが、これから先では \mathcal{F}_p 上の演算も普通に a+bab のように書くことにします。

有限体上の多項式とは、係数がすべてその体の要素であるような多項式です。多項式同士の計算をするときは、係数の演算を体上の演算で行います。次数の定義は普通の多項式と同じです。体 F 上の多項式x を変数とするものの全体は、F[x] と書きます。

それでは、次節で使う命題を述べてこの節を終えましょう。

補題1: 多項式 f \in \mathcal{F}_p [x] の次数が d 以下で、かつ、f が恒等的に0でないとき、r \in \mathcal{F}_pf(r) = 0 を満たすもの(「根(こん)」もしくは「零点(ゼロてん)」といいます。)は高々 d 個しか存在しない。

これは、体上では、a, b \neq 0 ならば ab \neq 0 である(「零因子(ゼロいんし、れいいんし)」が存在しない)ことの帰結です。(このことを、体は「整域(せいいき)」であるといいます。先ほど体の仲間に入れなかった整数も整域ではあるので、同じ命題が成り立ちます。)

素数 p の大きさの評価

それでは、本題に戻って、素数 p をどの程度にとれば上で示した方法が上手くいくかを調べましょう。鍵になるのはもちろん先ほどの補題1です。言い換えると、

多項式 f, g \in \mathcal{F}_p [x] の次数がそれぞれ d 以下で、かつ、f \neq g のとき、r \in \mathcal{F}_pf(r) = g(r) を満たすものは高々 d 個しか存在しない。

となります。右辺の g を左辺に移行すれば補題1に帰着できますね。もう少し我々の考えている問題に近づけると、

\mathcal{F}_p 上の多項式 f_A(x) := \sum_{k = 1}^n a_k x^k および f_B(x) := \sum_{k = 1}^n b_k x^k について、ある k に関して a_k \neq b_k のとき、r \in \mathcal{F}_pf_A(r) = f_B(r) を満たすものは高々 n 個しか存在しない。

ここで、S_A = f_A(r) また S_B = f_B(r) ですから、ある k に関して a_k \neq b_k のとき、ランダムに r \in \mathcal{F}_p を選んだときに S_A = S_B となる確率は、\mathcal{F}_p の中で n 個のものが占める割合 n / p で抑えられることが判ります。逆に、すべての k に関して a_k = b_k のときは、もちろん必ず S_A = S_B が成り立ちます。

もし、アリスとボブがチェックの誤り率を \delta 以下に抑えたいとすれば、n / p \leq \delta から、p \geq \lceil n / \delta \rceil にとればいいということになります。

では、そのような p の上限はどこまででしょうか?それについては、Chebyshev によって示された次の定理を用いることで解決します。

定理2: すべての正の整数 k について、k < p \leq 2k である素数 p が存在する。

よって、アリスが選ぶべき素数 p の範囲は、\lceil n / \delta \rceil \leq p \leq 2 \lceil n / \delta \rceil に決まりました。

これより、素数 p を表すビット列の長さは m \leq \log (n / \delta) + 2 で抑えられます。つまり、アリスとボブがチェックのために要する通信は、およそ

3m \approx 3 \log (n / \delta)

ビットということになります。

具体的に、n = 2^{43} ビット(1TB)、誤り率を \delta = 2^{-40} (約1兆分の1)とすると、

3 \log (2^{83}) = 3 \times 83 = 249

ビット程度の通信で済むということになります。実際は符号化の都合でもう少し増えますが、どう考えても対象のデータに比べて圧倒的に少ない通信量で、誤る可能性もほとんど無視できるレベルで、両者のデータが等しいかどうかのチェックが行えるということになります。

アリスとボブは1兆分の1やその程度で誤る可能性を妥協したことで、とてつもなく少ない通信量でデータが完全に一致しているかのチェックを行うことができたのです。これこそが妥協の効果であり、また、ランダムの力の一例なのです。

次回は、一歩も妥協しないとえらいことになる、という話をしたいと思います。では。

*1:計算機科学系の人は、2人の人物を例に出すときに慣例的にこの名前を使います。Alice と Bob、つまりAさんとBさんですね。Cさんは出現頻度が低いせいかそういう慣習がないので、チャーリー(Charley)やキャロライン(Caroline)などまちまちです。一方で、暗号業界では3人目は Eve(イヴ)であることが多いです。これは eavesdropper(盗聴者)に由来しています。

*2:実際の計算では、素数pを選ぶときにも乱数を使います。これこそは少しの妥協が大きな効果をもたらすことの極めて重要な例です。しかしながら、今回はその内容には立ち入りません。

*3:これ以後のすべてに共通して、対数 log の底を断らないときは、暗黙に2を底とします。これは情報科学の世界でよくある慣例です。自然対数には ln を用います。

*4:素数生成」「繰り返しべき乗法」などのキーワードで調べてみてください。それほど難しいことはやりません。