どうも、solobochiです。
今年度受講している文部科学省のデータ関連人材育成の学習プログラムでコンピュータサイエンスについて学習しましたのでまとめておきます。
目次
7/27更新 Update
コンピュータサイエンス
👉コンピュータの科学、では直訳ではあるが説明としては不十分。
👉Wikiによれば、情報と計算の理論的基礎、およびそのコンピュータへの実装・応用に関する研究分野
👉正確には、情報処理・問題処理をコンピュータの計算手順に転換することにより自動化する方法を発見する研究分野
→すなわち、言い換えれば、コンピュータシステムを作るための科学
👉具体的な研究分野としては、プログラミング言語論、計算理論・計算の基礎、アルゴリズム論、人工知能、自然言語、ソフトウェア工学、etc
ユークリッドの互除法
👉2つの自然数の最大公約数を求めるアルゴリズム
└アルゴリズムとは:問題を解く手順について定式的に表現したもの。計算可能なもの(=チューリングマシンで解くことができるもの)を計算するためのもの。
👉人類最古のアルゴリズム
🔸アルゴリズムは以下の通り
ユークリッド互除法
となるa,bについての最大公約数を求める
ⅰ) 以下の式のx , yにそれぞれa , bを代入する
ⅱ) y ≠ 0まで以下1,2を繰り返す
1.
(xをyで割った商をq、余りをrとする)◀️a = bq + r が成り立つ時、aとbの最大公約数は、bとrの最大公約数に等しいことを利用する
2. xにyを代入、yにrを代入する
ⅲ) y = 0となった時のxの値が最大公約数
👉数式で簡潔に書くと、
ユークリッド互除法を数式で簡潔に表現
の時、
gcd (a , b) = gcd (b , r) = d
※gcd :greatest common divisor(最大公約数)
フェルマーの小定理
👉RSA公開鍵暗号にも応用されている素数に関する定理
フェルマーの小定理
素数p、pと互いに素である整数aについて
因数分解の計算量
👉多項式時間で解ける素因数分解アルゴリズムは見つかっていない
因数分解の計算量
・計算量とは
→計算量理論:計算の複雑さを数学的に表現する
→入力サイズの関数で表現する
└→オーダー記法:O
・オーダー記法の一覧
オーダー記法(O) | 内容 |
O(1) : 定数時間 | データ数(N)によらず同じステップ数で実行できるアルゴリズム。 例)ハッシュ探索、ハッシュテーブルによるデータ検索、配列要素へのアクセス |
O( |
処理ごとに処理対象を減らすことのできるアルゴリズム。 データ数(N)が増えてもそれほど計算時間はほとんど増えない。 例)2分探索 |
O(n) : 線形時間 | データ数(N)の分だけ時間がかかるアルゴリズム。 例)forループ1回分、未ソート配列の探索 |
O( |
O(n)相当のループとO( 例)クイックソート(基準値との比較でソート)、マージソート、ヒープソートなどの高速ソートアルゴリズム |
O( |
O(n)相当のループを二重にしたアルゴリズム。全ての組み合わせのペアを調べるようなアルゴリズム。 例)バブルソート、挿入ソートなどの単純なソートアルゴリズム、工夫しないソートアルゴリズム。 |
O( |
全ての組み合わせについて調べるようなアルゴリズム。パターンを列挙する必要がある問題は指数時間となる。 例)ルービックキューブの総当たりによる解法、素因数分解の試し割りによる解法 |
O(n!) : 階乗時間 | Nの階乗に比例する時間がかかるアルゴリズム。 例)巡回セールスマン問題 |
因数分解の計算量(続き)
・整数Nを素因数分解するもっとも素朴な方法である、試し割り
→1から順に割っていき、まで割る
→の総当たりなので、指数時間アルゴリズム
・コンピュータ内部では0、1の2進数で整数・状態を表現しているので、1ビットで10進数の1、2を表現する。
(※余談→ノイマン型:0か1、量子:0と1の重ね合わせを表現)
同様に、2ビットで、1〜4、3ビットで1〜8、、、、pビットであれば、まで表現できる
Nを表現するために必要なビット数計算
整数Nを表現するために必要なビット数は、ビット(※)
※ のとき
⇒
⇒
∴
整数Nを素因数分解するアルゴリズムの計算量
⇒ より、
整数Nを試し割りでまで全て試していく方法の計算量は、
の指数時間アルゴリズムとなる
RSA公開鍵暗号
👉RSA公開鍵暗号の安全性は素因数分解の難しさ、計算量の大きさに依存している
RSA公開鍵暗号方式
・RSA公開鍵暗号とは
→素数p,qの積n()とある整数eを公開鍵として公開しておき、暗号文を公開鍵で暗号化
※平文に対して、e乗してmod nを求める
→暗号文を平文にする際には、秘密鍵dを使って、暗号文をd乗してmod nを求めて平文にする
→p、qがわかっていれば簡単だが、p、qが分からない場合は、公開されているnからp,qを探さなければならない。この時素因数分解の計算量が膨大であることがRSA公開鍵暗号方式の安全性を保っている。

dav
量子コンピュータ
👉RSA公開鍵暗号方式は電子署名やメール、SSLサーバ認証(https)を用いたECなど今やありとあらゆる場面で利用されているが、量子コンピュータにより素因数分解の計算量が低コスト化すればRSA公開鍵暗号をはじめとする様々なセキュリティが破られることになる
Shorのアルゴリズム
・Shorのアルゴリズム
→Shorのアルゴリズムを用いると、素因数分解を効率的に解くことができる
→2n個の量子ビットがあれば、の因数分解を効率的に解くことができる
以上