読者です 読者をやめる 読者になる 読者になる
スポンサーリンク

大学の「情報理論」(暗号理論を含む) の講義ノートPDF。代数学を使った情報量・符号化・通信路の理論

計算機科学 講義ノート リンク集 数学 代数学 数論 アルゴリズム


情報科学の一分野である「情報理論」(Information Theory)の講義ノート。

勉強しやすいものを集めた。


情報理論のテキストには,暗号に重点をおいた物と,符号理論(Coding Theory)から始める物の2タイプが存在する。

さらに言えば,符号理論も,データ圧縮と誤り訂正の2つに大別される。


ここでは下記のように分類する。

  • (1)暗号と,暗号理論に必要な数学。
    • 要点:初等整数論,素数に関連したアルゴリズム,有限体,公開鍵暗号,エルガマル暗号,ゼロ知識証明。
  • (2)情報のデジタル符号化をテーマにした「情報理論」
    • 要点:シャノンの情報理論。エントロピーと情報量,圧縮,通信路の符号化,誤り訂正。写像や行列など,線形代数を使って表現することが多い。広義では暗号理論を含む。

これらの事項を独学するための資料。

※もし数学が苦手だったり,暗号だけをかじりたい場合,こちらの資料で学ぶとよい。


※情報理論の数学的な土台は,群・環・体の講義ノート線形代数の講義ノートを参照。

※量子コンピュータによる量子情報処理・量子暗号はこちらのノートを参照。


(1)暗号と数学をセットで学べる講義ノート

まず情報理論の中で,特に有名な「暗号理論」のみにテーマを絞る。

符号理論をスキップし,暗号だけ学習できる。


下記は,「初歩的な数学(おもに整数論)」と「初歩的な暗号理論」の2つをセットで学べるテキスト:

素数と暗号・初等整数論とRSA暗号系入門
http://www.math.tohoku.ac.jp/~atsushi...

  • 東北大,18ページ。最初の「プロローグ」が面白い。
  • 内容:整数の合同,ユークリッドの互除法と応用,フェルマーの小定理,RSA暗号系。
  • 引用:“暗号化する手順は公開しているにも関わらず,手順を指定した本人にしか解読できないような暗号”というものは可能(=公開鍵暗号)。。RSA暗号系の安全性は,この“巨大な整数の素因数分解の難しさ”により支えられているのである。


情報数理:暗号理論入門
http://www.u-gakugei.ac.jp/~takalab/i...

  • 学芸大,24ページ。
  • 初等整数論のまとめ(合同式や有限体),現代暗号の基礎(RSA,署名と認証,エルガマル,鍵交換)


暗号理論と代数
http://www.math.sci.hiroshima-u.ac.jp...

  • 広島大,18ページ。
  • 古典的暗号,公開鍵暗号(鍵交換,エルガマル,RSA)


C.E.シャノンの暗号理論
http://repository.kulib.kyoto-u.ac.jp...

  • 京大,15ページ。解説記事という形式。シャノンが情報理論的なアプローチで暗号の強度を上げたという話。
  • 内容:歴史的な背景,暗号とは何か,暗号通信の数学的な表現,曖昧さの導入,完全秘匿,計算量的安全性。
  • 引用:共通鍵暗号は構造上ストリーム暗号とブロック暗号に大きく分けられるが,シャノンは「秘匿システムの通信理論」で,ストリーム暗号における完全秘匿の達成という問題,ブロック暗号においていかに強度を上げることができるかという問題の両方について指摘した。


情報解析学特講・暗号論入門
http://lupus.is.kochi-u.ac.jp/shiota/...

  • 高知大,41ページ。
  • 内容:初等整数論の準備,公開鍵暗号とRSA暗号,平方根の話,ゼロ知識証明,素数判定法・素因数分解法,有限体の基礎知識。


動画で学ぶ:

暗号理論に入門するための,大学の講義の動画。ドイツのルール大学の授業(英語)
http://computer-technology.hateblo.jp/entry/20140519/p2


