1. 高校数学の美しい物語
  2. 代数,情報・暗号理論

代数,情報・暗号理論

    更新日時 2021/03/11

    集合の濃度と可算無限・非可算無限

    有限集合の大きさは要素数ではかれる。

    無限集合の大きさの表現には濃度を用いる。

    高校数学の範囲を逸脱していますが非常に有名な話題です。

    → 集合の濃度と可算無限・非可算無限

    置換と偶置換・奇置換に関する基礎的なこと

    nn個のものを並び替える操作を置換と言う。

    置換は行列式の定義に使われていたり,ルービックキューブの理論などいろいろな対称性を扱うために使われたりと様々な場面で登場する重要な概念です。

    → 置換と偶置換・奇置換に関する基礎的なこと

    情報量の意味と対数関数を使う理由

    確率 p(>0)p ( > 0) で起こる事象を観測したときに得られる(自己)情報量を log2p-\log_2 p bitと定義する。

    情報理論の最も基本的な概念である情報量(自己エントロピー)について解説します。

    → 情報量の意味と対数関数を使う理由

    群の定義といろんな具体例

    集合 GG とその集合上の二項演算 ff の組がとある条件を満たすときに,そのペア (G,f)(G,f) を群と言う。

    抽象代数学の最も基本的な概念の一つで,数学のいろいろなところに登場する「群」について。

    まずは二項演算について説明し,群の定義,具体例へと進んでいきます。

    → 群の定義といろんな具体例

    RSA暗号の仕組みと安全性

    公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について解説します。数学がまあまあ得意な高校生なら理解できるレベルの内容です。

    → RSA暗号の仕組みと安全性

    (k,n)しきい値法とシャミアの秘密分散法

    多項式補間を使うことで「故障に強い」かつ「漏洩に強い」秘密情報の保管が実現できる。

    (k,n)(k,n) しきい値法の意味,嬉しさについて説明し,それを具体的に実現する方法としてシャミアの秘密分散法を解説します。

    → (k n)しきい値法とシャミアの秘密分散法

    対数和不等式の証明と応用

    対数和不等式(Log sum inequality)

    a1,a2,,an,b1,b2,,bna_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n を正の数とするとき,

    aklogakbk(ak)logakbk\sum a_k\log\dfrac{a_k}{b_k}\geq(\sum a_k)\log\dfrac{\sum a_k}{\sum b_k}

    主に情報理論で活躍する不等式です。この記事では k=1n\displaystyle\sum_{k=1}^n のことを \sum と書きます。

    → 対数和不等式の証明と応用

    有理数と無理数の稠密性

    任意の実数 a,b(a<b)a,b\:(a<b) に対して,

    a<q<ba< q< b を満たす有理数 qq が存在する(有理数の稠密性)。

    a<x<ba< x< b を満たす無理数 xx が存在する(無理数の稠密性)。

    → 有理数と無理数の稠密性

    同値関係といろいろな例

    数学の様々な場面で登場する重要な概念「同値関係」について解説します。同値関係とは,大雑把には「仲間であるという関係」です。前半は定義なので少し堅苦しいですが,後半はいろいろな例が登場します!

    → 同値関係といろいろな例

    差積の意味と置換の符号が定義できることの証明

    nn 個の変数の全てのペアの差の積: Δ(x1,,xn)=1i<jn(xjxi)\Delta (x_1,\cdots,x_n)=\displaystyle\prod_{1\leq i<j\leq n}(x_j-x_i)

    を差積(最簡交代式,基本交代式)と言う。

    → 差積の意味と置換の符号が定義できることの証明

    相互情報量の意味とエントロピーとの関係

    (離散の)確率変数 XXYY の間の相互情報量 I(X;Y)I(X;Y) を,

    I(X;Y)I(X;Y)

    =xXyYPX,Y(x,y)logPX,Y(x,y)PX(x)PY(y)\displaystyle=\sum_{x\in X}\sum_{y\in Y}P_{X,Y}(x,y)\log\dfrac{P_{X,Y}(x,y)}{P_X(x)P_Y(y)}

    で定義する。

    → 相互情報量の意味とエントロピーとの関係

    1. 高校数学の美しい物語
    2. 代数,情報・暗号理論