▽ﾋﾞｯｸﾞ･ｵｰ記法(Big-O notation)
●03/07 10:43 よく見る記法
概要
計算機科学関連の書物に､よく｢この関数は O（n） である｡｣のような O の表現を突然見かけたりします｡ これは､ﾋﾞｯｸﾞ･ｵｰ記法といって､表記を簡単にする工夫です｡ 議論を正確にして､かつわかりやすくするために積極的に行う略記です｡
省くことは不正確にする事とは違います｡ ある関数の性質を説明するときに 2n とか 3n といった係数のちょっとした違いが結果にたいした影響を及ぼさないと知っているとき､係数の省略を考えたとします｡ しかし､単に n と書いてしまうと不正確になってしまいます｡この O(ｵｰ) には｢係数が省かれているから忘れないでね｡｣という意味があると考えてください｡ 以下のような表現は特に良く見かけます｡
数値同士の場合､n<m のように不等号という表現があります｡関数同士で同様に比較が出来たら便利でしょう｡この記法は､関数同士の比較に用いられます｡
定義

▽公開鍵暗号(public-key cipher)
●03/07 09:48 公開鍵暗号
最近話題の､公開鍵暗号とは････
概要
公開鍵(public-key) という言葉は､広義には情報秘匿のほか､署名や認証などかなり広い技術を指します｡以下では 公開鍵技術の狭義の意味(情報秘匿用途)を説明します｡ 公開鍵暗号(public-key cipher) は､公開鍵(=暗号鍵)が敵に知れても､第三者に文書の解読が出来ない技術です｡ (参照→暗号)
もちろん復号鍵(=私有鍵)は敵に知られては困りますが､共通鍵暗号(symmetric cipher) に比べて鍵の管理が簡単です｡以下は､主な公開鍵暗号ｱﾙｺﾞﾘｽﾞﾑです｡
公開鍵暗号は､大別すると巨大な数の素因数分解(prime factorization problem) がとても難しいことを安全性の根拠とする素因数分解型 と巨大な群の離散対数問題(descrete logarithm problem) が難しいことを安全性の根拠とす

▽計算複雑性(computational complexity)
●03/07 05:28 計算複雑性(computational complexity)
Team TripleFalcon. http://www.triplefalcon.com/
概要
ある問題を計算するのが簡単な問題がある一方､計算するのが難しい問題もあることを私たちは直感的に知っています｡しかしながら､もう少し論理的に難しさとは何かについて考えることはできないものでしょうか｡
そのような直感を表現する方法は様々に提唱されましたが､中でもｺﾝﾋﾟｭｰﾀ技術者に最も適した表現方法としてﾁｭｰﾘﾝｸﾞ機械（Turing machine)と呼ばれる概念上の機械を考えて､機械が計算で消費する資源が大きいとき問題が難しいと考える､という方法があります｡そのような資源の消費量を計算量と呼びます｡（参照→ﾁｭｰﾘﾝｸﾞ機械）
ﾁｭｰﾘﾝｸﾞ機械が消費する資源としては､動作開始から動作終了までの時間による､時間計算量（関数δによる状態遷移回数）とか使用したﾃｰﾌﾟのﾏｽの数による領域計算量に着目

▽共通鍵暗号(symmetric cipher)
●03/07 04:13 共通鍵暗号(symmetric cipher)
概要
共通鍵暗号(symmetric cipher) は､暗号鍵と復号鍵が共通の暗号です｡(参照→暗号､ﾌﾞﾛｯｸ暗号､ｽﾄﾘｰﾑ暗号､公開鍵暗号)
共通鍵暗号には､ﾌﾞﾛｯｸ暗号(block cipher) とｽﾄﾘｰﾑ暗号(stream cipher) の種別があります｡
名称 概要
ｽﾄﾘｰﾑ暗号 文字単位､ﾋﾞｯﾄ単位毎にｽﾄﾘｰﾑ的処理を行う
ﾌﾞﾛｯｸ暗号 固定長のﾌﾞﾛｯｸ単位で処理
以下に､Alice が Bob に文書を送る方法を示します｡
ALICE(送信者)は鍵で文書を暗号化し､BOB(復号者) は､鍵で文書を復号します｡ 鍵が敵に知れた場合､第三者に文書が解読されます｡ Bob (受信者)が鍵を漏洩させないように配慮するのは当然ですが､ 暗号鍵と復号鍵が同一ですから Alice(送信者) も同様に慎重に鍵を管理しなければなりません｡
大は小を兼ねるの意味合いから言えば､公開鍵

▽暗号(cipher)
●03/07 03:35 暗号(cipher)
Team TripleFalcon. http://www.triplefalcon.com/
概要
暗号(cipher) は､情報の安全を守る技術の総称です｡最近は､広義の意味で様々な技術を暗号と読んでいます｡暗号の機能は､以下のようなものがあると思います｡
暗号は符号理論の一種でもあります｡（参照→符号）
目的 概要
守秘 最もｵｰｿﾄﾞｯｸｽな暗号利用の方法ではないでしょうか
文書の真正性 文書が改ざんされていないこと､文書作成者が誰であるか確認する
本人認証 本人であることを確かめる
その他 個人情報が露見しないよう情報収集するなど･･･
暗号を応用した製品や技術には､以下のようなものがあります｡
名称 概要
PGP 電子ﾒｰﾙ用ﾂｰﾙで､ｱﾌﾟﾘｹｰｼｮﾝﾚﾍﾞﾙで暗号化します｡
Kerberos 汎用です｡ｸﾗｲｱﾝﾄｻｰﾊﾞ間の通信に組み込んで利用します｡
SSL ｿｹｯﾄﾚﾍﾞﾙを暗