アルゴリズムの性能を分類するのはO記法を使用する
O記法はパラメータnに関する関数f(n)のnが大きくなった時の振る舞いを表現
f(n)のオーダーはO(n^d)
入力パラメータによる計算式に応じて、定数時間アルゴリズム、線形時間アルゴリズム、多項式アルゴリズムという
e.g. y=2^x, y=x^2, y=x, y=log(x)
メモリの消費量もO(n), O(n log(n))など色々なものがある
ビットと表現可能な範囲
### セキュリティパラメータ
暗号を破るのに必要な計算コスト
暗号技術の危殆化とは、計算機の性能向上や暗号解読・攻撃手法の進展に伴って暗号の安全性が低下すること
現在安全とされる128ビットセキュリティ
– 共通鍵暗号:128
– ハッシュ関数: 256
– RSA暗号: 約3000
– 楕円曲線暗号: 256 (2024ビットRSAより安全と考えられている)
