暗号理論入門(整数2)

　前回、『暗号理論入門(整数1)』として書いた記事の続きになります。前回の記事を読んでいないとわからないということはないと思いますが、事前知識として最低限、$g$進展開を知っていれば理解できると思います。

$O$記法と$\Omega $記法

暗号アルゴリズムを作る際には、以下の2点について評価する必要があります。

・そのアルゴリズムがどの程度の計算量を持つのか
・どれだけの大きさの格納領域(記憶領域)を必要とするのか

これらを評価する際に、$O$記法と$\Omega $記法を利用すると便利です。

ここで、まず$O$記法と$\Omega $記法を説明するうえで必要となってくる文字を導入していきます。

$k:$自然数、$X , Y \subset \mathbb{N}^k$とする。そして、$f:X \rightarrow \mathbb{R} \hspace{1mm},\hspace{1mm} g:Y \rightarrow \mathbb{R}$は関数であるとする。

$n_i > B\hspace{2mm}(1 \leqq i \leqq k)$となるすべての$(n_1 , \cdots , n_k) \in \mathbb{N}^k$に対して、次のことが成立する正の実数$B$と$C$が存在するとき、$f = O(g)$と書く。

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

つまり、ほとんど至るところ$ f(n_1 , \cdots , n_k) \leqq Cg(n_1 , \cdots , n_k)$が成立することを意味している。これはまた$g= \Omega(f)$とも書く。$g$が定数であれば、$f = O(1)$と書く。

$f = O(g)$が成立しているとき、$f$は高々$g$のオーダであるという。

なぜなら、前者は、$2n^2 + n + 1 \leqq 4n^2$がすべての$n \geqq 1$に対して成り立ち、後者は、$2n^2 + n + 1 \geqq 2n^2$がすべての$n\geqq1$に対して成立するからです。

$f(n) = \lfloor log_g n \rfloor + 1$で、$\lfloor log_g n \rfloor + 1 \leqq log_g n + 1 = \dfrac{log \hspace{2mm}n}{log\hspace{2mm}g} + 1$.

$n > 3$に対して、$log\hspace{2mm}n > 1$となるので、

$\dfrac{log \hspace{2mm}n}{log\hspace{2mm}g} + 1 < (\dfrac{1}{log\hspace{2mm}g} + 1)log\hspace{2mm}n$.

$\dfrac{1}{log\hspace{2mm}g} + 1$を定数としてみてあげると、$f(n) = O(log\hspace{2mm}n)$が成立することが分かる。

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

多くの暗号方式では、長い整数の加減乗除をします。その際に、その計算の実行時間がどのくらいなのかを調べる必要があります。そのために実際のコンピュータとできる限り似た計算モデルを設定します。ここでは、必要な計算時間に対してよい評価をするモデルを解説していきます。

$a,b:$二進展開で与えられている自然数、$a$の二進長を$m$、$b$の二進長を$n$とする。

$a+b$を計算するために、$a$と$b$の二進展開を書き、ビットごとに和を計算し、繰り上げをする。

2つのビットの和が時間$O(1)$を必要とすると仮定する。このとき、$a$と$b$のビットの和は実行時間$O(\max\{m,n\})$を必要とする。

※$O(1):$1ビット(1桁)ごとに計算するのにかかる時間

$a$は$m$、$b$は$n$桁あるので、最大で$\max\{m,n\}$計算する。
$a$から$b$を引く場合も、$O(\max\{m,n\})$で計算できる。

二進数のわり算を、引き算を繰り返して実行するアルゴリズムとして見る。$k$をこの除法でのビットの総数とする。

このとき、二進長$\leqq n+1$の二つの数について、高々$k$回一方から他方を引く必要があるので、実行時間$O(kn)$がかかる。

ここまでの内容をまとめていきます。ここからは整数$a$の二進長を$size(a)$と表すことにします。

多項式時間

暗号方式の分析では、その方式が効率的に機能していて、効率的に破られることがないかを示す必要があります。ここでは、アルゴリズムが効率的であるかどうかを示す指標である多項式時間について軽く触れていきます。

多項式時間をざっくり説明すると、入力する大きさを$N$としたとき、計算時間が$N$の何乗か程度で収まるアルゴリズムのことです。

1つのアルゴリズムに整数$z_1 , \cdots,z_n$を入力すると仮定する。もし負でない整数$e_1,\cdots,e_n$が存在し、アルゴリズムでの実行時間が

$$ O(size(z_1)^{e_1} \cdots size(z_n)^{e_n})$$

であるとき、このアルゴリズムは多項式実行時間を持つという。

アルゴリズムの実行時間が多項式実行時間であるとき、このアルゴリズムは効率的であるという。

今回は以上です。