この記事を読んでくださった皆様おはこんばんちは，ゆうぴっぴ(@_yu_pippi_)です．
ついに弊学校の職員さんが参加するなど，なんかアドベントカレンダーが盛り上がっているのですみッコから参戦しようかなと思います:)
過去記事を見ていただくとわかるのですが
#####「また秘密分散じゃねーか！！」
と言わずにお付き合いくださいｱﾁｮｯﾄ石投げないでください
秘密分散
秘密分散1とはかの有名なShamir先生が考案した，
「みんなで秘密を管理しよう」
という技術です．
といってもファイルをコピーして複数人に渡すのでは本末転倒ですので，「シェア」と呼ばれる情報に分散(変換)されて，それぞれに配布して管理します．
また秘密情報が欲しくなったら必要な分だけ集めて復元をします．
これらは分散処理を行う時点でパラメータとして指定することができます．便利便利;)
現在いくつかの手法があり，ファイルの容量効率が良いものや，暗号化と組み合わせて秘密分散するものなどあります．
(私の過去記事です)
秘密分散と触れ合おうの話
Shamirの秘密分散
先程簡単に説明した秘密分散のうちの一つです．
n個のシェアを生成します．つまりn人で情報を管理できるわけですね．
そしてk個のシェアから復元が可能です．またk-1個のシェアからは情報が全く漏れません(情報理論的安全)．
その数理部分ですが，この方法では定数項を秘密情報Sとするランダムなk次多項式を生成します．
f(x)=S+\sum_{i=1}^{k}{a_i}x^i
ここにIDやらなんやらの数字を入れて，そのIDと関数の値のペアをそれぞれに渡して管理します．
k個以上のシェアから復元できる，というのはk個以上集めると方程式がk個立ちますので，連立方程式を解くことで定数項がわかるわけです．
まあ愚直に連立方程式を解くのもよいですが，ラグランジュ補間2という多項式補間を用いるといい感じに解けるので便利です\ﾍﾞﾝﾘ/
拡大体
この拡大体というのが少しばかりハードルが高いです．
まずは体
「群論」という数学の分野の仲間で，端的に言えば体(たい)は四則演算が閉じている集合のことです．
「ガロア理論3」って聞いたことある方もいらっしゃるのではないでしょうか．
うまく数を集めてきて，いい感じの演算を定義すると嬉しい集合ができるよ！という感覚です(雑)．
例として，日常的に使っている実数全体の集合は体となっています．演算も普段使っている四則演算です．
こう聞くと少し身近に感じませんか？
その体に，新しい数を導入して，数の世界を広げたものが拡大体です．
例えば実数全体の集合に虚数単位iを導入すると複素数体となります．複素数は実数を拡大したものなわけですね．
また複素数全体は実数とほぼ同じような四則演算ができますし，複素数同士の演算結果は複素数になりますので，閉じています．
だんだん体の気持ちがわかってきたのではないでしょうか^^
そして今回は符号理論でも使われる体を使います．
この体はbit演算と相性がよく，また普通の体と違って離散値のみを扱うため，実数で計算したときのような誤差が生じません．
では構成していきましょう！
まず，0と1のみからなる体を考えます．
F_2=\{0,1\}
そして表のように演算を定義します．
足し算はこう
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
そしてかけ算はこう
| * | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
すると加減乗除で0or1の二項演算は必ず0or1になりますので閉じます！
これで小さな体が作れました．
またこれは"2"で割ったあまりの集合とも見れますね．
そして拡大体へ ――
ここで，「既約多項式」というものを考えます．これは既約，つまり因数分解できない多項式のことです．
先程の体の要素を係数にもつ任意の多項式を，たとえば
f(x)=x^2+x+1
で割ったあまりの集合を考えます．
係数は0or1ですので，
F_4=\{0,1,x,x+1\}
となります．ここで，仮想的に既約多項式の根αを考えてみます．
これを先程の小さい体に追加してあげます．
この根が存在するということは
x^2-\alpha^2=(x+\alpha)(x-\alpha)
であるといえます．この式を先程の既約多項式と照らし合わせると
x+1=\alpha^2
のようになっています．つまり
F_4=\{0,1,\alpha,\alpha^2\}
ともかけるわけですね！
こうして小さな体からちょっとだけ大きな体をつくることができました．これを体の拡大4といいます．
こんな感じで，考える既約多項式を変えるとより大きな体が構成できます．
今回は
f(x)=x^8+x^4+x^3+x^2+1
という既約多項式を考えます．
さっきは2次の既約多項式で要素が4つでしたが，今回は8次ですので要素は256個になります，キリがいいですね :)
このときの計算はどうするんだ！という疑問も出てくるころでしょうか．
足し算については「多項式のすがた」を用いて各次の項ごとに計算して2で割ったあまりをとってやればいいですね．
かけ算は「べきのすがた」によってかけて，指数を体の要素数-1で割ったあまりのものを使えばよいです．
こんな感じです．
x+(x+1)=2x+1=1 \\
\alpha\times\alpha^2=\alpha^3=\alpha^0=1
多項式の計算のほうをじーーーーーーーっと各次数に注目していただくと，XORに見えてきませんか？
また，べき計算のほうは指数部分をじーーーっとみると(A | B) & (多項式の次数-1)というふうにも見えます．
これがうれしいポイントですね，みなさんもうれしいとおもいます．
以上のようにして拡大体を構成しました．
ついに本題
ここまで長かったですね...
あとほんの少しですのでもう少しお付き合いください！
前に紹介した，Shamirの秘密分散は，加減乗除について閉じていれば構成できるわけです．
つまり我々が先程必死こいて構成した拡大体でもできるではないかと，そういうわけです．
ランダムな多項式は体の要素を係数にもつk次多項式を生成してやります．
このときに使う足し算だったりかけ算だったりをXORだったり，(A | B) & (多項式の次数-1)を使ってあげればいいわけです．
体では逆演算も可能ですので引き算も割り算もできます，四則演算ができますのでラグランジュ補間もできるようになります．
ということは
秘密分散を拡大体上で作れた！
ということになります！おめでとうございます！あなたは天才！最強！
最後はな〜んだ，そんなことかって感じでしたが，取り急ぎつくることができましたね．
大したものじゃないですが，実装例も載せておきます．
もしよければ「ここ変だよ！」ってPR投げたり，(@_yu_pippi_)に連絡くれたりするとありがたいです．泣いて喜びます．
そんな感じで長々とお付き合いいただきありがとうございました！
拙い文章ですが読んでくださった皆様に感謝します...ｱﾘｶﾞﾄ
それでは皆さんよいお年を〜〜〜