暗号の数学

計算量

計算複雑度

あるアルゴリズムを解くのに必要な計算時間であり,対象とする問題の入力のサイズ n の関数で表す. あるアルゴリズムの計算複雑度が n を使って関数 f (n) で表すことができて,

n > n0 に対して, f (n) < c |g(n)|   (n0:定数)

となれば,O(g(n)) の複雑度があるという.

また,計算量の評価を以下の式で表すことがある.

Ln[v, c] = exp{(c + o(1))(log n)v(log log n)(1-v) }

ここで,

である. また, o(1) は1を超えない定数であり,n → ∞ のとき0に漸近する.

計算量による問題の分類

暗号の実現に使われる解くのが困難な代表的な問題には,次のようなものがある.

数の表現

整数の表現


inserted by FC2 system