ベイズの定理の導出から, モンティ・ホール問題への応用まで.

ベイズの定理の導出

事象 $A$ が発生する確率を「$P(A) = A$ が発生する確率 $\div$ すべての事象の数」と書くとき, ベイズの定理は

と定義される. 以下ベイズの定理を導出する. 例として, 起こり得る全ての事象の数を $200$, 事象 $A$, 事象 $B$(以下単に $A$, $B$ と書く)が発生した回数をそれぞれ $60,\ 40$ とし, $A$ および $B$ が発生した確率を $10$ とする. 簡単のために, この事象関係を表すベン図を次に示す¹.

以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理¹については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.

エルガマル暗号が離散対数問題の応用であることは認知していたものの, きっちりと自分でまとめたことが無かったと思うので, それに関連する諸々の前提についてもふまえて, 一度書くことにした. また, その処理系を実装した. 本エントリでは, 同暗号プロトコルの話の前にまず前提を示し, その後, 実装の観点から見た要点を示す.

数論的関数の用語やその関連について整理したかったので書くことにした.

数論的関数

数論的関数は, 定義域が正整数 $\mathbb{Z}^{+}$ である複素数を値にもつ関数である. すなわち

をいう.

加法的関数

加法的関数は以下で定義される.

大学のレポート内で De Bruijn Sequence について書く機会があった. これまた以前と同じく, 折角なのでこちらのブログにも, 若干内容を変えつつ載せておくことにした.

De Bruijn Sequence は, オランダ人の数学者 Nicolaas de Bruijn に因んで命名された系列で, 特定の長さのすべての組み合わせを含む系列である. 次数 $n$ の $k$ 種類に関する De Bruijn Sequence $B(k, n)$ は, 長さ $n$ で表現可能なすべての部分列によって構成される. 次元数 $2$ (すなわちバイナリ) の De Bruijn Sequence は $B(2, n)$ であり, $n$ ビットの固有な部分系列から成る $2^n$ ビット長の系列である. 例えば, $B(2, 3)$ は $00011101_{(2)}$ であり $n$ に対する有向グラフが下図¹のように示される.