計算量：計算時間の見積もり
べき乗計算：$x^n$
素朴な方法：$n$回の掛け算$\implies 10^{nの表現の長さ(桁数)}\hspace{18mm}$に比例
高速計算法：$2\log n$回の掛け算$\implies nの表現の長さ(桁数)$に比例
整列：$n$個のデータを大きさの順に並べ替える
選択法：$n^2$に比例
クイックソート：平均的には $n\log n$ に比例
ベキ乗計算$y^x$ ($m$を法とする)
素朴なベキ乗計算法
$y,y^2,y^3,\dots,y^x$ と$y$を順に掛けていく
$x-1$ 回の掛け算が必要$\implies x$ に比例する計算時間$\implies x$ の桁数が増えてくると、現実的には計算できない
高速ベキ乗計算 Binary法
$y^1, y^2, y^4, y^8,\dots$の値を利用すると桁数の $2\frac{\log 10}{\log 2}\fallingdotseq 6.644$倍以下の乗算回数
例．$y^{22}＝y^{16+4+2}＝y^{16}\times y^4\times y^2$なので、
$y^2, y^4, y^8, y^{16}$の計算に掛け算4回、$y^{16}\times y^4\times y^2$の計算に掛け算$2$回で計$6$回
計算時間を
MOD電卓で試してみよう
【y
x】ボタンでは$1$に$y$を$x$回掛けて$y^x$を計算
【速y
x】ボタンは高速ベキ乗
整列(ソーティング)
選択ソート
「未整列部(赤表示)の最大値を選択して右端に移動させる(青表示)」を繰り返す。
計算時間：$n(n+1)/2$に比例
クイックソート
「未整列部(
[赤字])を、右端の値を基準に、基準値以下(
[赤字])と基準値以上(
[赤字])に分割」を繰り返す
計算時間：平均して $n\times\log n$に比例（計算例で赤字部分の長さの総和）
整列法比較アプリ（右上）で計算時間を比較してみよう。
手に負えない問題
プログラムが実行可能：計算時間が問題(入力)のサイズの多項式で抑えられる
素朴べき乗：実行可能でない
高速べき乗、選択法、クイックソート：実行可能
手におえない問題：実行可能なプログラムが存在しない問題
以後、問題をyes/no問題に限定する。
パズル．多項式時間プログラムを実効可能なプログラムとすることの是非を論ぜよ。
非決定性プログラム
非決定性プログラム：非決定性命令を含むプログラム
非決定性命令：次の動作を有限個の候補の中から選べる
計算：次の動作をうまく選んだ時に正しく計算できればよい
$\iff$可能な計算の中に正しく計算するものがあればよい
計算時間：正しく計算するものの中での最短時間としてよい
但し、正答がnoのときにyesと答える場合があってはいけない。
定理．非決定性プログラムで$t(n)$時間で計算できる問題は、
決定性プログラムで$a^{t(n)}$時間($a$は選択肢数の最大値)で計算できる。
略証：すべての選択肢を試行錯誤の虱潰しで調べればよい。
$\mathcal{P},\ \mathcal{NP}$
クラス$\mathcal{P}$:多項式時間決定性プログラムで解ける問題
クラス$\mathcal{NP}$：多項式時間非決定性プログラムで解ける問題
$\mathcal{P}\subseteq\mathcal{NP}$。
$\mathcal{P}\ne\mathcal{NP}$か否かが有名な未解決問題
(
ミレニアム問題)
オイラー路の存在判定問題$\in\mathcal{P}$
∵)オイラーの定理があるから
ハミルトン路の存在判定問題$\in\mathcal{NP}$
- ハミルトン路を非決定的に選択できれば、それがハミルトン路であることの検証は多項式時間で可能
- $\mathcal{P}$に属すか否かは知られていない
$\mathcal{NP}$問題の別表現
証拠が与えられれば、その答えがYesであることを、問題(入力)サイズの多項式時間内に検証できる問題。
$\mathcal{NP}$完全問題
問題$P$が$\mathcal{NP}$完全：問題$P$を解くプログラム$M_P$から、すべての$\mathcal{NP}$問題$Q$に対して、$Q$を解くプログラム$M_Q$を多項式時間で作れる$\mathcal{NP}$問題
$\mathcal{NP}$完全問題のどれか１つでも$\mathcal{P}$問題であれば、$\mathcal{P}=\mathcal{NP}$
つまり、$\mathcal{NP}$問題の中で、もっとも難しいと考えられる問題
Cookは充足可能性判定問題が$\mathcal{NP}$完全であることを示した(1971)。
充足可能性判定問題
与えられた論理式の値を真にする変数値の割り当てが存在するか否か判定する問題
証明のアイディア
$M_P$：$\mathcal{NP}$問題$P$を解く非決定性多項式$p(n)$時間チューリング機械とする。
$M_P$はサイズ$n$の入力$x$に対し、$p(n)$ステップで問題$P$の答$P(x)=$yes/noを(例えば)最初のセルに書き込んで停止する
$M_P$の入力$x$に対する動作列を記述し答がyesかnoかを判定する論理式$L(x)$を$N:=p(n)+1$の多項式時間で作り、
$L(x)$が充足可能$\iff P(x)=$yes となるようにする
| 変数 | $=真$ の意味 | 個数 |
| $S_{tq}$ | 時点$t$の$M_P$の内部状態が$q$ | $N\times$状態数 |
| $T_{tja}$ | 時点$t$のテープセル$j$の内容が記号$a$ | $N^2\times$記号数 |
| $H_{tk}$ | 時点$t$のヘッド位置が$k$ | $N^2$ |
これらの変数に対する真偽割り当てが、$M_P$の正しい計算になって(動作規則を満たして)いて出力がyesのときにのみ真となるような論理式をつくればよい。
$\mathcal{NP}$完全問題の例
充足性判定問題
ハミルトン(閉)路問題：与えれれたグラフがハミルトン(閉)路を持つか
巡回セールスマン問題：与えれた都市をすべてめぐるコスト$w$以下の路があるか
3彩色問題：与えれたグラフの頂点を3色で塗り分けることができるか
$\mathcal{P}$問題ではなさそうな$\mathcal{NP}$問題
素因数分解：与えられた数の素因数分解を求める
（素数判定は最近$\mathcal{P}$問題であることが示された）
公開鍵暗号
送信者 通信路 受信者
平文[暗号化]⇒ 暗号 ⇒[復号]平文
共通鍵暗号：送信者と受信者で実質的に同じ鍵を用いる
鍵(と手順)を秘密裡に共有し(ネット上で可能？)
送られた暗号をその鍵で復号
例 IBM[1文字前]⇒ HAL ⇒[1文字後]IBM
公開鍵暗号：送信者(暗号化)と受信者(復号)で異なる鍵
受信者が暗号化の鍵(と手順)を公開
送られた暗号を秘密にしている鍵で復号
公開(暗号化)鍵から秘蜜(復号)鍵が分からないのか？
RSA暗号、楕円曲線暗号
RSA公開鍵暗号の作成実験
$p,q$が素数$\implies x=x^{1+(p-1)(q-1)} \pmod{pq}$
$x=x^{1+(p-1)(q-1)}=x^{1+2(p-1)(q-1)}=\cdots \pmod{pq}$なので
$de＝1 \pmod{(p-1)(q-1)}$なら$(x^d)^e=(x^e)^d=x^{de}=x \pmod{pq}$。
$n=pq$を法として$d$乗と$e$乗が互いに逆関数$\implies$暗号化と復号に利用
RSA暗号の安全性
RSA暗号を破るには、次のような方法が考えられる。
- 暗号(の値)を、$n$を法として1乗、2乗、3乗、$\dots$して元に戻るか否かを調べる。$d$乗まで調べた時点で元に戻るから、秘密鍵 $d$ をいつかは知ることができる。
- $n$を素因数分解して、$p, q$を求め、$(p-1)(q-1)$を法とする$1\div e$を計算して$d$を求める。
- 推測した平文(の一部)$x$を$\pmod{n}$で$e$乗して盗聴した暗号(の一部)$y$と一致するか見る。
すべて虱潰しの方法であり、素朴ベキ乗計算の実習でみたように、$n$の値や秘密鍵、素数$p、q$を十分おおきくとれば安全と考えてよい。
ところで、$x^d$の計算は復号計算でもあるから、その計算に $x$を$d-1$回掛ける素朴な方法しかなければ、復号にとんでもない時間がかかってしまうことになり、RSA暗号は機能しない。幸い、$d$の値がわかっていれば、$d$乗を高速に行うBinary法が知られている。
暗号の安全性と$\mathcal{P}\ne\mathcal{NP}$
以上のことから、
復号は、秘密鍵$d$を知っている本人は高速実行できるが、たとえ暗号を入手(盗聴)できたとしても、秘密鍵を知らない第3者が可能な素朴な方法では、現実的な時間内に実行できない ことがわかる。
現在のところRSA暗号を現実的な時間内に破る方法は知られていない。
- について言えば、与えられた $x,y,n$ に対し、$x=y^d \pmod{n}$を満たす$d$を求める効率的な方法は知られていないし
- についていえば、$n$から$p, q$を求める効率的な素因数分解の方法は知られていない。
しかし、何か巧妙な方法が、まだ見つかっていないだけで、今後見つかる可能性は今のところ$0$とは決まっていない。そのような方法は存在しえず、それゆえ
RSA暗号は安全であると広く信じられてはいるが、そのことの数学的に厳密な証明は得られていない。このことは、
$\mathcal{P}\ne\mathcal{NP}$問題というクレイ数学研究所から100万ドルの賞金がかけられている有名な未解決問題の一つに関わる問題である。
電子署名
署名 := 文書を秘密鍵で暗号化したもの
文書＋署名の受取人は公開鍵で署名を復号して文書との一致を検証する
公開鍵で復号できる暗号を作れるのは秘密鍵の持ち主だけ
$\implies$文書の改ざん、署名の偽造(なりすまし)が防げる
秘密(鍵)を明かすことなく、秘密(鍵)を知っていることを証明する（納得させる）
$\iff$ゼロ知識証明
マジックプロトロコル
コイントス：A,B 両者が信頼できる第三者を介さずに通信線上で行う
コインを投げるAは、Bの答を聞いた後でコインの裏表を変えられない
裏表を当てるBは、Aが投げたコインを盗み見できない
Bが答えた後、その当否を両者(特にB)が確認できる
プロトコル(通信手順)
- Aは乱数$r$をBに送り、$r$のAによる署名(秘密鍵による暗号)の偶奇をBに問う。
- Bは偶奇を答える。
- Aは$r$の署名をBに送り、Bはそれを(公開鍵を使って)検証する
パズル．上のプロトコルがうまく働くことを示せ。
他のマジックプロトコル：いずれも通信線で第三者を介さずに行う
金持ち比べ：互いの資産額を知らせずに、その大小を比べる
カード配り：トランプのカードを配る
電子投票：投票の秘密を保って投・開票を行う
終了ページ