ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門　2.4〜2.6

暗号

暗号理論入門 原書第3版

暗号理論入門 原書第3版

2.4 Ｏ記法とΩ記法

k は自然数、 X, Y \in \mathbb{N}^k とする。f : X \to \mathbb{R},\ \ g : Y \to \mathbb{R} は関数であるとする。
n_i \gt B,\ \ 1 \le i \le k となるすべての(n_1,\ ...,\ n_k) \subset \mathbb{N}^k に対して、次のことが成立する正の実数 B と C が存在するとき、 f = O(g) と書く。（g = \Omega(f) とも書く。）

  1. (n_1,\ ...,\ n_k) \in X \cap Y、すなわちf(n_1,\ ...,\ n_k) と g(n_1,\ ...,\ n_k) が定義されていて、
  2. f(n_1,\ ...,\ n_k) \le Cg(n_1,\ ...,\ n_k) である。

g が定数であれば f = O(1) と書く。
f = O(g) が成立するとき、f は高々 g のオーダーであるという。

（正の実数C倍程度でf()とg()の大小関係が固定化するなら、オーダーは一緒ということか？）

2.5 加法、乗法、整除の計算量

a と b は2進展開で与えられている自然数であるとする。a の2進長を m 、b の2進長を n とする。
2つのbitの和が時間Ｏ(1)を必要と仮定すると、a と b の和は実行時間O(\max \{m, n\})を必要とする。
同様に a から b を実行時間O(\max \{m, n\})で引くことができる。

a * b は実行時間O(mn)がかかる。
a と b で割って余りを求める除法は、時間O(bq)を必要とする。ここで q は商である。

2.6 多項式時間

一つのアルゴリズムに整数 z_1,\ ...,\ z_n を入力すると仮定する。
もし負でない整数 e_1,\ ...,\ e_n が存在し、アルゴリズムの実行時間が
　O((size\ z_1)^{e_1}(size\ z_2)^{e_2} \cdot \cdot \cdot (size\ z_n)^{e_n})
であるとき、このアルゴリズムは多項式実行時間(polynomial running time)をもつという。
（アルゴリズムは指数 e_i が小さいときのみ、実用上効率的といえる）