発展的な内容:

暗号基盤特論
http://www.tcs.ics.saitama-u.ac.jp/~k...

  • 埼玉大。
  • 内容:暗号の攻撃を行なう際に必要となる確率論,一方向関数,識別不可能性,疑似乱数生成器,ゼロ知識対話証明,公開鍵暗号。
  • 紹介文:「暗号の安全性を考察する際,敵対者は乱択アルゴリズムと呼ばれる 乱数を利用するアルゴリズムでモデル化される.乱択アルゴリズムの性能や挙動を 評価するためには確率論の各種ツールが必要で,まず,それらの利用方法を習得してもらう. さらに,暗号の基礎部品である擬似乱数生成器について, 一方向性関数からの構成を通して,(確率論の各種ツールの利用の前提とする) 暗号学における基本的な解析技法を理解してもらう.」

(2)情報の符号化をテーマにした「情報理論」の講義ノート(暗号の話を含む)

次に,情報理論の全般的な入門用ノート。


情報量やエントロピーの話から始まって,符号の圧縮や誤り訂正,さらに暗号へと進む。

情報理論
http://eatz.yz.yamagata-u.ac.jp/jouho...

  • 山形大,54ページ。「情報の量」と「情報の符号化」についての基礎。
  • 内容:情報量,平均情報量,情報源モデル,情報源符号化,通信路容量,通信路符号化などの重要な概念についての理解。


符号理論
http://www.sm.u-tokai.ac.jp/~sugita/C...

  • 東海大,27ページ。
  • 内容:情報伝送モデル,ブロック符号,線形符号,ハミング符号,巡回符号,BCH符号,Reed-Solomon符号。


情報理論 -講義資料- | 北海道大学オープンコースウェア (Hokkaido University OpenCourseWare, HU-OCW, 北大OCW)
http://ocw.hokudai.ac.jp/Course/Facul...

  • 北大。回ごとに分かれている。
  • 内容:情報量とエントロピー,符号化,暗号。


情報暗号理論
http://www.cs.dm.u-tokai.ac.jp/~kikn/...

  • 東海大。各回ごと。
  • 内容:エントロピー,情報圧縮,誤り訂正,共通鍵暗号,公開鍵暗号。


情報理論
http://www.tuat.ac.jp/~s-hotta/info/

  • 東京農工大。各回ごとのスライド。
  • 内容:確率分布と確率過程から始めて,通信路符号化,線形符号と巡回符号。



演習問題と解答:

情報理論
http://www.eva.ie.u-ryukyu.ac.jp/~end...

  • 琉球大。情報源のエントロピーから,通信路の符号化まで。


動画で学ぶ:

MITの講義動画「情報理論」(情報とエントロピー)。ビットと符号化から量子情報まで
http://study-guide.hatenablog.jp/entry/20140519/p2



関連する記事:

ゲーム理論の講義ノートPDF。応用を含めた講義資料 (戦略と意思決定の方法論)
http://language-and-engineering.hatenablog.jp/entry/20140516/GameTheoryPDFNot...


「ラムダ計算」を独学で学習するための,講義ノートやPDFのリンク集 (復習用の問題付き)
http://language-and-engineering.hatenablog.jp/entry/20130313/LambdaCalculusBa...


「オペレーティングシステム論」の講義資料・ノートPDF。OSのプロセス管理やメモリ管理,ファイルシステムを勉強
http://language-and-engineering.hatenablog.jp/entry/20140510/OperatingSystemL...


大学の「制御工学・古典制御論」の講義ノートPDF(演習問題と解答つき)周波数領域での線形システムの解析
http://language-and-engineering.hatenablog.jp/entry/20140618/ClassicalControl...


金融工学・数理ファイナンス理論の講義ノートPDF (デリバティブや証券・オプション,ポートフォリオの経済学入門)
http://language-and-engineering.hatenablog.jp/entry/20140515/FinancialMathema...