代数,情報・暗号理論

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

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

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

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

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

置換の基礎(互換・偶置換・奇置換・符号の意味)

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 \left(\sum a_k \right) \log\dfrac{\sum a_k}{\sum b_k}

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

有理数と無理数の稠密性

任意の実数 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)

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

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

有限体(ガロア体)の基本的な話

位数(要素数)が qq の有限体が存在する     \iff ある素数 pp と正の整数 nn が存在して q=pnq=p^n

→ 有限体(ガロア体)の基本的な話

パリティビットと誤り検出

1の数の偶奇の情報を付加することで誤りを検出できる(ことがある)。

→ パリティビットと誤り検出

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

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

I(X;Y)=xXyYPX,Y(x,y)logPX,Y(x,y)PX(x)PY(y)=xXyYPX,Y(x,y)logPX,Y(x,y)PX(x)PY(y)\begin{aligned} &I(X;Y)\\ &= \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)}\\ &= \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)} \end{aligned}

で定義する。

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

環の定義とその具体例

足し算とかけ算ができるような代数系を環(かん)という。

整数や有理数,多項式,行列などの「和」と「積」をもつような対象を抽象化した概念をといいます。

→ 環の定義とその具体例

環の基礎用語~準同型・部分環・イデアル~

この記事では環論において極めて重要な準同型・部分環・イデアルについて説明します。

→ 環の基礎用語~準同型・部分環・イデアル~

体の基礎用語~拡大体と拡大次数

足し算・引き算・掛け算・割り算ができるような代数系を体(たい)という。

この記事では,実数や複素数のように,商も計算できる対象「」について解説します。

→ 体の基礎用語~拡大体と拡大次数

ギリシアの三大作図問題

三大作図問題

三大作図問題とは

  • 円積問題
  • 立方体倍積問題
  • 角の3等分問題

の3つのことである。

→ ギリシアの三大作図問題